求解迷宫从入口到出口的路径【算法】【栈】【深度优先搜索】

╰半夏微凉° 2023-10-03 17:40 4阅读 0赞

### 题目：求解迷宫从入口至出口的路径 ###

创建一个迷宫，求从入口通向出口的可行路径。  
为简化问题，迷宫用二维数组 int maze\[10\]\[10\]来存储障碍物的分布。  
假设迷宫的横向和纵向尺寸的大小是一样的，并由程序运行读入, 若读入迷宫大小的值是n（3<n<=10），则该迷宫横向或纵向尺寸都是n，规定迷宫最外面的一圈是障碍物，迷宫的入口是maze\[1\]\[1\]，出口是maze\[n-2\]\[n-2\], **若maze\[i\]\[j\] = 1代表该位置是障碍物，若maze\[i\]\[j\] = 0代表该位置是可以行走的空位（0<=i<=n-1, 0<=j<=n-1）**。求从入口maze\[1\]\[1\]到出口maze\[n-2\]\[n-2\]可以走通的路径。要求迷宫中只允许在水平或上下四个方向的空位上行走，走过的位置不能重复走，规定必须按**向右、向下、向左、向上的顺序向前搜索试探**。

**输入格式:**  
输入迷宫大小的整数n, 以及n行和n列的二维数组（数组元素1代表障碍物，0代表空位）。  
**输出格式**  
依次输出从入口到出口可行路径每个位置的行列下标（i,j），每个位置间用“,”分隔。若没有通路，输出：NO。

**输入样例 1**

4
    1 1 1 1
    1 0 1 1
    1 0 0 1
    1 1 1 1

**输出样例 1**

(1,1)(2,1)(2,2)

**输入样例 2**

10
    1 1 1 1 1 1 1 1 1 1
    1 0 0 1 0 0 0 1 0 1
    1 0 0 1 0 0 0 1 0 1
    1 0 0 0 0 1 1 0 0 1
    1 0 1 1 1 0 0 0 0 1
    1 0 0 0 1 0 0 0 0 1
    1 0 1 0 0 0 1 0 0 1
    1 0 1 1 1 0 1 1 0 1
    1 1 0 0 0 0 0 0 0 1
    1 1 1 1 1 1 1 1 1 1

**输出样例 2**

(1,1)(1,2)(2,2)(3,2)(3,1)(4,1)(5,1)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)(8,6)(8,7)(8,8)

**题目分析**  
注意题目的步骤，是从(1,1)开始的而不是(0,0)，且每次搜索是有一个方向的先后顺序的，而不是求最短路径等等，如果是求最短路径等需要用到广搜等。  
另外，该题需要输出的是每一步的坐标，故我们的栈里储存的应该是点的坐标，用pair容器存<int,int>类型数据

#include<iostream>
    #include<stack>
    using namespace std;
    
    typedef pair<int,int> PII;//构建坐标类型数据容器
    const int N = 11;
    int maze[N][N],d[N][N];//maze是地图，数组d是用来记录每个点是否已经走过
    int n,flag;//n是地图大小，flag用来判断搜索是否结束
    
    stack<PII> s,ans; 
    void dfs(int xx,int yy)
    {
        
        s.push({
        xx,yy});//将传入的坐标入栈
        d[xx][yy] = 1;//该点状态定义为已走
        if((xx == n-2 && yy == n-2))
        {
        
            //如果已经到达出口
            flag = 1;
            return;
        }
        int dx[] = {
        0,1,0,-1} , dy[] = {
        1,0,-1,0};//定义四个方向
    
            for(int i = 0 ; i < 4 ; i ++)
            {
        
                int x = xx + dx[i], y = yy + dy[i];
                if(x < n &&x >= 0 && y < n && y >=0 && maze[x][y] == 0 && !d[x][y])
                {
        
                    dfs(x,y);
                    if(flag)return;//到达出口后回溯至此时，可以直接结束
                }
            }
        s.pop();//该点不可走时，弹出该点坐标
        
    }
    
    int main()
    {
        
        cin >> n;
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < n; j ++)
                cin >> maze[i][j];//创建迷宫
        //if(maze[1][1] == 0)s.push({1,1});
        dfs(1,1);//从出口开始搜索
    
        //由于最终得到的栈的顺序是从入口至出口的，故需要将栈反转一下
    
        if(!s.size())cout << "NO";//如果最后栈空，表示路径不通
    
        while(s.size())
        {
        
            ans.push({
        s.top().first,s.top().second});
            s.pop();
        }
        while(ans.size())//反转后依次输出即可
        {
        
            cout << '(' << ans.top().first << ',' << ans.top().second << ')';
            ans.pop();
        }
        return 0;
    }

题目来源：拼题A上老师布置的一道题  
欢迎在评论区进行反馈