7218:アルギノンへの花束シロ初識広捜

15389 ワード

今日、やっと広捜(bfs)を使って問題を解決する方法をマスターしました.では、一つの例から、広捜の魅力を検討してみましょう.
link.
私はこの問題を名前にしました:マウスはチーズを食べますbfs
簡単に言えば、構造体が現在の座標と歩くステップ数を格納し、キューを再利用し、キューに1つずつ押し込み、最初に私たちが探している「チーズ」かどうかを判断することです.次に、(コードの実装):
まずtグループデータ,r行c列,方向配列xx,yy,次いでmap文字配列,v訪問配列,構造体node記録座標とステップ数を定義する.
次にbfsです.最小ステップ数を見つけることを目的としているので、int型データを返す必要があります.そのため、関数タイプをintと定義し、4つのパラメータ(各データの開始座標と終了座標が異なるため)nx,ny,ex,eyを入力します.
次に1つのキューを定義し、2つのnode型変数now,nextを定義し、nowを初期化し、配列中の座標に対応する点を訪問して1を訪問し、nowをキューに押し込み、キューが空でない場合、キュー内の最初の値をnowに割り当て、最初のポップアップを行い、最初の要求を満たすかどうかを判断し、満足すればnowのステップ数を返す.
次に、上下左右の探索を行い、方向配列とループを用いて、次に新しい座標が境界を越えているか否かを判定する='#'==訪問したことがあるか否かを判定し、要求を満たすならば、新しい座標の訪問座標を1にし、nextノードの座標に新しい座標を格納させるとともに、nextのステップ数がnowステップ数の+1に等しくなるようにし、nextノードをキューに押し込み、循環してこの層がまだ満足しているかどうかを見て、満足すれば押し込み、
あなたがアクセスした最初のノードの座標が最終座標になるまで最終座標を返すステップ数です.最終キューが空の場合、それはアクセスされていない場合は0を返します(なぜ0を返しますか?メイン関数でif文を使用すると、返された数が0でない限り見つかります.そうしないと見つからないので、関数では0を返します)
メイン関数にmap文字配列を入力と、開始座標と終了座標を同時に探し、bfs実行前に訪問配列を0にする操作を忘れないでください.
皆さんの鑑賞に感謝して、自分のためにほめて、私のコードを送ります
#include
#include
#include
using namespace std;
int t,r,c,xx[]={0,1,0,-1},yy[]={1,0,-1,0};
char map[201][201];
int v[201][201];
struct node{
    int x,y,step;
};
int bfs(int nx,int ny,int ex,int ey)
{
    queue<node> q;
    node now,next;
    now.x=nx;
    now.y=ny;
    now.step=0;
    v[now.x][now.y]=1;
    q.push(now);
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            if(now.x==ex&&now.y==ey)
            return now.step;
            int dx=now.x+xx[i];
            int dy=now.y+yy[i];
            if(dx>=0&&dx<r&&dy>=0&&dy<c&&v[dx][dy]==0&&map[dx][dy]!='#')
            {
                v[dx][dy]=1;
                next.x=dx;
                next.y=dy;
                next.step=now.step+1;
                q.push(next);
            }
        }
    }
    return 0;
}
int main()
{
    int i,j,nx,ny,ex,ey;
    cin>>t;
    while(t--)
    {
        cin>>r>>c;
        for(i=0;i<r;i++)
        {
            for(j=0;j<c;j++)
            {
            cin>>map[i][j];
            if(map[i][j]=='S')
            {
                nx=i;
                ny=j;
            }
            if(map[i][j]=='E')
            {
                ex=i;
                ey=j;
            }
            }
        }
        memset(v,0,sizeof(v));
        int k=bfs(nx,ny,ex,ey);
        if(k)
        cout<<k<<endl;
        else
        cout<<"oop!"<<endl;
    }
    return 0;
}