盛日辉的博客
0%

蓝桥-迷宫2019

发表于 更新于 分类于

题目

https://www.lanqiao.cn/problems/602/learning/

代码1

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
# 01-迷宫2019-2
import sys
from queue import Queue

# 加围墙
mp = []
mp.append([1] * 52)
for _ in range(30):
    mp.append([1] + list(map(int, input())) + [1])
mp.append([1] * 52)
mp[1][1] = 1
path = [["."] * 52 for _ in range(32)]
k = ("D", "L", "R", "U")
dir = ((1, 0), (0, -1), (0, 1), (-1, 0))


def print_path(x, y):
    if x == 1 and y == 1:
        return
    if path[x][y] == "U":
        print_path(x + 1, y)
    if path[x][y] == "D":
        print_path(x - 1, y)
    if path[x][y] == "L":
        print_path(x, y + 1)
    if path[x][y] == "R":
        print_path(x, y - 1)
    print(path[x][y], end="")


q = Queue()
q.put((1, 1))
mp[1][1] = 1
while q:
    x, y = q.get()
    for i in range(4):
        dx, dy = dir[i]
        nx, ny = x + dx, y + dy
        if mp[nx][ny] == 1:
            continue
        mp[nx][ny] = 1
        path[nx][ny] = k[i]
        if nx == 30 and ny == 50:
            print_path(30, 50)
            sys.exit(0)
        q.put((nx, ny))

代码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
# 01-迷宫2019-1
from queue import Queue

mp = []
n, m = 30, 50
for _ in range(n):
    mp.append(input())

vis = [list(map(int, i)) for i in mp]
k = ("D", "L", "R", "U")
dir = ((1, 0), (0, -1), (0, 1), (-1, 0))
q = Queue()
q.put((0, 0, ""))
vis[0][0] = 1
while q:
    x, y, p = q.get()
    # print(x, y, p)
    if x == n - 1 and y == m - 1:
        print(p)
        break
    for i in range(4):
        dx, dy = dir[i]
        nx, ny = x + dx, y + dy
        # print(i, x, y, dx, dy, nx, ny)
        if nx < 0 or ny < 0 or nx >= n or ny >= m or vis[nx][ny] == 1:
            continue
        p_t = p + k[i]
        vis[nx][ny] = 1
        q.put((nx, ny, p_t))
        # print(nx, ny, p)