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:
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [list(input()) for i in range(H)]
 
res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
count = 0
 
que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0
 
while (que or que_warp):
    while (que):
        if count > 0:
            que_warp.append(que[0])
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (0<=nx<=H-1) and (0<=ny<=W-1):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    que_warp.append((nx,ny))
        que.pop(0)
 
    count += 1
 
    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (0 <= nx <= H-1) and (0 <= ny <= W-1):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
        que_warp.pop(0)
 
print (res_S[Dh-1][Dw-1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readlines
from collections import deque

def main():
    infty = 10 ** 6
    wx = [1, 0, -1, 0]
    wy = [0, 1, 0, -1]
    mx = [2, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, -1, -1, -1, -1, -2, -2, -2, -2, -2]
    my = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]
    lines = input()
    H, W = list(map(int, lines[0].split()))
    ch, cw = list(map(int, lines[1].split()))
    dh, dw = list(map(int, lines[2].split()))

    S = [str(lines[i+3].strip()) for i in range(H)]

    def bfs():
        while d:
            y, x = d.popleft()

            #walk
            for i in range(4):
                nx, ny = x + wx[i], y + wy[i]
                if nx < 0 or ny < 0 or W <= nx or H <= ny or S[ny][nx] == '#':
                    continue
                dp[ny][nx] = min(dp[ny][nx], dp[y][x])
                if checker[ny][nx] == 0:
                    checker[ny][nx] = 1
                    d.append([ny, nx])

            #worp
            for i in range(20):
                nx, ny = x + mx[i], y + my[i]
                if nx < 0 or ny < 0 or  W <= nx or H <= ny or S[ny][nx] == '#':
                    continue
                dp[ny][nx] = min(dp[ny][nx], dp[y][x]+1)
                if checker[ny][nx] == 0:
                    checker[ny][nx] = 1
                    d.append([ny, nx])
    #start
    d = deque()
    d.append([ch-1, cw-1])
    dp = [[infty] * W for i in range(H)]
    dp[ch-1][cw-1] = 0
    checker = [[0] * W for i in range(H)]
    checker[ch-1][cw-1] = 1

    bfs()

    if dp[dh-1][dw-1] < infty:
        print(dp[dh-1][dw-1])
    else:
        print(-1)





main()

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split()) 
sy, sx = map(int, input().split()) 
gy, gx = map(int, input().split()) 
sy-=1
sx-=1
gy-=1
gx-=1
s = [input() for i in range(h)]

from collections import deque

q = deque([])
q.append([sy, sx, 0])

mx=[0,0,1,-1]
my=[1,-1,0,0]

vis = [[-1]*w for i in range(h)]
vis[sy][sx]=0

while len(q)>0:
  y, x, c = q.popleft()

  for i in range(4):
    nx=x+mx[i]
    ny=y+my[i]
    if 0<=nx<w and 0<=ny<h and s[ny][nx]=="." and vis[ny][nx]!=c:
      vis[ny][nx]=c
      q.appendleft([ny,nx,c])
      if ny==gy and nx == gx:
        print(c)
        quit()
  
  for xi in range(5):
    for yi in range(5):
      nx=x+xi-2
      ny=y+yi-2    
      if 0<=nx<w and 0<=ny<h and s[ny][nx]=="." and vis[ny][nx]==-1:
        vis[ny][nx]=c+1
        q.append([ny,nx,c+1])
        if ny==gy and nx == gx:
          print(c+1)
          quit()
        

print(vis[gy][gx])

Submission status: Wrong Answer

Solution code:
class Grid:
    def __init__(self, H, W, grid, road_wall=(".", "#")):
        self.road, self.wall = road_wall
        self.H = H
        self.W = W
        self.grid = grid
        self.parent = [[-1] * self.W for _ in range(self.H)]
        self.move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補
        self.move2 = dict()
        self.move2[(1,0)] = [(2,-1),(2,0),(2,1),(2,2),(1,1)]
        self.move2[(-1,0)] = [(-2,-1),(-2,0),(-2,1),(-2,-2),(-1,-1)]
        self.move2[(0,1)] = [(1,2),(0,2),(-1,2),(-2,2),(-1,1)]
        self.move2[(0,-1)] = [(1,-2),(0,-2),(-1,-2),(2,-2),(1,-1)]

    def bfs(self, start=(0,0), goal=-3, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if save:
            parent = self.parent
        else:
            parent = [[-1] * self.W for _ in range(self.H)]
        p, t = start, time
        parent[p[0]][p[1]] = -2
        next_set = deque([(p, t)])
        broken_set = deque([])
        while next_set:
            while next_set:
                p, t = next_set.popleft()
                h, w = p
                for dh, dw in self.move:
                    nh, nw = (h + dh, w + dw)
                    if nh < 0 or nh >= self.H or nw < 0 or nw >= self.W:
                        continue
                    if parent[nh][nw] != -1:
                        continue
                    if self.grid[nh][nw] == self.wall:         # 壁があったら進まない
                        for dh2, dw2 in self.move2[(dh,dw)]:
                            nh, nw = (h + dh2, w + dw2)
                            if nh < 0 or nh >= self.H or nw < 0 or nw >= self.W:
                                continue
                            if parent[nh][nw] != -1:
                                continue
                            if self.grid[nh][nw] == self.wall:  # 壁があったら進まない
                                continue
                            if (nh, nw) == goal:
                                return t + 1
                            parent[nh][nw] = 1
                            broken_set.append(((nh, nw), t+1))
                        continue
                    if (nh, nw) == goal:
                        return t
                    #### (debug code) ######
                    # self.debug(start, goal, q, t)
                    ########################
                    parent[nh][nw] = p
                    next_set.append(((nh, nw), t))
            next_set = broken_set
            broken_set = deque([])
        return -1

    def debug(self, start, goal, p, t):
        player = p
        debug_grid = list(list(self.grid[h]) for h in range(self.H))
        if start != (None, None):
            debug_grid[start[0]][start[1]] = "S"
        if goal != -3:
            debug_grid[goal[0]][goal[1]] = "G"
        debug_grid[player[0]][player[1]] = "P"
        print("~~~~~~~~~ t = " + str(t + 1) + "  ~~~~~~~~")
        for debug_h in range(self.H):
            print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W)))


############################################################################################

from collections import deque
import sys
input = sys.stdin.readline



road, wall = ".", "#"                         # (進行可能を意味する記号, 進行不可を意味する記号)

H, W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)
x, y = map(int, input().split())
start = (x-1,y-1)
x, y = map(int, input().split())
goal = (x-1,y-1)
grid = []
for h in range(H):
    grid.append(input().rstrip())

g = Grid(H, W, grid, (road, wall))
res = g.bfs(start=start, goal=goal)
print(res)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split()) 
sy, sx = map(int, input().split()) 
gy, gx = map(int, input().split()) 
sy-=1
sx-=1
gy-=1
gx-=1
s = [input() for i in range(h)]

from collections import deque

q = deque([])
q.append([sy, sx, 0])

mx=[0,0,1,-1]
my=[1,-1,0,0]

vis = [[-1]*w for i in range(h)]
vis[sy][sx]=0

while len(q)>0:
  y, x, c = q.popleft()

  for i in range(4):
    nx=x+mx[i]
    ny=y+my[i]
    if 0<=nx<w and 0<=ny<h and s[ny][nx]=="." and vis[ny][nx]!=c:
      vis[ny][nx]=c
      q.appendleft([ny,nx,c])
      if ny==gy and nx == gx:
        print(c)
        quit()
  
  for xi in range(5):
    for yi in range(5):
      nx=x+xi-2
      ny=y+yi-2    
      if 0<=nx<w and 0<=ny<h and s[ny][nx]=="." and vis[ny][nx]==-1:
        vis[ny][nx]=c+1
        q.appendleft([ny,nx,c+1])
        if ny==gy and nx == gx:
          print(c)
          quit()
        

print(vis[gy][gx])

Submission status: Wrong Answer

Solution code:
import heapq
xy=[(1,0),(-1,0),(0,1),(0,-1)]
wp=[(-1,-1),(-1,1),(1,1),(1,-1),(2,0),(-2,0),(0,2),(0,-2),(-2,-1),(-2,1),(2,1),(2,-1),(-1,-2),(-1,2),(1,2),(1,-2),(-2,-2),(-2,2),(2,2),(2,-2)]

h,w=map(int,input().split())
c1,c2=map(int,input().split())
d1,d2=map(int,input().split())
d=[list(input()) for i in range(h)]
d[c1-1][c2-1]=0
p=[]
heapq.heappush(p,(0,d1-1,d2-1))
while len(p):
    a,b,c=heapq.heappop(p)
    for x,y in xy:
        x+=b
        y+=c
        if 0<=x<h and 0<=y<w and d[x][y]!="#":
            if d[x][y]=="." or d[x][y]>a:
                d[x][y]=a
                heapq.heappush(p,(a,x,y))
    for x,y in wp:
        x+=a
        y+=b
        if 0<=x<h and 0<=y<w and d[x][y]!="#":
            if d[x][y]=="." or d[x][y]>a+1:
                d[x][y]=a+1
                heapq.heappush(p,(a+1,x,y))
    if d[d1-1][d2-1]==a:
        print(a)
        exit()
#    print(p)
#    print(d)

print(-1 if (d[d1-1][d2-1]=="#" or d[d1-1][d2-1]==".") else d[d1-1][d2-1])

Submission status: Wrong Answer

Solution code:
import sys;input=sys.stdin.readline
H, W = map(int, input().split())
cx, cy = map(int, input().split())
dx, dy = map(int, input().split())
cx-=1;cy-=1;dx-=1;dy-=1
B = []
for _ in range(H):
    B.append(input().strip())

D = [0]*(H*W)
bb = -1
t = 0
t2c = dict()
for i in range(H):
    for j in range(W):
        if B[i][j] == "#":
            D[i*W+j] = bb
            continue
        if D[i*W+j]>0:
            continue
        t += 1
        t2c[t] = set()
        stack = [(i, j)]
        while stack:
            u, v = stack.pop()
            D[W*u+v] = t
            t2c[t].add((u, v))
            for x, y in [(u+1, v), (u-1, v), (u, v-1), (u, v+1)]:
                if x >= H or x<0:
                    continue
                if y >= W or y<0:
                    continue
                if B[x][y] == "#":
                    D[x*W+y] = bb
                    continue
                if D[x*W+y]:
                    continue
                stack.append((x, y))
depth = 0
cs = [D[cx*W+cy]]
tt = D[dx*W+dy]
vs = set([cs[0]])
if tt in vs:
    print(0)
    sys.exit()
sys.exit()
while True:
    depth += 1
    nexts = []
    for c in cs:
        for i, j in t2c[c]:
            for ii in range(max(0, i-2), min(i+3, H)):
                for jj in range(max(0, j-2), min(j+3, W)):
                    if B[ii][jj] == "#":
                        continue
                    if D[ii*W+jj] in vs:
                        continue
                    nexts.append(D[ii*W+jj])
                    if D[ii*W+jj] == tt:
                        print(depth)
                        sys.exit()
    cs = nexts
    if not cs:
        break
print(-1)

Submission status: Wrong Answer

Solution code:
class Grid:
    def __init__(self, H, W, grid, road_wall=(".", "#")):
        self.road, self.wall = road_wall
        self.H = H
        self.W = W
        self.grid = grid
        self.parent = [[-1] * self.W for _ in range(self.H)]
        self.move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補
        self.move2 = dict()
        self.move2[(1,0)] = [(2,-1),(2,0),(2,1),(2,2),(1,1)]
        self.move2[(-1,0)] = [(-2,-1),(-2,0),(-2,1),(-2,-2),(-1,-1)]
        self.move2[(0,1)] = [(1,2),(0,2),(-1,2),(-2,2),(-1,1)]
        self.move2[(0,-1)] = [(1,-2),(0,-2),(-1,-2),(2,-2),(1,-1)]

    def bfs(self, start=(0,0), goal=-3, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if save:
            parent = self.parent
        else:
            parent = [[-1] * self.W for _ in range(self.H)]
        p, t = start, time
        parent[p[0]][p[1]] = -2
        next_set = deque([(p, t)])
        broken_set = deque([])
        while next_set:
            while next_set:
                p, t = next_set.popleft()
                h, w = p
                for dh, dw in self.move:
                    nh, nw = (h + dh, w + dw)
                    if nh < 0 or nh >= self.H or nw < 0 or nw >= self.W:
                        continue
                    if parent[nh][nw] != -1:
                        continue
                    if self.grid[nh][nw] == self.wall:         # 壁があったら進まない
                        for dh2, dw2 in self.move2[(dh,dw)]:
                            nh, nw = (h + dh2, w + dw2)
                            if nh < 0 or nh >= self.H or nw < 0 or nw >= self.W:
                                continue
                            if parent[nh][nw] != -1:
                                continue
                            if self.grid[nh][nw] == self.wall:  # 壁があったら進まない
                                continue
                            if (nh, nw) == goal:
                                return t + 1
                            parent[nh][nw] = 1
                            broken_set.append(((nh, nw), t+1))
                        continue
                    if (nh, nw) == goal:
                        return t
                    #### (debug code) ######
                    # self.debug(start, goal, q, t)
                    ########################
                    parent[nh][nw] = p
                    next_set.append(((nh, nw), t))
            next_set = broken_set
        return -1

    def debug(self, start, goal, p, t):
        player = p
        debug_grid = list(list(self.grid[h]) for h in range(self.H))
        if start != (None, None):
            debug_grid[start[0]][start[1]] = "S"
        if goal != -3:
            debug_grid[goal[0]][goal[1]] = "G"
        debug_grid[player[0]][player[1]] = "P"
        print("~~~~~~~~~ t = " + str(t + 1) + "  ~~~~~~~~")
        for debug_h in range(self.H):
            print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W)))


############################################################################################

from collections import deque
import sys
input = sys.stdin.readline



road, wall = ".", "#"                         # (進行可能を意味する記号, 進行不可を意味する記号)

H, W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)
x, y = map(int, input().split())
start = (x-1,y-1)
x, y = map(int, input().split())
goal = (x-1,y-1)
grid = []
for h in range(H):
    grid.append(input().rstrip())

g = Grid(H, W, grid, (road, wall))
res = g.bfs(start=start, goal=goal)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
readline=sys.stdin.readline

H,W=map(int,readline().split())

sy,sx = map(int,readline().split())
gy,gx = map(int,readline().split())

sy -= 1
sx -= 1
gy -= 1
gx -= 1

G = [None] * H
for i in range(H):
  G[i] = readline().rstrip()

# 幅優先探索
INF = 10 ** 10
costs = [[INF] * W for i in range(H)]

from collections import deque
q = deque([])
# y,x,魔法の回数,親y,親x
q.append((sy,sx,0,-1,-1))

cases = ((0,1),(0,-1),(1,0),(-1,0))
warp = ((-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-2,-1),(2,-1),(-2,0),(2,0),(-2,1),(2,1),(-2,-2),(-2,-1),(-2,0),(-2,0),(-2,0),(-1,-1),(-1,1),(1,-1),(1,1))
while q:
  y,x,co,py,px = q.popleft()
  if costs[y][x] <= co:
    continue
  if G[y][x] == "#":
    continue
  costs[y][x] = co
  for c in cases:
    if y + c[0] == py and x + c[1] == px:
      continue
    if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
      if G[y + c[0]][x + c[1]] == "#":
        continue
      if costs[y + c[0]][x + c[1]] <= co:
        continue
      q.appendleft((y + c[0], x + c[1], co, y, x))
  # 行先がないのでワープ検討
  for w in warp:
    if 0 <= y + w[0] < H and 0 <= x + w[1] < W:
      if G[y + w[0]][x + w[1]] == "#":
        continue
      if costs[y + w[0]][x + w[1]] <= co + 1:
        continue
      q.append((y + w[0], x + w[1], co + 1, y, x))

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

Submission status: Wrong Answer

Solution code:
import queue
h, w = map(int, input().split())
c = list(map(int, input().split()))
d = list(map(int, input().split()))
ans = float('inf')
q = queue.Queue()
q.put([c[0], c[1], 0])

route = [['#']*(w+2)]
for i in range(h):
    route += [list('#'+input()+'#')]
route += [['#']*(w+2)]

while not q.empty():
    now = q.get()
    if route[now[0]][now[1]] == '.':
        route[now[0]][now[1]] = '#'
    if now[0] == d[0] and now[1] == d[1]:
        ans = min(ans, now[2])
    if route[now[0]+1][now[1]] != '#':
        q.put([now[0]+1, now[1], now[2]])
    if route[now[0]-1][now[1]] != '#':
        q.put([now[0]-1, now[1], now[2]])
    if route[now[0]][now[1]+1] != '#':
        q.put([now[0], now[1]+1, now[2]])
    if route[now[0]][now[1]-1] != '#':
        q.put([now[0], now[1]-1, now[2]])
    for i in range(-2, 3):
        for j in range(-2, 3):
            if 0 <= now[0]+i <= h+1 and 0 <= now[1]+j <= w+1:
                if route[now[0]+i][now[1]+j] != '#':
                    q.put([now[0]+i, now[1]+j, now[2]+1])

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())
c=tuple(map(int,input().split()))
c=(c[0]-1,c[1]-1)
d=tuple(map(int,input().split()))
d=(d[0]-1,d[1]-1)
S=[]
for i in range(H):
  S.append(input())
  
INF=10**8

def bfs(s):
  seen = [[0 for i in range(W)] for j in range(H)]
  total = [[INF for i in range(W)] for j in range(H)]
  todo = deque([])
  now = s
  seen[now[0]][now[1]],total[now[0]][now[1]] = 1,0
  todo.append(now)
  while 1:
    if len(todo)==0:break
    now = todo.popleft()
    wall = [0,0]
    for d in [(1,0),(-1,0),(0,1),(0,-1)]:
      new = (now[0]+d[0], now[1]+d[1])
      if new[0]<0 or new[0]>=H:continue
      if new[1]<0 or new[1]>=W:continue
      if seen[new[0]][new[1]]==1:continue
      if S[new[0]][new[1]]=='#':
        wall[0] += abs(new[0])
        wall[1] += abs(new[1])
        continue
      seen[new[0]][new[1]] = 1
      todo.appendleft(new)
      total[new[0]][new[1]] = total[now[0]][now[1]]
    if sum(wall)==0:continue
    for dx in range(-2,3):
      if wall[0]==0:continue
      for dy in range(-2,3):
        if wall[1]==0:continue
        new = (now[0]+dx,now[1]+dy)
        if new[0]<0 or new[0]>=H:continue
        if new[1]<0 or new[1]>=W:continue
        if seen[new[0]][new[1]]==1:continue
        if S[new[0]][new[1]]=='#':continue
        seen[new[0]][new[1]] = 1
        todo.append(new)
        total[new[0]][new[1]] = total[now[0]][now[1]]+1
        
  return total

total = bfs(c)
ans = total[d[0]][d[1]]
if ans == INF:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10**9)

h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())

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

queue = deque([(ch-1, cw-1)])
S = [[float("inf")]*w for _ in range(h)]
S[ch-1][cw-1] = 0

while queue:
    y, x = queue.popleft()
    dx_dy = [(1,0),(0,1),(-1,0),(0,-1)]
    for j, i in dx_dy:
        if 0 <= x+i < w and 0 <= y+j < h:
            if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                S[y+j][x+i] = S[y][x]
                queue.appendleft((y+j, x+i))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if i != 0 and j != 0:
                if 0 <= x+i < w and 0 <= y+j < h:
                    if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                        S[y+j][x+i] = S[y][x] + 1
                        queue.append((y+j, x+i))


if S[dh-1][dw-1] == float("inf"):
    print(-1)
else:
    print(S[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
H, W = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())

S = [0] * H
for i in range(H):
    S[i] = input()

class UnionFind(object):
    def __init__(self, n = 1):
        self.link = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.link[x] == x:
            return x

        # re-connect union find to make the height of tree lower
        # you can use while, but recursion makes it easier to reconnect
        self.link[x] = self.find(self.link[x])
        return self.link[x]

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.size[x] < self.size[y]:
            x, y = y, x
        self.link[y] = x
        self.size[x] += self.size[y]
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]

uni = UnionFind(H * W)

visited = [False] * (H * W)
def dfs(i, j):
    if visited[i * W + j]:
        return
    visited[i * W + j] = True
    for dy, dx in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        y = i + dy
        x = j + dx
        if y < 0 or y >= H or x < 0 or x >= W:
            continue
        if visited[y * W + x]:
            continue
        if S[i][j] == '#':
            continue
        uni.unite(i * W + j, y * W + x)
        dfs(y, x)

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        if visited[i * W + j]:
            continue
        dfs(i, j)

c = ch * W + cw
d = dh * W + dw
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        u = i * W + j
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                y = i + dy
                x = j + dx
                if y < 0 or y >= H or x < 0 or x >= W:
                    continue
                if S[y][x] == '#':
                    continue
                v = y * W + x
                if not uni.is_same(u, v):
                    uni.unite(u, v)
                    ans += 1
                    if uni.is_same(c, d):
                        print(ans)
                        exit()
if uni.is_same(c, d):
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [list(input()) for i in range(H)]

res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
count = 0

que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0

while (que or que_warp):
    while (que):
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    que_warp.append((nx,ny))
                    if (nx == Dh) and (ny == Dw):
                        print(res_S[Dh - 1][Dw - 1])
                        exit()
        que.pop(0)

    count += 1

    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
                    if (nx == Dh) and (ny == Dw):
                        print(res_S[Dh - 1][Dw - 1])
                        exit()
        que_warp.pop(0)

print (res_S[Dh-1][Dw-1])

Submission status: Wrong Answer

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
def Dijkstra(graph,s):
    INF = 10**9
    dist = [INF]*len(graph)
    dist[s] = 0
    #nn_node = [-1]*len(graph) #nearest neighborのnode
    #checked=[False]*len(graph) #dist 確定
    heap = [(0,s)]
    while heap:
        cost,node = hq.heappop(heap)
        if cost>dist[node]:continue
        for weight,nex in graph[node]:
            d = cost+weight
            if d<dist[nex]:
                dist[nex] = d
                #nn_node[nex] = node
                hq.heappush(heap,(d,nex))
    for i in range(len(dist)):
        if dist[i] == INF:
            dist[i] = -1
    return dist #,nn_node

dyx = [(i,j) for i in range(-1,2) for j in range(-1,2)]
dyx.remove((0,0))

INF=10**9
H,W = ma()
ch,cw = ma()
ch-=1;cw-=1
dh,dw=ma()
dh-=1;dw-=1
area= []
for h in range(H):
    area.append(input())

group = [[-1]*W for h in range(H)]
def BFS(sy,sx,cnt):
    que = collections.deque()
    que.append((sy,sx))
    group[sy][sx]=idx
    while que:
        h,w = que.popleft()
        for dy,dx in dyx:
            if (0<=h+dy<H )and (0<=w+dx<W):
                if area[h+dy][w+dx] =="." and group[h+dy][w+dx] ==-1:
                    group[h+dy][w+dx] = idx
                    que.append((h+dy,w+dx))


idx = 0
for h in range(H):
    for w in range(W):
        if area[h][w] =="." and group[h][w] ==-1:
            BFS(h,w,idx)
            idx+=1

tree = [set() for _ in range(idx)]
dyx2 = [(i,j) for i in range(-2,3) for j in range(-2,3)]
dyx2.remove((0,0))
for h in range(H):
    for w in range(W):
        g = group[h][w]
        for dy,dx in dyx2:
            if (0<=h+dy<H )and (0<=w+dx<W) and (g !=group[h+dy][w+dx]):
                tree[g].add((1,group[h+dy][w+dx]))
dist = Dijkstra(tree,group[ch][cw])

#print(group)
#print(tree)
print(dist[group[dh][dw]])

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [list(input()) for i in range(H)]
 
res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
count = 0
 
que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0
 
while (que or que_warp):
    while (que):
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    que_warp.append((nx,ny))
        que.pop(0)
 
    count += 1
 
    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
                    que_warp.append((nx, ny))
        que_warp.pop(0)
 
print (res_S[Dh-1][Dw-1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
H, W = map(int, input().split())
c = [int(i) + 1 for i in input().split()]
d = [int(i) + 1 for i in input().split()]

s = []
s.append('#'*(W+4))
s.append('#'*(W+4))
for i in range(H):
    a = input()
    s.append('##' + a + '##')
s.append('#'*(W+4))
s.append('#'*(W+4))

q = deque([]) # 探索開始点
qq = deque([])
q.append((c[0], c[1], 0))
visited = [[False for __ in range(W+4)] for _ in range(H+4)]

while q:
    xx, yy, kaisuu = q.popleft()
    if visited[xx][yy] == True:
        continue
    qq.append((xx, yy, kaisuu))
    ls = deque()
    while qq:
        x, y, kaisuu = qq.pop()
        visited[x][y] = True
        ls.append((x, y, kaisuu))
        if x == d[0] and y == d[1]:
            print(kaisuu)
            sys.exit()
        if s[x+1][y] == '.' and visited[x+1][y] == False:
            qq.append((x+1, y, kaisuu))
        if s[x-1][y] == '.' and visited[x-1][y] == False:
            qq.append((x-1, y, kaisuu))
        if s[x][y+1] == '.' and visited[x][y+1] == False:
            qq.append((x, y+1, kaisuu))
        if s[x][y-1] == '.' and visited[x][y-1] == False:
            qq.append((x, y-1, kaisuu))
    for u in ls:
        a, b, e = u
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                if abs(i) == 1 and abs(j) == 1:
                    continue
                if s[a+i][b+j] == '.' and visited[a+i][b+j] == False:
                    q.append((a+i, b+j, e+1))
print(-1)