Advertisement
EleonoraWhite

Untitled

May 2nd, 2019
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.22 KB | None | 0 0
  1. from queue import Queue
  2.  
  3. n, m = input().split()
  4. n = int(n)
  5. m = int(m)
  6.  
  7. x1, y1 = input().split()
  8. x1 = int(x1)
  9. y1 = int(y1)
  10. x2, y2 = input().split()
  11. x2 = int(x2)
  12. y2 = int(y2)
  13.  
  14. g = [0] * (n * m)
  15.  
  16. for i in range (n * m):
  17. g[i] = []
  18.  
  19. for i in range(n * m):
  20. g[i] = []
  21.  
  22. pole = [0] * n
  23.  
  24. for i in range(n):
  25. pole[i] = input()
  26.  
  27. for i in range(n):
  28. for j in range(m):
  29. if (i + 1 < n and pole[i + 1][j] != 'X'):
  30. g[i * m + j].append((i + 1) * m + j)
  31. if (i - 1 > -1 and pole[i - 1][j] != 'X'):
  32. g[i * m + j].append((i - 1) * m + j)
  33. if (j + 1 < m and pole[i][j + 1] != 'X'):
  34. g[i * m + j].append(i * m + j + 1)
  35. if (j - 1 > -1 and pole[i][j - 1] != 'X'):
  36. g[i * m + j].append(i * m + j - 1)
  37. #print(i * m + j, g[i * m + j])
  38.  
  39. used = [0] * (n * m)
  40. d = [-1] * (n * m)
  41. q = Queue()
  42. q.put(x1 * m + y1)
  43. used[x1 * m + y1] = 1
  44.  
  45. while (not q.empty()):
  46. v = q.get()
  47.  
  48. for i in range(len(g[v])):
  49. to = g[v][i]
  50. if (used[to] == 0):
  51. used[to] = 1
  52. q.put(to)
  53. d[to] = d[v] + 1
  54.  
  55. if (d[x2 * m + y2] == -1):
  56. print("INF")
  57. else:
  58. print(d[x2 * m + y2] + 1)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement