Neaya~

笔记、记录、总结

深搜dfs求解迷宫问题

发表于 更新于 分类于 评论数：
本文字数： 2.5k 阅读时长 ≈ 2 分钟

摘要：dfs求解迷宫问题

深搜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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
"""
# @Time    :  2020/10/5
# @Author  :  Jimou Chen
"""
# 迷宫二维列表 n行m列 ：[[0 for i in range(m)] for j in range(n)]
# 假设1 是空地，2 是障碍物
a = [[0 for i in range(10)] for j in range(10)]
# 标志是否访问, 0是未访问，1是已经访问
flag = [[0 for i in range(10)] for j in range(10)]
# 目标坐标
# p, q = 0, 0
# 设最短路径长度
min_dis = 99999999


def dfs(x, y, step):
    if x == p and y == q:
        global min_dis
        if step < min_dis:
            min_dis = step
        # 回退
        return

    '''顺时针试探'''
    # 右边
    if a[x][y + 1] == 1 and flag[x][y + 1] == 0:
        flag[x][y + 1] = 1
        dfs(x, y + 1, step + 1)
        flag[x][y + 1] = 0
    # 下
    if a[x + 1][y] == 1 and flag[x + 1][y] == 0:
        flag[x + 1][y] = 1
        dfs(x + 1, y, step + 1)
        flag[x + 1][y] = 0
    # 左
    if a[x][y - 1] == 1 and flag[x][y - 1] == 0:
        flag[x][y - 1] = 1
        dfs(x, y - 1, step + 1)
        flag[x][y - 1] = 0
    # 上
    if a[x - 1][y] == 1 and flag[x - 1][y] == 0:
        flag[x - 1][y] = 1
        dfs(x - 1, y, step + 1)
        flag[x - 1][y] = 0

    return


if __name__ == '__main__':
    # 输入m行n列
    m, n = map(int, input().split())
    # 给地图赋值,空地、障碍物
    for i in range(0, m):
        temp = list(map(int, input().split()))
        for j in range(0, n):
            # a[i][j] = int(input())
            a[i][j] = temp[j]

    # 输入起点和终点坐标
    start_x, start_y = map(int, input().split())
    # global p, q
    p, q = map(int, input().split())

    # 从起点开始，所以起点设置为已经访问状态
    flag[start_x][start_y] = 1
    dfs(start_x, start_y, 0)

    print(min_dis)

'''
5 4
1 1 2 1
1 1 1 1
1 1 2 1
1 2 1 1
1 1 1 2
0 0
3 2
'''

优化后的模板

  • 添加方向数组
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
58
59
60
61
62
63
64
65
66
67
68
69
"""
# @Time    :  2020/10/5
# @Author  :  Jimou Chen
"""
# 迷宫二维列表 n行m列 ：[[0 for i in range(m)] for j in range(n)]
# 假设1 是空地，2 是障碍物
a = [[0 for i in range(100)] for j in range(100)]
# 标志是否访问, 0是未访问，1是已经访问
flag = [[0 for i in range(100)] for j in range(100)]
# 方向数组
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

# 设最短路径长度
min_dis = 99999999


def dfs(x, y, step):
    if x == p and y == q:
        global min_dis
        if step < min_dis:
            min_dis = step
        # 回退
        return

    '''顺时针试探'''
    for i in range(0, 4):
        tx = x + dx[i]
        ty = y + dy[i]
        if a[tx][ty] == 1 and flag[tx][ty] == 0:
            flag[tx][ty] = 1
            dfs(tx, ty, step + 1)
            flag[tx][ty] = 0

    return


if __name__ == '__main__':
    # 输入m行n列
    m, n = map(int, input().split())
    # 给地图赋值,空地、障碍物
    for i in range(0, m):
        temp = list(map(int, input().split()))
        for j in range(0, n):
            # a[i][j] = int(input())
            a[i][j] = temp[j]

    # 输入起点和终点坐标
    start_x, start_y = map(int, input().split())
    # global p, q
    p, q = map(int, input().split())

    # 从起点开始，所以起点设置为已经访问状态
    flag[start_x][start_y] = 1
    dfs(start_x, start_y, 0)

    print(min_dis)

'''
5 4
1 1 2 1
1 1 1 1
1 1 2 1
1 2 1 1
1 1 1 2
0 0
3 2
'''

1
2
3
4
5
6
7
8
9
10
11
5 4
1 1 2 1
1 1 1 1
1 1 2 1
1 2 1 1
1 1 1 2
0 0
3 2
7

Process finished with exit code 0
Welcome to reward