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

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
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)
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