题解 | #迷宫问题#

c++, bfs,用链表保存路径

#include<bits/stdc++.h>
using namespace std;
int arr[15][15];
struct Node{
    int x;
    int y;
    Node *fa;
};
int fx[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
bool vis[15][15];
int main(){
    int n,m;
    while(cin>>n>>m){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>arr[i][j];
            }
        }
        for(int i=0;i<15;i++){
            for(int j=0;j<15;j++){
                vis[i][j]=false;
            }
        }
        queue<Node*> que;
        Node *node = new Node;
        node->x = 0;
        node->y = 0;
        node->fa=NULL;
        que.push(node);
        vis[node->x][node->y]=true;
        while(!que.empty()){
            node = que.front();
            que.pop();
            if(node->x == n-1&& node->y==m-1){
                stack<Node*> sta;
                while(node){
                    sta.push(node);
                    node = node->fa;
                }
                while(!sta.empty()){
                    node = sta.top();
                    sta.pop();
                    cout<<"("<<node->x<<","<<node->y<<")"<<endl;
                }
                break;
            }
            for(int i=0;i<4;i++){
                if(node->x+fx[i][0]<0||node->x+fx[i][0]>=n){
                    continue;
                }
                if(node->y+fx[i][1]<0||node->y+fx[i][1]>=m){
                    continue;
                }
                if(vis[node->x+fx[i][0]][node->y+fx[i][1]]){
                    continue;
                }
                if(arr[node->x+fx[i][0]][node->y+fx[i][1]]){
                    continue;
                }
                Node *newnode = new Node;
                newnode->x = node->x + fx[i][0];
                newnode->y = node->y + fx[i][1];
                newnode->fa = node;
                que.push(newnode);
            }
        }

    }
}