bfs走出迷宫

bfs走出迷宫_第1张图片


#include

#include  
using namespace std;
struct node{
int x,y,step;
};
queue Q;
int m,n;
const int maxn=200;
char map[maxn][maxn];
bool book[maxn][maxn]={false};
int next[4][2]={
0,-1,
0,1,
-1,0, 
1,0
};
int bfs(int x,int y,int endx,int endy){
node nn;
nn.x=x; nn.y=y; nn.step=0;
while(!Q.empty()) Q.pop();
Q.push(nn);
book[x][y]=true;
while(!Q.empty()){
node top;
top=Q.front();
Q.pop();
for(int i=0;i<4;i++){
int nx=top.x+next[i][0];
int ny=top.y+next[i][1];
if(nx<0 || nx>n-1 || ny<0 || ny>m-1) continue;
if(map[nx][ny]=='*')    continue;
if(book[nx][ny]==true)  continue;
node now;
now.x=nx;  now.y=ny;  now.step=top.step+1;
if(nx==endx  &&  ny==endy)  return now.step;
Q.push(now);
book[nx][ny]=true;


}
int main(int argc, char** argv) {
cin>>m>>n;
for(int i=0;i for(int j=0;j cin>>map[i][j];
}
}
int startx,starty,endx,endy;
for(int i=0;i for(int j=0;j if(map[i][j]=='S'){
startx=i;
starty=j;
}
if(map[i][j]=='T'){
endx=i;
endy=j;
}
}
}
int ans;
cout< cout< ans=bfs(startx,starty,endx,endy);
cout< return 0;
}

你可能感兴趣的