题解 | #迷宫问题#

1. 使用DFS回溯。
2. 别忘了使用visit数组
3. 别忘了return

#include<bits/stdc++.h>

using namespace std;

int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

void DFS(vector<vector<int>> maze, int r, int c, vector<pair<int,int>>& path, vector<vector<pair<int,int>>>& all_path, vector<vector<bool>>& visited){


    //base case
    if(r == maze.size() -1 && c == maze[0].size() -1){//记住是-1
        all_path.push_back(path);
        return;//别忘了return
    }


    //回溯，做选择
    for(int i = 0; i< 4;i++){

        int newx = c + dx[i];
        int newy = r + dy[i];

        if(newx<0||newx>=maze[0].size()||newy<0||newy>=maze.size()||maze[newy][newx]==1||visited[newy][newx] ){
            continue;
        }

        //回溯
        visited[newy][newx] = true;
        path.push_back({newy,newx});

        //入递归
        DFS(maze, newy, newx, path,all_path,visited);

        //回退
        visited[newy][newx] = false;
        path.pop_back();

    }

}



int main(){

    int r,c,a;
    while(cin>>r>>c){
        vector<vector<int>> maze(r,vector<int>(c,0));

        for(int i =0; i< r; i++){
            for(int j =0; j< c; j++){
                cin>>a;
                maze[i][j] = a;
            }
        }

        vector<vector<bool>> visited(r, vector<bool>(c, false));

        //DFS(回溯)

        vector<pair<int,int>> path;
        vector<vector<pair<int,int>>> all_path;
        path.push_back({0,0}); //初始点
        visited[0][0] = true;
        DFS(maze, 0,0, path,all_path,visited);

        sort(all_path.begin(),all_path.end());//双数组排序，默认按照数组从小到大

        vector<pair<int,int>> final_path(all_path[0]);//别忘了访问数组

        for(auto c : final_path)
        {
            cout << "(" << c.first << "," << c.second << ")" << endl;
        }

    }




}