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にする操作を忘れないでください.
皆さんの鑑賞に感謝して、自分のためにほめて、私のコードを送ります
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;
}