 # Untitled

Jul 7th, 2021
705
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. rows = int(input())
2. maze, visited, exits, path, ans = [], [], [], [], []
3. start_r, start_c = -1, -1
4.
5. for row in range(rows):
6.     maze.append([])
7.     visited.append([])
8.     line = input()
9.     for col in range(len(line)):
10.         maze[row].append(line[col] == ' ')
11.         visited[row].append(0)
12.         if line[col] == 'k':
13.             start_r, start_c = row, col
14.             maze[row][col] = True
15.         if line[col] == ' ' and ((row == 0 or row == rows - 1) or (col == 0 or col == len(line) - 1)):
16.             exits.append([row, col])
17.
18.
19. # Source https://stackoverflow.com/a/60957101
20. def traverse(r: int, c: int):
21.     # if it is a wall ot it was visited, do nothing
22.     if not maze[r][c] or visited[r][c]:
23.         return
24.     # mark the index as visited
25.     visited[r][c] = 1
26.     # add index to the path
27.     path.append((r, c))
28.     # if the exit is reached, store the path
29.     # and pop th last index to traverse other paths
30.     if [r, c] in exits:
31.         # any path that reached exit are appended here
32.         ans.append(list(path))
33.         path.pop()
34.         return
35.     # loop on the neighbours. if they are valid indices, do same
36.     for k in range(4):
37.         nwr = r + [-1, 1, 0, 0][k]
38.         nwc = c + [0, 0, 1, -1][k]
39.         if 0 <= nwr < len(maze) and 0 <= nwc < len(maze[nwr]):
40.             traverse(nwr, nwc)
41.     # after finishing this index, just pop because we do not need it any more
42.     path.pop()
43.     return
44.
45.
46. traverse(start_r, start_c)
47.
48. if len(ans) == 0:
49.     # fix for when Kate is already on the exit
50.     if start_c == 0 or start_c == len(maze) - 1 or start_r == 0 or start_r == len(maze) - 1:
51.         print('Kate got out in 1 moves')
52.     else:
53.         print('Kate cannot get out')
54. else:
55.     print(f"Kate got out in {min([len(p) for p in ans])} moves")
RAW Paste Data