[数据结构与算法]求解迷宫从入口到出口的路径【算法】【栈】【深度优先搜索】

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

创建一个迷宫，求从入口通向出口的可行路径。
为简化问题，迷宫用二维数组 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上老师布置的一道题
欢迎在评论区进行反馈