Submission #64537128

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
h, w = map(int, input().split())
from heapq import *
q = []
s = [input() for _ in range(h)]
a, b, c, d = map(lambda x: int(x) - 1, input().split())
dxy = [0, 1, 0, -1, 0]
inf = 1 << 60
ans = [[inf] * w for _ in range(h)]
heappush(q, (0, a, b))
while q:
    cost, y, x = heappop(q)
    for i in range(4):
        ny, nx = y + dxy[i], x + dxy[i + 1]
        if 0 <= ny < h and 0 <= nx < w:
            if s[ny][nx] == "." and ans[ny][nx] > cost:
                heappush(q, (cost, ny, nx))
                ans[ny][nx] = cost
            elif s[ny][nx] == "#" and ans[ny][nx] >= cost + 1:
                heappush(q, (cost + 1, ny, nx))
                ans[ny][nx] = cost + 1
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

h, w = map(int, input().split())
from heapq import *

q = []
s = [input() for _ in range(h)]
a, b, c, d = map(lambda x: int(x) - 1, input().split())
dxy = [0, 1, 0, -1, 0]
inf = 1 << 60
ans = [[inf] * w for _ in range(h)]
heappush(q, (0, a, b))
while q:
    cost, y, x = heappop(q)
    for i in range(4):
        ny, nx = y + dxy[i], x + dxy[i + 1]
        if 0 <= ny < h and 0 <= nx < w:
            if s[ny][nx] == "." and ans[ny][nx] > cost:
                heappush(q, (cost, ny, nx))
                ans[ny][nx] = cost
            elif s[ny][nx] == "#" and ans[ny][nx] >= cost + 1:
                heappush(q, (cost + 1, ny, nx))
                ans[ny][nx] = cost + 1
                nny, nnx = ny + dxy[i], nx + dxy[i + 1]
                if 0 <= nny < h and 0 <= nnx < w:
                    heappush(q, (cost + 1, nny, nnx))
                    ans[nny][nnx] = cost + 1
print(ans[c][d])

#print(ans[c])

Submission Info

Judge Result