Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from queue import Queue
- n, m = input().split()
- n = int(n)
- m = int(m)
- x1, y1 = input().split()
- x1 = int(x1)
- y1 = int(y1)
- x2, y2 = input().split()
- x2 = int(x2)
- y2 = int(y2)
- g = [0] * (n * m)
- for i in range (n * m):
- g[i] = []
- for i in range(n * m):
- g[i] = []
- pole = [0] * n
- for i in range(n):
- pole[i] = input()
- for i in range(n):
- for j in range(m):
- if (i + 1 < n and pole[i + 1][j] != 'X'):
- g[i * m + j].append((i + 1) * m + j)
- if (i - 1 > -1 and pole[i - 1][j] != 'X'):
- g[i * m + j].append((i - 1) * m + j)
- if (j + 1 < m and pole[i][j + 1] != 'X'):
- g[i * m + j].append(i * m + j + 1)
- if (j - 1 > -1 and pole[i][j - 1] != 'X'):
- g[i * m + j].append(i * m + j - 1)
- #print(i * m + j, g[i * m + j])
- used = [0] * (n * m)
- d = [-1] * (n * m)
- q = Queue()
- q.put(x1 * m + y1)
- used[x1 * m + y1] = 1
- while (not q.empty()):
- v = q.get()
- for i in range(len(g[v])):
- to = g[v][i]
- if (used[to] == 0):
- used[to] = 1
- q.put(to)
- d[to] = d[v] + 1
- if (d[x2 * m + y2] == -1):
- print("INF")
- else:
- print(d[x2 * m + y2] + 1)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement