题目：[kuangbin带你飞]专题一 简单搜索 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;
}