走迷宫

题目描述

有一个 m×nm\times n 格的迷宫(表示有 mm 行、nn 列)，其中有可走的也有不可走的，如果用 11 表示可以走，00 表示不可以走，文件读入这 m×nm\times n 个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息（用 −1-1 表示无路）。

优先顺序：左上右下。数据保证随机生成。

输入格式

第一行是两个数 m,n(1<m,n<15)m,n(1<m,n<15)，接下来是 mm 行 nn 列由 11 和 00 组成的数据，最后两行是起始点和结束点。

输出格式

所有可行的路径，描述一个点时用 (x,y)(x,y) 的形式，除开始点外，其他的都要用 -> 表示方向。

如果没有一条可行的路则输出 −1-1。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
5 6
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
1 1
5 6

样例输出 #1

1
2
3
4
5
6
7
8
9
10
11
12
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)

提示

数据保证随机生成。事实上，如果 n=m=14n=m=14 且每个位置都是 11 的话，有 6945066476152136166427470154890735899648869450664761521361664274701548907358996488 种路径。

思路

这是一道经典的走迷宫，要求我们输出的是路径，走迷宫用DFS四按照题目要求的四个方向左上右下走就可以，那么输出路径我们可以把一个点的路径存储到结构体，再存到栈中。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int m, n;                                            // m*n 大小的迷宫
int sx, sy, zx, zy;                                  // 起点的x和y的坐标，和终点的x和y的坐标
bool mg[20][20];                                     // 存迷宫,1表示可以走，0不能走
bool vis[20][20];                                    // 是否访问
int walk[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}}; // 走的方向，左上右下
int cnt;                                             // 一开始得90，然后突然想起来没路径要输出-1 。。。。
struct node
{
    int x, y;
}; // 存路径
vector<node> road;       // 栈
bool in_mg(int x, int y) // 是否在迷宫内，还有是否没有被访问过
{
    return x >= 1 && x <= m && y >= 1 && y <= n && mg[x][y] && !vis[x][y];
}
void dfs(int x, int y)
{
    vis[x][y] = 1;          // 标记，访问过了
    road.push_back({x, y}); // 栈顶加入一个元素，记录当当前坐标x和y值
    if (x == zx && y == zy) // 到终点了
    {
        cnt++;
        for (int i = 0; i < road.size() - 1; i++) // 最后一个点的坐标先不输出
        {
            cout << "(" << road[i].x << "," << road[i].y << ")->";
        }
        cout << "(" << zx << "," << zy << ")" << endl;
        return; // 走到终点就返回
    }
    for (int i = 0; i < 4; i++) // 朝四个方向走
    {
        int new_x = x + walk[i][0]; // 下一个点的x坐标
        int new_y = y + walk[i][1]; // 下一个点的y坐标
        if (in_mg(new_x, new_y))    // 判断，下一个点可以走
        {
            dfs(new_x, new_y);     // 走
            vis[new_x][new_y] = 0; // 回溯时标记为没走
            road.pop_back();       // 删除栈顶数据
        }
    }
}
int main()
{
    cin >> m >> n; // m*n大小的迷宫
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> mg[i][j];     // 读入迷宫
    cin >> sx >> sy >> zx >> zy; // 起点和终点
    dfs(sx, sy);                 // DFS
    if (!cnt)                    //! cnt就是cnt==0
        cout << -1;
    return 0;
}