題目：[kuangbin帶你飛]專題一 簡(jiǎn)單搜索 K
沒什么特殊的bfs就是記錄路徑。
ac代碼:
#include<iostream>
#include<queue>
using namespace std;
#define N 5
int mm[10][10];
bool vis[10][10];
int mov[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct node{
int x;
int y;
queue<string> path;
};
int main(){
for(int i = 0 ;i <N;i++){
for(int j = 0;j<N;j++){
cin>>mm[i][j];
}
}
queue<node> Q;
node start;
start.x = 0 ;
start.y = 0 ;
start.path.push("(0, 0)");
Q.push(start);
vis[0][0] = 1;
while(!Q.empty()){
node nownode;
node nextnode;
nownode = Q.front();Q.pop();
if(nownode.x==N-1&&nownode.y==N-1){
while(!nownode.path.empty()){
cout<<nownode.path.front()<<endl;
nownode.path.pop();
}
break;
}
nextnode= nownode;
for(int i = 0 ;i<4;i++){
nextnode.x = nownode.x+mov[i][0];
nextnode.y = nownode.y+mov[i][1];
if(nextnode.x>=0&&nextnode.y>=0&&nextnode.x<N&&nextnode.y<N
&&!vis[nextnode.x][nextnode.y]&&!mm[nextnode.x][nextnode.y]){
// cout<<nextnode.x<<" "<<nextnode.y<<endl;
string paths ="(";
paths+=(char)(nextnode.x+'0');
paths+=", ";
paths+=(char)(nextnode.y+'0');
paths+=")";
nextnode.path = nownode.path;
nextnode.path.push(paths);
vis[nextnode.x][nextnode.y]=true;
Q.push(nextnode);
}
}
}
return 0;
}
