Submission #64537711

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 collections import deque
q = deque()
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)]
q.append((a, b, 0))
while q:
    y, x, cost = q.popleft()
    #print(y, x, cost)
    if y == c and x == d:
        exit(print(cost))
    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:
                q.appendleft((ny, nx, cost))
                ans[ny][nx] = cost
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

h, w = map(int, input().split())
from collections import deque

q = deque()
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)]
q.append((a, b, 0))
while q:
    y, x, cost = q.popleft()
    #print(y, x, cost)
    if y == c and x == d:
        exit(print(cost))
    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:
                q.appendleft((ny, nx, cost))
                ans[ny][nx] = cost
            elif s[ny][nx] == "#" and ans[ny][nx] >= cost + 1:
                q.append((ny, nx, cost + 1))
                # print(y, x, cost)
                ans[ny][nx] = cost + 1
                nny, nnx = ny + dxy[i], nx + dxy[i + 1]
                if 0 <= nny < h and 0 <= nnx < w and ans[nny][nnx] > cost + 1:
                    q.append((nny, nnx, cost + 1))
                    ans[nny][nnx] = cost + 1

Submission Info

Judge Result