boris-vlasenko

Поиск пути, волновой алгоритм

Dec 5th, 2021
617
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def wave(r, c):
  2.     q = [(r, c)]
  3.     number = 1
  4.     while q:
  5.         new_q = []
  6.         for r, c in q:
  7.             m[r][c] = number
  8.             for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
  9.                 rr = r + dr
  10.                 cc = c + dc
  11.                 if 0 <= rr < nr and 0 <= cc < nc:
  12.                     if a[rr][cc] != 'X' and m[rr][cc] == 0:
  13.                         new_q.append((rr, cc))
  14.         number += 1
  15.         q = new_q
  16.  
  17.  
  18. def get_path(r, c):
  19.     while m[r][c] > 1:
  20.         next_res = None
  21.         for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
  22.             rr = r + dr
  23.             cc = c + dc
  24.             if 0 <= rr < nr and 0 <= cc < nc:
  25.                 if m[rr][cc] != 0:
  26.                     if next_res is None or m[rr][cc] < next_res:
  27.                         next_res = m[rr][cc]
  28.                         next_r = rr
  29.                         next_c = cc
  30.         a[next_r][next_c] = '*'
  31.         r, c = next_r, next_c
  32.  
  33.  
  34. f = open('input.txt')
  35. a = []
  36. r = 0
  37. for line in f.readlines():
  38.     a.append(list(line.strip()))
  39.     if 's' in line:
  40.         start = (r, line.find('s'))
  41.     if 'f' in line:
  42.         finish = (r, line.find('f'))
  43.     r += 1
  44. f.close()
  45.  
  46. nc = len(a[0])
  47. nr = len(a)
  48. m = [[0 for c in range(nc)] for r in range(nr)]
  49.  
  50. wave(*start)
  51. get_path(*finish)
  52. r, c = finish
  53. res = m[r][c] - 1
  54. if res > 0:
  55.     print(res)
  56. else:
  57.     print('Пути нет')
  58. r, c = start
  59. a[r][c] = 's'
  60.  
  61. for r in range(nr):
  62.     for c in range(nc):
  63.         print(a[r][c], end='')
  64.     f.write()
  65.  
RAW Paste Data