Advertisement
K_Y_M_bl_C

Untitled

Apr 19th, 2018
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.91 KB | None | 0 0
  1. head = 0
  2. q = []
  3.  
  4. def isempty():
  5.     return head == len(q)
  6.  
  7. def push(val):
  8.     q.append(val)
  9.  
  10. def pop():
  11.     global head
  12.     head += 1
  13.  
  14. def front():
  15.     return q[head]
  16.  
  17. n, m = map(int, input().split())
  18.  
  19. s = list(map(int, input().split()))
  20. t = list(map(int, input().split()))
  21.  
  22. g = []
  23.  
  24. for i in range(n):
  25.     g.append(str(input()))
  26.  
  27. d = []
  28.  
  29. for i in range(n):
  30.     d.append([])
  31.     for j in range(m):
  32.         d[i].append(-1)
  33.  
  34. dx = [0, -1, 0, 1]
  35. dy = [-1, 0, 1, 0]
  36.  
  37. d[s[0]][s[1]] = 0
  38. push(s)
  39.  
  40. def check(x, y):
  41.     return 0 <= x and x < n and 0 <= y and y < m and g[x][y] != 'X'
  42.  
  43. if (not check(s[0], s[1])):
  44.     print('INF')
  45.     exit()
  46.  
  47. if (not check(t[0], t[1])):
  48.     print('INF')
  49.     exit()
  50.  
  51. ans = []
  52.  
  53. while (not isempty()):
  54.     u = front()
  55.     x = u[0]
  56.     y = u[1]
  57.     pop()
  58.     for i in range(4):
  59.         nx = x + dx[i]
  60.         ny = y + dy[i]
  61.         if (check(nx, ny)):
  62.             if (d[nx][ny] == -1):
  63.                 d[nx][ny] = d[x][y] + 1
  64.                 push((nx, ny))
  65.  
  66. if (d[t[0]][t[1]] == -1):
  67.     print('INF')
  68.     exit()
  69.  
  70. print(d[t[0]][t[1]])
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement