题解 | #迷宫问题#

递归，深度优先搜索

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
using namespace std;
int maxx,maxy;
class point{
    public:
        int x;
        int y;
        point *child;
        point(int a,int b):x(a),y(b){}
};

void dfs(point *pt,vector<vector<int>> &maze,vector<vector<bool>> &visited,bool &final){
    int x=pt->x;
    int y=pt->y;
    visited[x][y]=true;
    if(x==maxx-1 && y==maxy-1){
        final=true;
        pt->child=nullptr;
        return;
    }
    if(y - 1 >= 0 && maze[x][y-1] == 0 && visited[x][y-1] == false){
        point *temp=new point(x,y-1);
        pt->child=temp;
        dfs(temp,maze,visited,final);
        if(final) return;
    }//left
    if(x - 1 >= 0 && maze[x-1][y] == 0 && visited[x-1][y] == false){
        point *temp=new point(x-1,y);
        pt->child=temp;
        dfs(temp,maze,visited,final);
        if(final) return;
    }//up
    if(y + 1 < maxy && maze[x][y+1] == 0 && visited[x][y+1] == false){
        point *temp=new point(x,y+1);
        pt->child=temp;
        dfs(temp,maze,visited,final);
        if(final) return;
    }//right
    if(x + 1 < maxx && maze[x+1][y] == 0 && visited[x+1][y] == false){
        point *temp=new point(x+1,y);
        pt->child=temp;
        dfs(temp,maze,visited,final);
        if(final) return;
    }//down
    visited[x][y]=false;
    delete pt;
}

int main() {
    int a, b;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        bool final=false;
        maxx=a;
        maxy=b;
        vector<vector<int>> maze(a,vector<int>(b,0));
        vector<vector<bool>> visited(a,vector<bool>(b,false));
        for(int i=0;i<a;++i){
            for(int j=0;j<b;++j){
                cin>>maze[i][j];
                visited[i][j]=false;
            }
        }
        point *pp = new point(0,0);
        dfs(pp,maze,visited,final);
        while(pp!=nullptr){
            point *temp = pp;
            cout<<'('<<pp->x<<','<<pp->y<<')'<<endl;
            pp=pp->child;
            delete temp;
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")