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:
import numpy as np
from collections import deque
H,W = map(int, input().split())
CH,CW = map(int, input().split())
DH,DW = map(int, input().split())
[CH,CW,DH,DW] = [CH-1,CW-1,DH-1,DW-1]
S = np.array([list(input()) for i in range(H)])
M = 10 ** 9
Distance = np.ones((H,W))*M
Distance[CH,CW] = 0
[nowH,nowW] = [CH,CW]
q0 = deque([])
q0.append([nowH,nowW])
q1 = deque([])
while len(q0) != 0 or len(q1) != 0:
  if len(q0) != 0:
    [nowH,nowW] = q0.popleft()
  else:
    [nowH,nowW] = q1.popleft()
  if [nowH,nowW] == [DH,DW]:
    break
  for i in range(-2,3):
    for j in range(-2,3):
      if nowH+i >= 0 and nowW+j >= 0 and nowH+i < H and nowW+j < W:
        if (abs(i) + abs(j)) == 1:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              q0.append([nowH+i,nowW+j])
            elif [nowH+i,nowW+j] in q1:
              q0.append([nowH+i,nowW+j])
              q1.remove([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW],Distance[nowH+i,nowW+j])
        elif (abs(i) + abs(j)) >= 2:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              q1.append([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW]+1,Distance[nowH+i,nowW+j])       
  print(Distance)
if Distance[DH,DW] == M:
  print(-1)
else:
  print(int(Distance[DH,DW]))

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    from sys import stdin
    readline = stdin.readline

    INF = float('inf')

    H, W = map(int, readline().split())
    Ch, Cw = map(lambda x: int(x) - 1, readline().split())
    Dh, Dw = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    while q:
        warpq = []
        while q:
            h, w = q.popleft()
            a = t[h][w]
            if h - 1 >= 0 and t[h - 1][w] > a:
                q.append((h - 1, w))
                warpq.append((h - 1, w))
                t[h - 1][w] = a
            if h + 1 < H and t[h + 1][w] > a:
                q.append((h + 1, w))
                warpq.append((h + 1, w))
                t[h + 1][w] = a
            if w - 1 >= 0 and t[h][w - 1] > a:
                q.append((h, w - 1))
                warpq.append((h, w - 1))
                t[h][w - 1] = a
            if w + 1 < W and t[h][w + 1] > a:
                q.append((h, w + 1))
                warpq.append((h, w + 1))
                t[h][w + 1] = a

        for h, w in warpq:
            for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
                ti = t[i]
                for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                    if ti[j] <= a + 1:
                        continue
                    ti[j] = a + 1
                    q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
H,W = map(int, input().split())
CH,CW = map(int, input().split())
DH,DW = map(int, input().split())
[CH,CW,DH,DW] = [CH-1,CW-1,DH-1,DW-1]
S = np.array([list(input()) for i in range(H)])
M = 2*H*W
Distance = np.ones((H,W))*M
Distance[CH,CW] = 0
[nowH,nowW] = [CH,CW]
q0 = deque([])
q0.append([nowH,nowW])
q1 = deque([])
while len(q0) != 0 or len(q1) != 0:
  if len(q0) != 0:
    [nowH,nowW] = q0.popleft()
  else:
    [nowH,nowW] = q1.popleft()
  for i in range(-2,3):
    for j in range(-2,3):
      if nowH+i >= 0 and nowW+j >= 0 and nowH+i < H and nowW+j < W:
        if (abs(i) + abs(j)) == 1:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              q0.append([nowH+i,nowW+j])
              if [nowH+i,nowW+j] in q1:
                q1.remove([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW],Distance[nowH+i,nowW+j])
        elif (abs(i) + abs(j)) >= 2:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              q1.append([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW]+1,Distance[nowH+i,nowW+j])       
if Distance[DH,DW] == M:
  print(-1)
else:
  print(int(Distance[DH,DW]))

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
H,W = map(int, input().split())
CH,CW = map(int, input().split())
DH,DW = map(int, input().split())
[CH,CW,DH,DW] = [CH-1,CW-1,DH-1,DW-1]
S = np.array([list(input()) for i in range(H)])
M = 2*H*W
Distance = np.ones((H,W))*M
Distance[CH,CW] = 0
[nowH,nowW] = [CH,CW]
q0 = deque([])
q0.append([nowH,nowW])
q1 = deque([])
while len(q0) != 0 or len(q1) != 0:
  if len(q0) != 0:
    [nowH,nowW] = q0.popleft()
  else:
    [nowH,nowW] = q1.popleft()
  for i in range(-2,3):
    for j in range(-2,3):
      if nowH+i >= 0 and nowW+j >= 0 and nowH+i < H and nowW+j < W:
        if (abs(i) + abs(j)) == 1:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              q0.append([nowH+i,nowW+j])
              if [nowH+i,nowW+j] in q1:
                q1.remove([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW],Distance[nowH+i,nowW+j])
        elif (abs(i) + abs(j)) >= 2:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              q1.append([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW]+1,Distance[nowH+i,nowW+j])       
if Distance[DH,DW] == H*W:
  print(-1)
else:
  print(int(Distance[DH,DW]))

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
H,W = map(int, input().split())
CH,CW = map(int, input().split())
DH,DW = map(int, input().split())
[CH,CW,DH,DW] = [CH-1,CW-1,DH-1,DW-1]
S = np.array([list(input()) for i in range(H)])
M = 2*H*W
Distance = np.ones((H,W))*M
Distance[CH,CW] = 0
[nowH,nowW] = [CH,CW]
q0 = deque([])
q0.append([nowH,nowW])
q1 = deque([])
while len(q0) != 0 or len(q1) != 0:
  if len(q0) != 0:
    [nowH,nowW] = q0.popleft()
  else:
    [nowH,nowW] = q1.popleft()
  for i in range(-2,3):
    for j in range(-2,3):
      if nowH+i >= 0 and nowW+j >= 0 and nowH+i < H and nowW+j < W:
        if (abs(i) + abs(j)) == 1:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              q0.append([nowH+i,nowW+j])
              if [nowH+i,nowW+j] in q1:
                q1.remove([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW],Distance[nowH+i,nowW+j])
        elif (abs(i) + abs(j)) >= 2:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == H*W:
              q1.append([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW]+1,Distance[nowH+i,nowW+j])       
if Distance[DH,DW] == H*W:
  print(-1)
else:
  print(int(Distance[DH,DW]))

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
H,W = map(int, input().split())
CH,CW = map(int, input().split())
DH,DW = map(int, input().split())
[CH,CW,DH,DW] = [CH-1,CW-1,DH-1,DW-1]
S = np.array([list(input()) for i in range(H)])
M = H*W
Distance = np.ones((H,W))*M
Distance[CH,CW] = 0
[nowH,nowW] = [CH,CW]
q0 = deque([])
q0.append([nowH,nowW])
q1 = deque([])
while len(q0) != 0 or len(q1) != 0:
  if len(q0) != 0:
    [nowH,nowW] = q0.popleft()
  else:
    [nowH,nowW] = q1.popleft()
  for i in range(-2,3):
    for j in range(-2,3):
      if nowH+i >= 0 and nowW+j >= 0 and nowH+i < H and nowW+j < W:
        if (abs(i) + abs(j)) == 1:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              q0.append([nowH+i,nowW+j])
              if [nowH+i,nowW+j] in q1:
                q1.remove([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW],Distance[nowH+i,nowW+j])
        elif (abs(i) + abs(j)) >= 2:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == H*W:
              q1.append([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW]+1,Distance[nowH+i,nowW+j])
print(Distance)            
if Distance[DH,DW] == H*W:
  print(-1)
else:
  print(int(Distance[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 = [input() for i in range(H)]

dist = [[10**9+7 for _ in range(W)] for _ in range(H)]
Ch = Ch-1
Cw = Cw-1
Dh = Dh-1
Dw = Dw-1

queue = []
queue.append([Ch,Cw])
queue2 = []
dist[Ch][Cw] = 0

walk = [[0,1],[1,0],[0,-1],[-1,0]]
    
while len(queue) > 0:
    while len(queue) > 0:
        x, y = queue.pop(0)
        d = dist[x][y]
        flag = 0
        for vx,vy in walk:
            nx = x + vx
            ny = y + vy
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                if S[nx][ny] == '.':
                    if dist[nx][ny] > d:
                        dist[nx][ny] = d
                        queue.append([nx,ny])
                else:
                        flag += 1
        if flag:
            queue2.append([x,y])
            
    while len(queue2) > 0:
        x, y = queue2.pop(0)
        for vx in range(-2,3):
            for vy in range(-2,3):
                nx = x + vx
                ny = y + vy
                if 0 <= nx and nx < H and 0 <= ny and ny< W:
                    if S[nx][ny] == '.' and dist[nx][ny] == 10**9+7:
                        dist[nx][ny] = dist[x][y] + 1
                        queue.append([nx,ny])
                
print(dist[Dh][Dw])

Submission status: Wrong Answer

Solution code:
# D - Wizard in Maze
import sys
from collections import deque
from typing import List, Tuple


class WarpableMaze:
    __slots__ = ["height", "width", "start", "goal", "road", "wall", "grid"]

    def __init__(
        self,
        height: int,
        width: int,
        start: Tuple[int, int],
        goal: Tuple[int, int],
        grid: List[str],
        road: str = ".",
        wall: str = "#",
    ) -> None:
        # Values of start and goal must be 0-origin.
        self.height = height + 4
        self.width = width + 4
        self.start = self._flatten_coordinate(*start)
        self.goal = self._flatten_coordinate(*goal)
        self.road = road
        self.wall = wall
        self.grid = self._flatten_grid(grid)

    def _flatten_coordinate(self, h: int, w: int) -> int:
        return self.width * (h + 2) + w + 2

    def _flatten_grid(self, grid: List[str]) -> str:
        flat_grid = self.wall * self.width * 2
        for row in grid:
            flat_grid += self.wall * 2 + row + self.wall * 2
        flat_grid += self.wall * self.width * 2
        return flat_grid

    def bfs(self) -> int:
        w = self.width
        move = (-w, w, -1, 1)
        warp = [-2 * w - 2, -2 * w - 1, -2 * w, -2 * w + 1, -2 * w + 2]
        warp.extend([-w - 2, -w - 1, -w + 1, -w + 2, -2, 2])
        warp.extend([w - 2, w - 1, w + 1, w + 2])
        warp.extend([2 * w - 2, 2 * w - 1, 2 * w, 2 * w + 1, 2 * w + 2])

        unsearched = 1 << 30
        dist = [unsearched] * (self.height * self.width)
        dist[self.start] = 0
        queue = deque([self.start])
        while queue:
            x = queue.popleft()
            if x == self.goal:
                break
            cur_dist = dist[x]

            for dx in move:
                nx = x + dx
                if self.grid[nx] == self.wall:
                    continue
                if dist[nx] > cur_dist:
                    dist[nx] = cur_dist
                    queue.appendleft(nx)

            for dx in warp:
                nx = x + dx
                if self.grid[nx] == self.wall:
                    continue
                if dist[nx] > cur_dist + 1:
                    dist[nx] = cur_dist + 1
                    queue.append(nx)

        return dist[self.goal] if dist != unsearched else -1

    def debug(self):
        print(f"<DEBUG>\nstart={self.start}, goal={self.goal}", file=sys.stderr)
        for row in zip(*[iter(self.grid)] * self.width):
            print(*row, file=sys.stderr)


def main():
    H, W, CH, CW, DH, DW, *S = open(0).read().split()
    start, goal = (int(CH) - 1, int(CW) - 1), (int(DH) - 1, int(DW) - 1)
    maze = WarpableMaze(int(H), int(W), start, goal, S)
    # maze.debug()
    print(maze.bfs())


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
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=[list(input()) for _ in range(h)]

dy=[1, 0, -1, 0]
dx=[0, 1, 0 ,-1]
my=[-2, -1,  0,  1,  2, -2, -1,  0,  1,  2, -2, -1, 1, 2, -2, -1, 0, 1, 2, -2, -1,  0,  1,  2]
mx=[-2, -2, -2, -2, -2, -1, -1, -1, -1, -1,  0,  0, 0, 0,  1,  1, 1, 1, 1,  2,  2,  2,  2,  2]

from collections import deque

d=[[float("inf")]*w for _ in range(h)]
queue=deque()
queue.append((ch, cw))
d[ch][cw]=0

while queue:
    y,x=queue.popleft()

    for d_y, d_x in zip(dy, dx):
        new_y=y+d_y
        new_x=x+d_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]>d[y][x]:
            d[new_y][new_x]=d[y][x]
            queue.append((new_y, new_x))

    for m_y, m_x in zip(my, mx):
        new_y=y+m_y
        new_x=x+m_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]==float("inf"):
            d[new_y][new_x]=d[y][x]+1
            queue.appendleft((new_y, new_x))

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

Submission status: Wrong Answer

Solution code:
from collections import*
INF=10**18
h,w=map(int,input().split())
sh,sw=map(int,input().split())
gh,gw=map(int,input().split())
s=[input() for _ in range(h)]
q=deque([(sh-1,sw-1,1)])
d=[[INF]*w for _ in range(h)]
dx=[1,0,-1,0]
dy=[0,-1,0,1]
wx=[-2,-1,0,1,2]
wy=[-2,-1,0,1,2]
while q:
  x,y,c=q.popleft()
  if d[x][y]!=INF:continue
  d[x][y]=c
  for i,j in zip(dx,dy):
    nx=x+i
    ny=y+j
    if not(0<=nx<h and 0<=ny<w):continue
    if s[nx][ny]=='.' and d[nx][ny]==INF:
      q.appendleft((nx,ny,c))
  for i in wx:
    nx=x+i
    if not(0<=nx<h):continue
    for j in wy:
      ny=y+j
      if not(0<=ny<w):continue
      if s[nx][ny]=='.' and d[nx][ny]==INF:
        q.append((nx,ny,c+1))
print(d[gh-1][gw-1]if d[gh-1][gw-1]!=INF else -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 _ in range(h)]

ch-=1
cw-=1
dh-=1
dw-=1

dy=[1, 0, -1, 0]
dx=[0, 1, 0 ,-1]
my=[-2, -1,  0,  1,  2, -2, -1,  0,  1,  2, -2, -1, 1, 2, -2, -1, 0, 1, 2, -2, -1,  0,  1,  2]
mx=[-2, -2, -2, -2, -2, -1, -1, -1, -1, -1,  0,  0, 0, 0,  1,  1, 1, 1, 1,  2,  2,  2,  2,  2]

from collections import deque

d=[[float("inf")]*w for _ in range(h)]
queue=deque()
queue.append((ch, cw))
d[ch][cw]=0

while queue:
    y,x=queue.popleft()

    for d_y, d_x in zip(dy, dx):
        new_y=y+d_y
        new_x=x+d_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]>d[y][x]:
            d[new_y][new_x]=d[y][x]
            queue.append((new_y, new_x))

    for m_y, m_x in zip(my, mx):
        new_y=y+m_y
        new_x=x+m_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]==float("inf"):
            d[new_y][new_x]=d[y][x]+1
            queue.append((new_y, new_x))
print(-1 if d[dh][dw]==float("inf") else d[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 _ in range(h)]

ch-=1
cw-=1
dh-=1
dw-=1

dy=[1, 0, -1, 0]
dx=[0, 1, 0 ,-1]
my=[-2, -1,  0,  1,  2, -2, -1,  0,  1,  2, -2, -1, 1, 2, -2, -1, 0, 1, 2, -2, -1,  0,  1,  2]
mx=[-2, -2, -2, -2, -2, -1, -1, -1, -1, -1,  0,  0, 0, 0,  1,  1, 1, 1, 1,  2,  2,  2,  2,  2]

from collections import deque

d=[[float("inf")]*w for _ in range(h)]
queue=deque()
queue.append((ch, cw))
d[ch][cw]=0

while queue:
    y,x=queue.popleft()

    for d_y, d_x in zip(dy, dx):
        new_y=y+d_y
        new_x=x+d_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]<d[y][x]:
            d[new_y][new_x]=d[y][x]
            queue.append((new_y, new_x))

    for m_y, m_x in zip(my, mx):
        new_y=y+m_y
        new_x=x+m_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]==float("inf"):
            d[new_y][new_x]=d[y][x]+1
            queue.append((new_y, new_x))
print(-1 if d[dh][dw]==float("inf") else d[dh][dw])

Submission status: Wrong Answer

Solution code:
from collections import*
INF=10**18
h,w=map(int,input().split())
sh,sw=map(int,input().split())
gh,gw=map(int,input().split())
s=[input() for _ in range(h)]
q=deque([(sh-1,sw-1,1)])
d=[[INF]*w for _ in range(h)]
dx=[1,0,-1,0]
dy=[0,-1,0,1]
wx=[-2,-1,0,1,2]
wy=[-2,-1,0,1,2]
while q:
  x,y,c=q.popleft()
  if d[x][y]!=INF:continue
  d[x][y]=c
  for i,j in zip(dx,dy):
    nx=x+i
    ny=y+j
    if not(0<=nx<h and 0<=ny<w):continue
    if s[nx][ny]=='.' and d[nx][ny]==INF:
      q.appendleft((nx,ny,c))
  for i in wx:
    nx=x+i
    if not(0<=nx<h):continue
    for j in wy:
      ny=y+j
      if not(0<=ny<w):continue
      if s[nx][ny]=='.' and d[nx][ny]==INF:
        q.append((nx,ny,c+1))
print(d[gh-1][gw-1]if d[gh-1][gw-1]==INF else -1)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
H,W = map(int, input().split())
CH,CW = map(int, input().split())
DH,DW = map(int, input().split())
CH = CH -1
CW = CW -1
DH = DH -1
DW = DW -1
S = np.array([list(input()) for i in range(H)])
countWarp = np.ones((H,W))*H*W
nowH = CH
nowW = CW
countWarp[CH,CW] = 0
q = deque([])
q.append([nowH,nowW])
for n in range(0,H*W):
  tmp = q.popleft()
  nowH = tmp[0]
  nowW = tmp[1]
  for i in range(-2,3):
    for j in range(-2,3):
      if nowH+i >= 0 and nowW+j >= 0 and nowH+i < H and nowW+j < W:
        if (abs(i) + abs(j)) == 1:
          if S[nowH+i,nowW+j] == '.':
            if countWarp[nowH+i,nowW+j] == H*W:
              q.append([nowH+i,nowW+j])
            countWarp[nowH+i,nowW+j] = min(countWarp[nowH,nowW],countWarp[nowH+i,nowW+j])
        if (abs(i) + abs(j)) >= 2:
          if S[nowH+i,nowW+j] == '.':
            if countWarp[nowH+i,nowW+j] == H*W:
              q.append([nowH+i,nowW+j])
            countWarp[nowH+i,nowW+j] = min(countWarp[nowH,nowW]+1,countWarp[nowH+i,nowW+j])
  if len(q) == 0:
    break
if countWarp[DH,DW] == H*W:
  print(-1)
else:
  print(int(countWarp[DH,DW]))

Submission status: Wrong Answer

Solution code:
H, W = list(map(int, input().split()))
Ch, Cw = list(map(lambda x:int(x)+1, input().split()))
Dh, Dw = list(map(lambda x:int(x)+1, input().split()))
S = []

S.append(list('#'*(W+4)))
S.append(list('#'*(W+4)))
for i in range(H):
    S.append(list('#'*2+input()+'#'*2))
S.append(list('#'*(W+4)))
S.append(list('#'*(W+4)))

from collections import deque

q1 = deque()
q2 = deque()
inf = 10**6


#cost
T = []
for w in S:
    T_W = [-1 if s=='#' else inf for s in w]
    T.append(T_W)

# print(T)
move1 = [(1,0),(0,1),(-1,0),(0,-1)]
move2 = [(i-2,j-2) for i in range(5) for j in range(5)]
move2.remove((0,0))
for t in move1:
    move2.remove(t)
d = 0
h, w = Ch, Cw
T[Ch][Cw] = d
q1.append((h,w))
q2.append((h,w))


while len(q2)>0 or len(q1)>0:
    while len(q1)>0:
        v = q1.popleft()
        if v == (Dh,Dw):
            print(d)
            break
        for t in [(1,0),(0,1),(-1,0),(0,-1)]:
            h, w = v[0]+t[0], v[1]+t[1]
            if T[h][w] > d:
                T[h][w] = d
                q1.append((h,w))
                q2.append((h,w))
    d += 1
    while len(q2)>0:
        v = q2.popleft()
        if v == (Dh,Dw):
            print(d)
            break
        for t in move2:
            h, w = v[0]+t[0], v[1]+t[1]
            if T[h][w] > d:
                T[h][w] = d
                q1.append((h,w))
    q2.extend(q1)
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 = [input() for i in range(H)]

dist = [[10**9+7 for _ in range(W)] for _ in range(H)]
Ch2 = Ch-1
Cw2 = Cw-1
Dh2 = Dh-1
Dw2 = Dw-1

queue = []
queue.append([Ch2,Cw2])
queue2 = []
dist[Ch2][Cw2] = 0
    
while len(queue) > 0:
    while len(queue) > 0:
        x, y = queue.pop(0)
        d = dist[x][y]
        flag = 0
        for vx in range(-1,2):
            for vy in range(-1,2):
                if abs(vx) == abs(vy):
                    continue
                nx = x + vx
                ny = y + vy
                if 0 <= nx and nx < H and 0 <= ny and ny < W:
                    if S[nx][ny] == '.':
                        if dist[nx][ny] > d:
                            dist[nx][ny] = d
                            queue.append([nx,ny])
                    else:
                        flag += 1
        if flag:
            queue2.append([x,y])
            
    while len(queue2) > 0:
        x, y = queue2.pop(0)
        for vx in range(-2,3):
            for vy in range(-2,3):
                nx = x + vx
                ny = y + vy
                if 0 <= nx and nx < H and 0 <= ny and ny< W:
                    if S[nx][ny] == '.' and dist[nx][ny] == 10**9+7:
                        dist[nx][ny] = dist[x][y] + 1
                        queue.append([nx,ny])
                
print(dist[Dh2][Dw2])

Submission status: Wrong Answer

Solution code:
from collections import*
INF=10**18
h,w=map(int,input().split())
sh,sw=map(int,input().split())
gh,gw=map(int,input().split())
s=[input() for _ in range(h)]
q=deque([(sh-1,sw-1)])
d=[[INF]*w for _ in range(h)]
d[sh-1][sw-1]=0
dx=[1,0,-1,0]
dy=[0,-1,0,1]
wx=[-2,-1,0,1,2]
wy=[-2,-1,0,1,2]
while q:
  x,y=q.popleft()
  if (x,y)==(gh-1,gw-1):
    print(d[gh-1][gw-1])
    break
  for i,j in zip(dx,dy):
    nx=x+i
    ny=y+j
    if not(0<=nx<h and 0<=ny<w):continue
    if s[nx][ny]=='.' and d[nx][ny]==INF:
      d[nx][ny]=d[x][y]
      q.appendleft((nx,ny))
  for i in wx:
    nx=x+i
    if not(0<=nx<h):continue
    for j in wy:
      ny=y+j
      if not(0<=ny<w):continue
      if s[nx][ny]=='.' and d[nx][ny]==INF:
        d[nx][ny]=d[x][y]+1
        q.append((nx,ny))
else:print(-1)

Submission status: Wrong Answer

Solution code:
from itertools import product
 
def add_magic_move(enable_to_move_list):
  ret = list(enable_to_move_list)
  for h, w in enable_to_move_list:
    for target_h, target_w in product([h-1, h, h+1], [w-1, w, w+1]):
      if -1 < target_h < H and -1 < target_w < W and (target_h, target_w) not in enable_to_move_list:
        s[target_h][target_w] = '.'
        ret += [(target_h, target_w)]
  return ret
    
 
def get_enable_to_move_list(h, w, enable_to_move_list):
  if (h, w) in enable_to_move_list:
    return enable_to_move_list
  enable_to_move_list += [(h, w)]
  targets = ((h+1, w), (h-1, w), (h, w+1), (h, w-1))
  for h, w in targets:
    if -1 < h < H and -1 < w < W and s[h][w] == '.':
      enable_to_move_list = get_enable_to_move_list(h, w, enable_to_move_list)
  return enable_to_move_list
 
H, W = map(int, input().split())
s_h, s_w = [i-1 for i in map(int, input().split())]
d_h, d_w = [i-1 for i in map(int, input().split())]
s = [list(input()) for i in range(H)]
 
enable_to_move_list = get_enable_to_move_list(s_h, s_w, [])
i = 0
while True:
  if (d_h, d_w) in enable_to_move_list:
    break
  tmp = add_magic_move(enable_to_move_list)
  i += 1
  for h, w in set(tmp) - set(enable_to_move_list):
  	enable_to_move_list = get_enable_to_move_list(h, w, enable_to_move_list)
  if not set(tmp) ^ set(enable_to_move_list):
    i = -1
    break

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

dq = deque()
dq.append((start,0))
dist[start] = 0

while dq:
    p,d = dq.popleft()
    if dist[goal] <= dist[p]:
        break
    if d>dist[p]:
        break
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if abs(dy)+abs(dx)==1:
                    if dist[q]>dist[p]:
                        dist[q] = dist[p]
                        dq.appendleft((q,dist[q]))
                else:
                    if dist[q]>dist[p]+1:
                        dist[q] = dist[p] + 1
                        dq.append((q,dist[q]))

print(-1 if dist[goal]==10**10 else dist[goal])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
CY, CX = map(lambda x: int(x)-1, input().split())
DY, DX = map(lambda x: int(x)-1, input().split())

gridgraph = [input() for _ in range(H)]
q = deque()
q.append([CY, CX])
# 更新されるなら追加
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]
INF = 10**10
distant = [[INF]*W for _ in range(H)]
distant[CY][CX] = 0
while len(q):
    cy, cx = q.popleft()
    for dy, dx in adjacent:
        ny, nx = cy+dy, cx+dx
        if ny < 0 or ny >= H or nx < W or nx >= W:
            continue
        if gridgraph[ny][nx] == "." and distant[ny][nx] > distant[cy][cx]:
            distant[ny][nx] = distant[cy][cx]
            q.appendleft([ny, nx])
    for i in range(-2, 3, 1):
        for j in range(-2, 3, 1):
            ny, nx = cy+dy, cx+dx
            if ny < 0 or ny >= H or nx < W or nx >= W:
                continue
            if gridgraph[ny][nx] == "." and distant[ny][nx] > distant[cy][cx]+1:
                distant[ny][nx] = distant[cy][cx]+1
                q.append([ny, nx])
if distant[DY][DX] == INF:
    print(-1)
else:
    print(distant[DY][DX])