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
|
with open('maze.txt') as f:
maze = f.readlines()
maze_list =[]
for i in maze:
temp = []
temp.extend(i.strip('\n'))
maze_list.append(temp)
minn = 9999
ans = ''
visited = [[0 for _ in range(50)] for _ in range(50)] #是否访问过
direction = [[1, 0], [0, -1], [0, 1], [-1, 0]]
dp = [[9999 for _ in range(50)] for _ in range(50)] #保存每一步的当前路数
vv = [0 for _ in range(1000)]
s = ['D', 'D', 'L', 'R', 'U']
def dfs(x, y, steps):
global minn, ans
if steps > minn:return
if x == 29 and y == 49:
if steps < minn:
minn = steps
tmp = ''
for i in range(1, steps):
tmp += s[vv[i]]
ans = tmp
return
for i in range(1, 5):
tx = x + direction[i-1][0]
ty = y + direction[i-1][1]
if tx < 0 or ty < 0 or tx > 29 or ty >49: #越界判断
continue
if visited[tx][ty] or maze_list[tx][ty] == '1':
continue
if steps + 1 > dp[tx][ty]:
return
dp[tx][ty] = steps + 1
visited[tx][ty] = 1
vv[steps] = i
dfs(tx, ty, steps + 1)
visited[tx][ty] = 0
dfs(0, 0, 1)
print(ans)
|