题目的主要信息：

输入一个迷宫，其中的1表示墙壁，0表示可以走的路。
迷宫中只能横着走或竖着走，不能斜着走。

要求从坐标[0,0]出发,找到一条到右下角的路径走出迷宫。

方法一：

采用递归。用ans保存最终路径，temp用于暂存递归中的路径，row和col为迷宫的行数和列数，flag用于递归结束判断。dfs函数用于递归，从坐标(0,0)出发，每经过一个坐标就把它存到temp中，并且将当前位置的值从0变为1，表示当前位置已经访问过，不可重复访问。接着尝试从上下左右四个方向走，如果flag为true说明已经找到了一条路径，结束递归。如果四个方向都走不通，那么将temp回溯，并且恢复当前位置状态为为访问。 alt 具体做法：

#include<iostream>
#include<vector>

using namespace std;

vector<pair<int,int>> ans;//最终路径
vector<pair<int,int>> temp;//暂存路径
int row,col;//迷宫的行数和列数
bool flag=false;//用于递归结束判断


void dfs(vector<vector<int>> &dp,int a,int b){
    temp.push_back({a,b});
    dp[a][b] = 1;//将当前位置的0改为1，表示当前位置已经访问过了，不可重复访问
    if(a == row - 1 && b == col - 1){//已经走到了右下角
        ans = temp;//保存最终路径
        flag = true;//结束循环
        return;
    }
    
    if(a+1 < row && dp[a+1][b] == 0){
        dfs(dp,a+1,b);//向下走
        if(flag) return;
    }
    if(b+1 < col && dp[a][b+1] == 0){
        dfs(dp,a,b+1);//向右走
        if(flag) return;
    }
    if(a-1 >= 0 && dp[a-1][b] == 0){
        dfs(dp,a-1,b);//向上走
        if(flag) return;
    }
    if(b-1 >= 0 && dp[a][b-1] == 0){
        dfs(dp,a,b-1);//向左走
        if(flag) return;
    }
    temp.pop_back();//回溯
    dp[a][b] = 0;//恢复当前位置为0
}

int main(){
    while(cin >> row >> col){//输入迷宫的大小
        vector<vector<int>> dp(row,vector<int>(col,0));
        for(int i = 0;i < row;i++){//输入迷宫
            for(int j = 0;j < col;j++){
                cin >> dp[i][j];
            }
        }
        dfs(dp,0,0);
        for(auto it:ans){//输出最终路径
            cout << '(' << it.first << ',' << it.second << ')' << endl;
        }
        //清空
        ans.clear();
        temp.clear();
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (m n)$ ，dfs需要遍历整个迷宫。
空间复杂度： $O (m n)$ ，递归栈的大小。

方法二：

采用广度优先搜索。首先从根节点出发，将当前节点四个方向的所有可达子节点依次访问，存到队列中，并且再father数组中记录子节点的父节点，然后再根据队列依次访问子节点，一直下去直到所有节点被遍历。访问到(n-1,m-1)节点时，说明已经找到一条路径，可以从(n-1,m-1)搜索father数组找到这条路径，但是这个路径顺序是反的，因此，用一个栈存父节点，最后输出这个栈就是从(0,0)到(n-1,m-1)的路径。

具体做法：

#include <iostream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

pair<int,int> direction[4]={{-1,0},{0,1},{1,0},{0,-1}};//上下左右四个方向

int main(){
    int n,m;
    while(cin >> n >> m){
        vector<vector<int>> maze(n,vector<int>(m,0));
        vector<vector<int>> visit(n,vector<int>(m,0));
        pair<int,int> father[n][m];//记录当前下标的父亲下标
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin >> maze[i][j];//输入迷宫
            }
        }
        queue<pair<int,int>> q;//队列
        q.push({0,0});//左上角坐标入队列
        visit[0][0]=1;
        while(!q.empty()){
            auto pos=q.front();
            q.pop();
            if(pos.first==n-1&&pos.second==m-1){//遍历到最后一个节点，说明找到了路径，结束
                break;
            }
            for(int i=0;i<4;i++){//遍历四个方向
                int x=pos.first+direction[i].first;//下一格的横坐标
                int y=pos.second+direction[i].second;//下一格的纵坐标
                if(x<0||x>=n||y<0||y>=m){//如果该坐标超过了迷宫范围则放弃这个方向，继续下一个方向
                    continue;
                }
                if(visit[x][y]==0&&maze[x][y]==0){//如果(x,y)未访问过并且不是墙壁，则加入队列
                    father[x][y]={pos.first,pos.second};//(x,y)的父亲是pos
                    q.push({x,y});
                    visit[x][y]=1;
                }
            }
        }
        //输出整个路径
        stack<pair<int,int>> stk;
        stk.push({n-1,m-1});
        int i=n-1,j=m-1;
        while(i!=0||j!=0){//father中存着右下左上的一条路径，用栈将这条路径变为左上到右下
            pair<int,int> f=father[i][j];//查找父节点
            i=f.first;
            j=f.second;
            stk.push(f);
        }
        while(!stk.empty()){//输出整个栈
            cout<<'('<<stk.top().first<<','<<stk.top().second<<')'<<endl;
            stk.pop();
        }
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (m n)$ ，所有节点都会遍历一遍。
空间复杂度： $O (m n)$ ，father的大小为 $m\times n$ 。

题解 | #迷宫问题#

题目的主要信息：

方法一：

方法二：