VOJ 走迷宫 题解 DFS

走迷宫

题目描述

给一个 n 行 m 列的 2 维的迷宫，‘S’表示迷宫的起点，‘T’表示迷宫的终点，’#‘表示不能通过的点，’.’ 表示可以通过的点。你需要从’S’出发走到’T’，每次只能上下左右走动，并且只能进入能通过的点，每个点只能通过一次。现在要求你求出有多少种通过迷宫的的方案。

输入描述

第一行输入 n, m (1≤n,m≤10) 表示迷宫大小。
接下来输入 n 行字符串表示迷宫。

输出描述

输入通过迷宫的方案数。

样例 1

样例输入 1

2 3
S.#
..T
1
2
3

样例输出 1

2
1

样例 2

样例输入 2

3 3
S..
.#.
..T
1
2
3
4

样例输出 2

2
1

思路

预处理迷宫的边界为不能通过的点，用vis[ ]数组记录是否访问过某点，然后从起点开始进行深度优先搜索，每递归到终点方案数就加1。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char a[12][12];
bool vis[12][12]; // 是否走过该点
int n, m;         // 迷宫大小
// 四个方向
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
// 统计方案数
int ans = 0;
// 深搜
void dfs(int x, int y) // x,y为当前节点的坐标
{
    if (a[x][y] == 'T') // 走到终点，方案数++
    {
        ans++;
        return;
    }
    for (int i = 0; i < 4; i++) // 以当前点向四个方向搜索
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (vis[nx][ny] == 0 && a[nx][ny] != '#') // 没有访问过并且可以通过
        {
            vis[nx][ny] = 1;
            dfs(nx, ny);     // 递归
            vis[nx][ny] = 0; // 回溯
        }
    }
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    int sx, sy;                // 起点坐标
    memset(a, '#', sizeof(a)); // 将迷宫的边界预处理为不能通过的点
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            if (a[i][j] == 'S') // 记录起点坐标
            {
                sx = i;
                sy = j;
            }
        }
    }
    vis[sx][sy] = 1; // 起点已访问
    dfs(sx, sy);
    cout << ans << '\n';
    return 0;
}
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
57