kostovhg

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[0]) - 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