Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    c = [input().rstrip() for _ in range(h)]
    cw -= 1
    ch -= 1
    dw -= 1
    dh -= 1
    c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
    d1 = deque([[cw, ch]])
    d2 = deque([])

    for cnt in range(30000):
        for _ in range(50000):
            for _ in range(len(d1)):
                now_x, now_y = d1.popleft()
                for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                    x, y = now_x + next_x, now_y + next_y
                    if 0 <= x < w and 0 <= y < h:
                        if x == dw and y == dh:
                            print(cnt)
                            exit()
                        c_next = c[y][x]
                        c_now = c[now_y][now_x]
                        if c_now != "-" and c_next == "#":  # 今いるマスの周り5*5マスワープ不可判定走査開始
                            for next_y in range(-2, 3):
                                for next_x in range(-2, 3):
                                    x, y = now_x + next_x, now_y + next_y
                                    if 0 <= x < w and 0 <= y < h:
                                        if c[y][x] == ".":
                                            c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                                            d2.append([x, y])
                            else:  # 今いるマスに5*5マスワープ不可判定走査済マーク
                                x, y = now_x, now_y
                                c[y] = c[y][:x] + "-" + c[y][x + 1 :]
                        elif c_next == ".":  # 走査済マーク
                            c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                            d1.append([x, y])
        else:
            if [dw, dh] in d2:
                print(cnt + 1)
                exit()
            if not d2:
                print(-1)
                exit()
            while d2:
                x, y = d2.pop()
                if c[y][x] == "!":
                    d1.append([x, y])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    c = [input().rstrip() for _ in range(h)]
    cw -= 1
    ch -= 1
    dw -= 1
    dh -= 1
    c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
    d1 = deque([[cw, ch]])
    d2 = deque([])

    for cnt in range(30000):
        for _ in range(70000):
            for _ in range(len(d1)):
                now_x, now_y = d1.popleft()
                for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                    x, y = now_x + next_x, now_y + next_y
                    if 0 <= x < w and 0 <= y < h:
                        if x == dw and y == dh:
                            print(cnt)
                            exit()
                        c_next = c[y][x]
                        c_now = c[now_y][now_x]
                        if c_now != "-" and c_next == "#":  # 今いるマスの周り5*5マスワープ不可判定走査開始
                            for next_y in range(-2, 3):
                                for next_x in range(-2, 3):
                                    x, y = now_x + next_x, now_y + next_y
                                    if 0 <= x < w and 0 <= y < h:
                                        if c[y][x] == ".":
                                            c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                                            d2.append([x, y])
                            else:  # 今いるマスに5*5マスワープ不可判定走査済マーク
                                x, y = now_x, now_y
                                c[y] = c[y][:x] + "-" + c[y][x + 1 :]
                        elif c_next == ".":  # 走査済マーク
                            c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                            d1.append([x, y])
        else:
            if [dw, dh] in d2:
                print(cnt + 1)
                exit()
            if not d2:
                print(-1)
                exit()
            d1 = d2.copy()
            d2.clear()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
## dijkstraで解く
import heapq

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = [input() for i in range(H)]

INF = 1 << 10
N = 10**4
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = []
heapq.heapify(q)
heapq.heappush(q,(0, (ch-1)*N+(cw-1)))
while q:
    cnt, n  = heapq.heappop(q)
    h,w = divmod(n, N)
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    # 歩いた
    for dh in range(-2,3):
        for dw in range(-2,3):            
            hn = h + dh
            wn = w + dw
            if not 0 <= wn < W: continue
            if not 0 <= hn < H: continue
            if fs[hn][wn] == "#": continue
            if abs(dh) + abs(dw) <= 1:
                if dps[hn][wn] <= cnt:continue
                heapq.heappush(q, (cnt, hn*N+wn))
            else:
                if dps[hn][wn] <= cnt + 1: continue
                heapq.heappush(q, (cnt+1, hn*N+wn))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()


# 迷路読み込み
H,W = map(int, input().split())
c1,c2= map(int, input().split())
d1,d2= map(int, input().split())
A=[list(input()) for i in range(H)]
edges = [[] for i in range(H * W)]
print(A)

for i in range(H):
    for j in range(W):
        for di in range(-2,3):
            for dj in range(-2, 3):
                ni, nj = i + di, j + dj
                if 0 <= ni < H and 0 <= nj < W and A[i][j]!='#' and A[ni][nj]!='#':
                    if di==0 and dj==0:
                        continue
                    elif (di==0 and dj==1) or (di==1 and dj==0) or (di==-1 and dj==0) or (di==0 and dj==-1):
                        edges[i * W + j].append((ni * W + nj,0))
                    else:
                        edges[i * W + j].append((ni * W + nj,1))


#ダイクストラ法
from heapq import heappush, heappop

def dijkstra(edges, size, source):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    INF=pow(10,9)
    distance = [INF] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance[g]

s=(c1-1)*W+c2-1
g=(d1-1)*W+d2-1
ans=dijkstra(edges,H*W,s)
if ans==pow(10,9):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

INF = 10**12

H, W = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3)
        for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
maze = []

for _ in range(H):
    maze.append(list(input()))

q = deque()
d = [[INF] * W for i in range(H)]
d[sx][sy] = 0
q.append((sx, sy, 0))

while q:
    x, y, s = q.pop()
    if x == gx and y == gy:
        break
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and d[nx][ny] > s:
            d[nx][ny] = s
            q.append((nx, ny, s))
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and d[nx][ny] > s+1:
            d[nx][ny] = s + 1
            q.append((nx, ny, s+1))

if d[gx][gy] == INF:
    print(-1)
else:
    print(d[gx][gy])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#import heapq
from collections import deque

H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

S = []
for _ in range(H):
  S.append(list(input()))
  
dpat = ((-1,0),(1,0),(0,-1),(0,1))
mpat = []
for i in range(-2,3):
  for j in range(-2,3):
    if (i,j) in dpat:
      continue
    if i == j and j == 0:
      continue
    mpat.append((i,j))
                
#print(mpat)

#BFS
visited = [[False] * W for _ in range(H)]
willSearch = [[False] * W for _ in range(H)]
Q = deque()
QN = deque()
Q.append((0,Ch,Cw))
QN.append((0,Ch,Cw))
while Q:
  while Q:
    c,x,y = Q.popleft()
    if visited[x][y]:
      continue
    visited[x][y] = True
    QN.append((c,x,y))
    print(c,x,y)
    if x == Dh and y == Dw:
      print(c)
      exit(0)
    for dx,dy in dpat:
      nx,ny = x+dx, y+dy
      if 0<=nx<H and 0<=ny<W:
        if S[nx][ny] == "#":
          continue
        if visited[nx][ny]:
          continue
        Q.append((c,nx,ny))
        QN.append((c,nx,ny))
        willSearch[nx][ny] = True
  while QN:
    c,x,y = QN.popleft()
    for dx,dy in mpat:
      nx,ny = x+dx, y+dy
      if 0<=nx<H and 0<=ny<W:
        if S[nx][ny] == "#":
          continue
        if visited[nx][ny]:
          continue
        Q.append((c+1,nx,ny))
        print("m", c+1, nx,ny)
        #willSearch[nx][ny] = True
      
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    dh, dw = map(int, input().split())
    dh -= 1
    dw -= 1
    maze = [input() for i in range(h)]
    visited = [[-1]*w for j in range(h)]
    mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    ans = -1
    visited = [[-1]*w for j in range(h)]
    q = deque([[ch, cw]])
    visited[ch][cw] = 0 
    while q:
        y, x = q.popleft()
        if y == dh and x == dw:
            ans = visited[y][x]
            break
        for i, j in mv:
            if (0 <= y + i < h) and (0 <= x + j < w):  
                ny = y+i
                nx = x+j
                if visited[ny][nx] != -1:
                    continue
                if maze[ny][nx] == '.':
                    visited[ny][nx] = visited[y][x] + 1 
                    q.append([ny, nx])
            else:
                continue
    if ans != -1:
        print(0)
        exit()
    else:
        cnt = 1
        n_yx_s = [[]]
        while len(n_yx_s) > 0:
            n_yx = list()
            for y in range(h):
                for x in range(w):
                    if visited[y][x] != -1:
                        for ny in range(-2, 3):
                            for nx in range(-2, 3):
                                if 0 < y+ny < h and \
                                    0 < x+nx < w and \
                                    visited[y+ny][x+nx] == -1 and \
                                    maze[y+ny][x+nx] != '#': 
                                    n_yx.append([y+ny, x+nx])
                                    visited[y+ny][x+nx] += 1
            n_yx_s = set(map(tuple, n_yx))
            if (dh, dw) in n_yx_s:
                print(cnt)
                exit()
            else:
                cnt += 1
        print(-1)
                        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
## dijkstraで解く

from collections import deque
import heapq

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)

walks = [(-1,0),(1,0),(0,1),(0,-1)]
magics = []
for i in range(-2,3):
    for j in range(-2,3):
        if i==j==0:continue
        if (i,j) not in walks:
            magics.append((i,j))

INF = 1 << 50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = []
heapq.heappush(q,(0, (ch-1)*INF+(cw-1)))
while len(q)>0:
    cnt, n  = heapq.heappop(q)
    h,w = divmod(n, INF)
    if dps[h][w] != INF:continue
    dps[h][w] = cnt
    # 歩いた
    for dh, dw in walks:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                heapq.heappush(q, (cnt, hn*INF+wn))
    # 魔法
    for dh, dw in magics:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                heapq.heappush(q, (cnt+1, hn*INF+wn))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)

Submission status: Wrong Answer

Solution code:

from collections import deque
def resolve():
    drc4 = {(-1, 0), (0, 1), (1, 0), (0, -1)}

    def bfs(start, goal):
        sy, sx = start
        gy, gx = goal
        q = deque()
        q.append(start)
        ans[sy][sx] = 0

        while q:
            sy, sx = q.popleft()
            # if sy == gy and sx == gx:
            #     return print(ans[gy][gx])
            for dy, dx in drc4:
                ny, nx = dy + sy, dx + sx
                # if G[ny][nx] == "@" or ans[ny][nx] != INF:
                #     if G[ny][nx] != "#":
                #         continue
                if G[ny][nx] == "." and ans[ny][nx] > ans[sy][sx]:
                    ans[ny][nx] = ans[sy][sx]
                    q.append((ny, nx))

            for dy8 in range(-2, 3):
                for dx8 in range(-2, 3):
                    if (dy8, dx) in drc4:
                        continue
                    ny8, nx8 = dy8 + sy, dx8 + sx
                    if 1 <= ny8 <= H + 1 and 1 <= nx8 <= W + 1:
                        # if G[ny8][nx8] == "#":
                        #     continue
                        # if G[ny8][nx8] == "@" or ans[ny8][nx8] != INF:
                        #     continue
                        if G[ny8][nx8] == "." and ans[ny8][nx8] > ans[sy][sx] + 1:
                            ans[ny8][nx8] = ans[sy][sx] + 1
                            q.append((ny8, nx8))
        # return print(-1)

    H, W = map(int, input().split())
    sy, sx = map(int, input().split())
    gy, gx = map(int, input().split())
    G = []
    G.append(["@"] * (W + 2))
    G += [["@"] + list(input()) + ["@"] for _ in range(H)]
    G.append(["@"] * (W + 2))

    INF = 10 ** 7
    ans = [[INF] * (W + 2) for _ in range(H + 2)]

    bfs((sy, sx), (gy, gx))

    print(ans[gy][gx] if ans[gy][gx] < INF else '-1')


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(1000000)

H,W = map(int,input().split())
curX,curY = map(int,input().split())
curX -= 1
curY -= 1
goalX,goalY =  map(int,input().split())
goalX -= 1
goalY -= 1

graph = [ list(input()) for _ in range(H) ]
q = deque([(curX,curY)])
dist = [ [float('inf')]*W for _ in range(H) ]
dist[curX][curY] = 0

while q:
  r,c = q.popleft()
  if r==goalX and c==goalY: break
  hop = dist[r][c]

  # if be able to move 1 step
  for x,y in [(1,0),(-1,0),(0,1),(0,-1)]:
    nr,nc = r+x,c+y
    if 0<=nr<H and 0<=nc<W and graph[nr][nc]!="#" and dist[nr][nc]>hop:
      dist[nr][nc] = hop
      q.append((nr,nc))

  for i in range(-2, 3):
    for j in range(-2, 3):
      nr,nc = r+i,c+j
      if 0<=nr<H and 0<=nc<W and graph[nr][nc]!="#" and dist[nr][nc]>hop+1:
        dist[nr][nc] = hop+1
        q.append((nr,nc))

ans = dist[goalX][goalY]
if ans == float('inf'):
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#import heapq
from collections import deque

H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

S = []
for _ in range(H):
  S.append(list(input()))
  
dpat = ((-1,0),(1,0),(0,-1),(0,1))
mpat = []
for i in range(-2,3):
  for j in range(-2,3):
    if (i,j) in dpat:
      continue
    if i == j and j == 0:
      continue
    mpat.append((i,j))
                
#print(mpat)

#BFS
visited = [[False] * W for _ in range(H)]
willSearch = [[False] * W for _ in range(H)]
Q = deque()
QN = deque()
Q.append((0,Ch,Cw))
QN.append((0,Ch,Cw))
while Q:
  while Q:
    c,x,y = Q.popleft()
    if visited[x][y]:
      continue
    visited[x][y] = True
    #print(c,x,y)
    if x == Dh and y == Dw:
      print(c)
      exit(0)
    for dx,dy in dpat:
      nx,ny = x+dx, y+dy
      if 0<=nx<H and 0<=ny<W:
        if S[nx][ny] == "#":
          continue
        if visited[nx][ny] or willSearch[nx][ny]:
          continue
        Q.append((c,nx,ny))
        QN.append((c,nx,ny))
        willSearch[nx][ny] = True
  while QN:
    c,x,y = QN.popleft()
    for dx,dy in mpat:
      nx,ny = x+dx, y+dy
      if 0<=nx<H and 0<=ny<W:
        if S[nx][ny] == "#":
          continue
        if visited[nx][ny] or willSearch[nx][ny]:
          continue
        Q.append((c+1,nx,ny))
        willSearch[nx][ny] = True
      
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
C0, C1 = map(int, input().split())
D0, D1 = map(int, input().split())

ARR = []

for i in range(H):
    ARR.append(input())


def calculate(h, w, c0, c1, d0, d1, arr):
    c0 = c0 - 1
    c1 = c1 - 1
    d0 = d0 - 1
    d1 = d1 - 1

    status = []
    for i in range(H):
        tmp = []
        for j in range(W):
            tmp.append(-1)
        status.append(tmp)

    q = deque()

    q.append((c0, c1, 0))

    while len(q) > 0:
        hIndex, wIndex, index = q.popleft()


        sss = [(hIndex,wIndex - 1), (hIndex, wIndex + 1), ( hIndex - 1, wIndex), (hIndex + 1, wIndex)]


        for sH, sW in sss:
            if (sH >= 0) and (sH < h) and (sW >= 0) and (sW < w):
                if arr[sH][sW] == '.':
                    tmpIndex = index
                    if status[sH][sW] == -1:
                        status[sH][sW] = tmpIndex
                        q.append((sH, sW, tmpIndex))
                    else:
                        if status[sH][sW] > tmpIndex:
                            status[sH][sW] = tmpIndex
                            q.append((sH, sW, tmpIndex))

        for _hIndex in range(hIndex - 2, hIndex + 3):
            for _wIndex in range(wIndex - 2, wIndex + 3):
                if (_hIndex == hIndex) and (_wIndex == wIndex):
                    continue
                if (_hIndex == c0) and (_wIndex == c1):
                    continue
                if (_hIndex, _wIndex) in sss:
                    continue
                if (_hIndex >= 0 and _hIndex < h) and (_wIndex >= 0 and _wIndex < w):
                    if arr[_hIndex][_wIndex] == '.':
                        tmpIndex = index + 1
                        if status[_hIndex][_wIndex] == -1:
                            status[_hIndex][_wIndex] = tmpIndex
                            q.append((_hIndex, _wIndex, tmpIndex))
                        # else:
                        #     if status[_hIndex][_wIndex] > tmpIndex:
                        #         status[_hIndex][_wIndex] = tmpIndex
                        #         q.append((_hIndex, _wIndex, tmpIndex))

    if status[d0][d1] >= 0:
        print(status[d0][d1])
    else:
        print(-1)


calculate(H, W, C0, C1, D0, D1, ARR)

Submission status: Wrong Answer

Solution code:

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    def bfs(start, goal):
        sy, sx = start
        gy, gx = goal
        q = deque()
        q.append(start)
        ans[sy][sx] = 0

        while q:
            sy, sx = q.popleft()
            if sy == gy and sx == gx:
                return print(ans[gy][gx])
            for dy, dx in drc4:
                ny, nx = dy + sy, dx + sx
                # if G[ny][nx] == "@" or ans[ny][nx] != INF:
                #     if G[ny][nx] != "#":
                #         continue
                if G[ny][nx] == "." and ans[ny][nx] > ans[sy][sx]:
                    ans[ny][nx] = ans[sy][sx]
                    q.append((ny, nx))

            for dy8 in range(-2, 3):
                for dx8 in range(-2, 3):
                    ny8, nx8 = dy8 + sy, dx8 + sx
                    if 1 <= ny8 <= H + 1 and 1 <= nx8 <= W + 1:
                        # if G[ny8][nx8] == "#":
                        #     continue
                        # if G[ny8][nx8] == "@" or ans[ny8][nx8] != INF:
                        #     continue
                        if G[ny8][nx8] == "." and ans[ny8][nx8] > ans[sy][sx] + 1:
                            ans[ny8][nx8] = ans[sy][sx] + 1
                            q.append((ny8, nx8))
        return print(-1)

    H, W = map(int, input().split())
    sy, sx = map(int, input().split())
    gy, gx = map(int, input().split())
    G = []
    G.append(["@"] * (W + 2))
    G += [["@"] + list(input()) + ["@"] for _ in range(H)]
    G.append(["@"] * (W + 2))

    # visited = [[False] * (W + 2) for _ in range(H+2)]
    INF = 10 ** 7
    ans = [[INF] * (W + 2) for _ in range(H + 2)]

    bfs((sy, sx), (gy, gx))


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W = map(int,input().split())
curX,curY = map(int,input().split())
curX -= 1
curY -= 1
goalX,goalY =  map(int,input().split())
goalX -= 1
goalY -= 1

graph = []
for _ in range(H):
  graph.append(list(input()))

ans = float('inf')
q = deque([(curX,curY)])
dist = [ [float('inf')]*W for _ in range(H) ]
dist[curX][curY] = 0

while q:
  r,c = q.popleft()
  if r==goalX and c==goalY: break
  hop = dist[r][c]

  # if be able to move 1 step
  for x,y in [(-1,0),(0,-1),(1,0),(0,1)]:
    nr,nc = r+x,c+y
    if nr<0 or nc<0 or nr>=H or nc>=W: continue
    if graph[nr][nc] == "#": continue
    if dist[nr][nc] <= hop: continue
    dist[nr][nc] = hop
    q.append((nr,nc))

  for i in range(-2, 3):
    for j in range(-2, 3):
      nr,nc = r+i,c+j
      if nr<0 or nc<0 or nr>=H or nc>=W: continue
      if graph[nr][nc] == "#": continue
      if dist[nr][nc] <= hop+1: continue
      dist[nr][nc] = hop+1
      q.append((nr,nc))

ans = dist[goalX][goalY]
if ans == float('inf'):
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W = map(int,input().split())
curX,curY = map(int,input().split())
goalX,goalY =  map(int,input().split())
goalX -= 1
goalY -= 1

graph = []
for _ in range(H):
  r = list(input())
  graph.append(r)

ans = float('inf')
q = deque([(curX-1,curY-1,0)])
dist = [ [float('inf')]*W for _ in range(H) ]

while q:
  r,c,hop = q.popleft()
  if r==goalX and c==goalY: break

  # if be able to move 1 step
  for x,y in [(-1,0),(0,-1),(1,0),(0,1)]:
    nr,nc = r+x,c+y
    if nr<0 or nc<0 or nr>=H or nc>=W: continue
    if graph[nr][nc] == "#": continue
    if dist[nr][nc] <= hop: continue
    dist[nr][nc] = hop
    q.append((nr,nc,hop))

  for i in range(-2, 3):
    for j in range(-2, 3):
      nr,nc = r+i,c+j
      if nr<0 or nc<0 or nr>=H or nc>=W: continue
      if graph[nr][nc] == "#": continue
      if dist[nr][nc] <= hop+1: continue
      dist[nr][nc] = hop+1
      q.append((nr,nc,hop+1))

ans = dist[goalX][goalY]
if ans == float('inf'):
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W = map(int,input().split())
curX,curY = map(int,input().split())
goalX,goalY =  map(int,input().split())
goalX -= 1
goalY -= 1

graph = []
for _ in range(H):
  r = list(input())
  graph.append(r)

ans = float('inf')
q = deque([(curX-1,curY-1,0)])
dist = [ [float('inf')]*W for _ in range(H) ]

while q:
  r,c,hop = q.popleft()
  if r==goalX and c==goalY: break

  # if be able to move 1 step
  for x,y in [(-1,0),(0,-1),(1,0),(0,1)]:
    nr,nc = r+x,c+y
    if nr<0 or nc<0 or nr>=H or nc>=W: continue
    if graph[nr][nc] == "#": continue
    if dist[nr][nc] <= hop: continue
    dist[nr][nc] = hop
    q.append((nr,nc,hop))

  for i in range(-2, 3):
    for j in range(-2, 3):
      nr,nc = r+i,c+j
      if nr<0 or nc<0 or nr>=H or nc>=W: continue
      if graph[nr][nc] == "#": continue
      if dist[nr][nc] <= hop: continue
      dist[nr][nc] = hop+1
      q.append((nr,nc,hop+1))

ans = dist[goalX][goalY]
if ans == float('inf'):
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))


def solve():
    h, w = rl()
    starth, startw = rl()
    endh, endw = rl()
    maze = []
    for i in range(h):
        maze.append(list(input()))

    def nbrs(x, y):
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < h and 0 <= ny and ny < w:
                yield (nx, ny)

    def magic(x, y):
        for nx in range(x - 2, x + 3):
            for ny in range(y - 2, y + 3):
                if nx == x and ny == y: continue
                if 0 <= nx and nx < h and 0 <= ny and ny < w:
                    yield (nx, ny)


    bridges = dd(set)
    def dfs(x, y, num):
        if maze[x][y] != '.':
            return
        else:
            maze[x][y] = num
            for nx, ny in magic(x, y):
                if maze[nx][ny] not in ['.', '#', num]:
                    bridges[num].add(maze[nx][ny])
                    bridges[maze[nx][ny]].add(num)
            for nx, ny in nbrs(x, y):
                dfs(nx, ny, num)

    num = 0
    for x in range(h):
        for y in range(w):
            if maze[x][y] == ".":
                dfs(x, y, num)
                num += 1
   
    curr = [maze[starth-1][startw-1]]
    goal = maze[endh-1][endw-1]
    if curr[0] == goal:
        print (0)

    seen = set(curr)
    depth = 0
    while curr:
        ring = []
        depth += 1
        for node in curr:
            for nxt in bridges[node]:
                if nxt not in seen:
                    if nxt == goal:
                        print (depth)
                        return
                    seen.add(nxt)
                    ring.append(nxt)
        curr = ring

    print (-1)



mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
S=[input() for _ in range(H)]
visited=[[-1]*W for _ in range(H)]
visited[ch-1][cw-1]=0
h,done=deque([(ch-1,cw-1)]),[(ch-1,cw-1)]
c=0
while 1:
  while h:
    cx,cy=h.popleft()
    for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
      nx,ny = cx+dx,cy+dy
      if 0<=nx<H and 0<=ny<W and S[nx][ny]=='.' and visited[nx][ny]==-1:
        h.append((nx,ny))
        done.append((nx,ny))
        visited[nx][ny]=c
  for cx,cy in done:
    for dx in range(-2,3):
      for dy in range(-2,3):
        nx,ny = cx+dx,cy+dy
        if 0<=nx<H and 0<=ny<W and S[nx][ny]=='.' and visited[nx][ny]==-1:
          h.append((nx,ny))
          visited[nx][ny]=c+1
  if not h:
    break
  c+=1
  done=[]
print(visited[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
S=[input() for _ in range(H)]
visited=[[-1]*W for _ in range(H)]
visited[ch-1][cw-1]=0
h,done=deque([(ch-1,cw-1)]),[(ch-1,cw-1)]
c=0
while 1:
  while h:
    cx,cy=h.popleft()
    for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
      nx,ny = cx+dx,cy+dy
      if 0<=nx<H and 0<=ny<W and S[nx][ny]=='.' and visited[nx][ny]==-1:
        h.append((nx,ny))
        done.append((nx,ny))
        visited[nx][ny]=c
  for cx,cy in done:
    for dx in range(-2,3):
      for dy in range(-2,3):
        nx,ny = cx+dx,cy+dy
        if 0<=nx<H and 0<=ny<W and S[nx][ny]=='.' and visited[nx][ny]==-1:
          h.append((nx,ny))
          visited[nx][ny]=c+1
  if not h or visited[dh-1][dw-1]!=-1:
    break
  c+=1
  done=[]
print(visited[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = list(map(int, input().split()))
cy, cx = list(map(int, input().split()))
dy, dx = list(map(int, input().split()))

grid = []
for i in range(h):
    grid.append(input())

nodes = []
edges = {}

for y in range(h):
    for x in range(w):
        edges[str((x, y))] = []

        if grid[y][x] == ".":
            ci = [(x-1, y, 0), (x+1, y, 0), (x, y-1, 0), (x, y+1, 0)]

            for o1 in [-2, 2]:
                for o2 in [-1, 0, 1]:
                    ci.append((x+o1, y+o2, 1))
                    ci.append((x+o2, y+o1, 1))

                for o3 in [-2, 2]:
                    ci.append((x+o1, y+o3, 1))

            for c in ci:
                if c[0] >= 0 and c[0] < w and c[1] >= 0 and c[1] < h:
                    if grid[c[1]][c[0]] == ".":
                        edges[str((x, y))].append(c)

start = (cx-1, cy-1)
goal = (dx-1, dy-1)

visit = deque()
visit.append(start)
dist = {str(start): 0}
found = False

while len(visit) > 0:
    nei = visit.popleft()
    if nei[0] == goal[0] and nei[1] == goal[1]:
        found = True
        break

    for n2 in edges[str((nei[0], nei[1]))]:
        key = str((n2[0], n2[1]))
        n2dist = dist[str(nei)] + n2[2]
        if key in dist:
            dist[key] = min(dist[key], n2dist)
        else:
            dist[key] = n2dist

            if n2[2] == 0:
                visit.appendleft((n2[0], n2[1]))
            else:
                visit.append((n2[0], n2[1]))

print(dist[str(goal)] if found else -1)