蓝桥杯刷题-迷宫_4*4迷宫问题

蓝桥杯-迷宫

DAY ONE

写在前面的话：这次报名的是python组，python的语法有些遗忘，通过做题把python的语法捡一捡，同时把这学期学得数据结构运用到实际中做题中

题目如下

X 星球的一处迷宫游乐场建在某个小山坡上。它是由 10 ×10 相互连通的小房间组成的。

房间的地板上写着一个很大的字母。我们假设玩家是面朝上坡的方向站立，则：

• L 表示走到左边的房间，
• R 表示走到右边的房间，
• U 表示走到上坡方向的房间，
• D 表示走到下坡方向的房间。

X 星球的居民有点懒，不愿意费力思考。他们更喜欢玩运气类的游戏。这个游戏也是如此！

开始的时候，直升机把 100名玩家放入一个个小房间内。玩家一定要按照地上的字母移动。

迷宫地图如下：

UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR

请你计算一下，最后，有多少玩家会走出迷宫，而不是在里边兜圈子？

如果你还没明白游戏规则，可以参看下面一个简化的 4x4 迷宫的解说图：

分析

1、填空题，没有什么运行时间和运行内存的限制

2、可以采取暴力遍历法，把从每个点出发的路径遍历一遍，设置一个count，满足条件就加一

3、深度遍历，递归调用

具体实现

遇到的问题

1、如何初始化地图

用列表加字符串的形式

L = ['' for i in range(10)]#列表推导式
#L = [''] * 10 同样能达到相同的效果
L[0] = "UDDLUULRUL"
L[1] = "UURLLLRRRU"
L[2] = "RRUURLDLRD"
L[3] = "RUDDDDUUUU"
L[4] = "URUDLLRRUU"
L[5] = "DURLRLDLRL"
L[6] = "ULLURLLRDU"
L[7] = "RDLULLRDDD"
L[8] = "UUDDUDUDLL"
L[9] = "ULRDLUURRR"
1
2
3
4
5
6
7
8
9
10
11
12

2、遍历过程的主要部分（递归实现）

def dfs(x, y):
    global count  #这里因为在函数外定义了count，在global
    if (visited[x][y] == 1):#设置的二维数组，一旦访问，将值置为一，判断条件成立，说明回到已经访问的点，结束递归
        return
    if (x < 0 or y < 0 or x >= 10 or y >= 10):
        count += 1
        return
    #满足条件，计数加一，递归结束
    
    
    #python里没有switch语句，用if语句代替
    #移动过程中，递归的参数x，y很容易弄混，注意区分
    #visited二维数组要比地图大一个格子，否则第一个if语句会报错
    if (L[x][y] == "L"):
        visited[x][y] = 1
        dfs(x, y - 1)
        visited[x][y] = 0
    elif (L[x][y] == "R"):
        visited[x][y] = 1
        dfs(x, y + 1)
        visited[x][y] = 0
    elif (L[x][y] == "U"):
        visited[x][y] = 1
        dfs(x - 1, y )
        visited[x][y] = 0
    else:
        visited[x][y] = 1
        dfs(x + 1, y)
        visited[x][y] = 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

附完整代码：

L = ['' for i in range(10)]
L[0] = "UDDLUULRUL"
L[1] = "UURLLLRRRU"
L[2] = "RRUURLDLRD"
L[3] = "RUDDDDUUUU"
L[4] = "URUDLLRRUU"
L[5] = "DURLRLDLRL"
L[6] = "ULLURLLRDU"
L[7] = "RDLULLRDDD"
L[8] = "UUDDUDUDLL"
L[9] = "ULRDLUURRR"
for i in range(10):
    for j in range(10):
        print(L[i][j],end='')
    print()
# print (L)
visited = [[0 for i in range(11)] for i in range(11)]
for i in range(11):
    for j in range(11):
        print(visited[i][j],end='')
    print()
print(L[2][4])
count = 0
def dfs(x, y):
    global count
    if (visited[x][y] == 1):
        return
    if (x < 0 or y < 0 or x >= 10 or y >= 10):
        count += 1
        return
    if (L[x][y] == "L"):
        visited[x][y] = 1
        dfs(x, y - 1)
        visited[x][y] = 0
    elif (L[x][y] == "R"):
        visited[x][y] = 1
        dfs(x, y + 1)
        visited[x][y] = 0
    elif (L[x][y] == "U"):
        visited[x][y] = 1
        dfs(x - 1, y )
        visited[x][y] = 0
    else:
        visited[x][y] = 1
        dfs(x + 1, y)
        visited[x][y] = 0


def test():
    for i in range(10):
        for j in range(10):
            dfs(i, j)


if __name__ == "__main__":
    test()
    print(count)

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