BFS入門経典(天神小学校)に加えて行列の基礎説明

天神小学校時間制限(普通/Java):1000 MS/3000 MS運行メモリ制限:65536 KByte総提出:145試験合格:50
题目描述《corpse party:blood drive》中的一首歌《corpse party:blood drive》里的一首歌《corpse party:blood drive》里的一首歌《corpse party:blood drive》里的一首歌《corpse party:blood drive》.今は幸子がいないと仮定して、班長は自分の力で天神小学校を脱出しなければならない.天神小学校を二次元の迷路と見なすことができ、毎秒現在の位置から上下左右4つの隣接する格子の中までしか歩けない.天が小さくて崩れ続けているので、歩けない点が多い.班長に天小で完全に崩壊することができるかどうかを聞いて、つまりt秒以内に天神小学校を脱出することができます.
最初の行に1つの整数Tを入力し、データ群数を表すデータの最初の行に3つの整数n,m,tを入力すると、迷路の行数、列数、および天小崩壊までの残りの時間を表す.(3≦n,m≦20,t≦100)次にn行を入力し、各行に長さmの文字列が1つある.文字'.'通行可能文字を表す'*'は通行不能文字を表す'O'は出口文字を表す'X'は班長の開始位置を表す
出力出力出力「happy end」を脱出できれば「bad end」を出力
サンプル入力2 5 5 13.....*.*X*O ... …*.
5 5 14 ….. .*. .*X*O ... …*.
サンプル出力bad end happy end

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
const int lim=50;
using namespace std;
int dirx[4]= {-1, 1, 0, 0};
int diry[4]= {0, 0, -1, 1};
int row, col, time;
char Map[lim][lim];
int vis[lim][lim];
char str[300];
int xru, yru, xchu, ychu;
struct point
{
    int x;
    int y;
    int step;
};
void bfs();
int main ()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int i, j, T;
    cin>>T;
    while(T--)
    {
        cin>>row>>col>>time;  
        memset(str, 0, sizeof(str));
        memset(Map, 0, sizeof(Map));
        memset(vis, 0, sizeof(vis));
        for(i=1; i<=row; i++)
        {
            scanf("%s", str);
            for(j=1; j<=col; j++)
                Map[i][j]=str[j-1];
        }
        for(i=1; i<=row; i++)
            for(j=1; j<=col; j++)
            {
                if(Map[i][j]=='X')
                {
                    xru=j;
                    yru=i;
                }
            }
        for(i=1; i<=row; i++)
            for(j=1; j<=col; j++)
            {
                if(Map[i][j]=='O')
                {
                    xchu=j;
                    ychu=i;
                }
            }
        bfs();
    }
    return 0;
}

void bfs()
{
    int i, j;
    vis[xru][yru]=1;
    point node, t;
    queue<point> q;
    node.x=xru;
    node.y=yru;
    node.step=0;
    q.push(node);
    while(!q.empty())
    {
        node=q.front();
        q.pop();
        for(i=0; i<4; i++)
        {
            t=node;
            t.x+=dirx[i];
            t.y+=diry[i];
            t.step++;
            if(t.x==xchu&&t.y==ychu)
            {

                printf("%s", t.step<=time?"happy end
":"bad end
");
                return;
            }
            if(t.x<1||t.x>col||t.y<1||t.y>row||Map[t.y][t.x]=='*'||vis[t.y][t.x])
                continue;
            else
            {
                vis[t.y][t.x]=1;
                q.push(t);
            }
        }
    }
    printf("bad end
");
    return;
}

             ，  bfs   。           。(            ，       ，         ，         ) 

実はまだC++に接触していない学生に対して、このコードは少し理解しにくいように見えますが、言語は言語で、思考の含有量がなくて、文法の規則を覚えていればいいです.キューを使用するには、まずヘッダファイルを含める必要があります.すると、include.int変数のように、キュー、queue qを宣言します.カスタムポイントのキューを宣言しました.q.pop()は、q.pop(t)のように、キューの最初の要素tを「蹴り」に出すq.push()は、q.push(t)のように、キューの最後に要素tを「どうぞ」に与える.q.front()は、t=q.front(t)のように、キューの最初の要素をtに与えることである.q.empty()キューが空の場合はtrueを返し、そうでない場合はfalse q.size()がキュー内の要素の個数を返すので、q.size==0でもオブジェクトが空であるか否かを判断する方法です.一般的な基础の深さは最小の连通のブロック(种の诘め込みのアルゴリズムをも叫んで、ウィキペディアの种の诘め込みの言叶はGIFアニメーションがあって、みんなは见てみることができます)を探して、広く最短の経路を求めます.