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 = [int(a) for a in input().split()]
s = [int(a) for a in input().split()]
e = [int(a) for a in input().split()]
S = [None]*H
for h in range(H):
    S[h] = [1 if c=='.' else 0 for c in input()]
#print( H,W,s,e,S,sep='\n')
walk=[[] for _ in range(H*W)]
warp=[[] for _ in range(H*W)]
#print(walk,warp,sep='\n')
for i in range(H):
    for j in range(W):
        if S[i][j]==0:continue
        if i==0:
            if j==0:pass
            elif j==1:
                if S[i][j-1]:
                    walk[i*W+j].append(i*W+j-1)
                    walk[i*W+j-1].append(i*W+j)
            else:
                if S[i][j-1]:
                    walk[i*W+j].append(i*W+j-1)
                    walk[i*W+j-1].append(i*W+j)
                if S[i][j-2]:
                    warp[i*W+j].append(i*W+j-2)
                    warp[i*W+j-2].append(i*W+j)
        elif i==1:
            if j==0:
                if S[i-1][j]:
                    walk[i*W+j].append((i-1)*W+j)
                    walk[(i-1)*W+j].append(i*W+j)
            elif j==1:
                if S[i][j-1]:
                    walk[i*W+j].append(i*W+j-1)
                    walk[i*W+j-1].append(i*W+j)
                if S[i-1][j]:
                    walk[i*W+j].append((i-1)*W+j)
                    walk[(i-1)*W+j].append(i*W+j)
                if S[i-1][j-1]:
                    warp[i*W+j].append((i-1)*W+j-1)
                    warp[(i-1)*W+j-1].append(i*W+j)
            else:
                if S[i][j-1]:
                    walk[i*W+j].append(i*W+j-1)
                    walk[i*W+j-1].append(i*W+j)
                if S[i-1][j]:
                    walk[i*W+j].append((i-1)*W+j)
                    walk[(i-1)*W+j].append(i*W+j)
                if S[i-1][j-1]:
                    warp[i*W+j].append((i-1)*W+j-1)
                    warp[(i-1)*W+j-1].append(i*W+j)
                if S[i][j-2]:
                    warp[i*W+j].append(i*W+j-2)
                    warp[i*W+j-2].append(i*W+j)
                if S[i-1][j-2]:
                    warp[i*W+j].append((i-1)*W+j-2)
                    warp[(i-1)*W+j-2].append(i*W+j)
            if j<W-1:
                if S[i-1][j+1]:
                    warp[i*W+j].append((i-1)*W+j+1)
                    warp[(i-1)*W+j+1].append(i*W+j)
                if j<W-2:
                    if S[i-1][j+2]:
                        warp[i*W+j].append((i-1)*W+j+2)
                        warp[(i-1)*W+j+2].append(i*W+j)
        else:
            if j==0:
                if S[i-1][j]:
                    walk[i*W+j].append((i-1)*W+j)
                    walk[(i-1)*W+j].append(i*W+j)
                if S[i-2][j]:
                    warp[i*W+j].append((i-2)*W+j)
                    warp[(i-2)*W+j].append(i*W+j)
            elif j==1:
                if S[i][j-1]:
                    walk[i*W+j].append(i*W+j-1)
                    walk[i*W+j-1].append(i*W+j)
                if S[i-1][j]:
                    walk[i*W+j].append((i-1)*W+j)
                    walk[(i-1)*W+j].append(i*W+j)
                if S[i-1][j-1]:
                    warp[i*W+j].append((i-1)*W+j-1)
                    warp[(i-1)*W+j-1].append(i*W+j)
                if S[i-2][j]:
                    warp[i*W+j].append((i-2)*W+j)
                    warp[(i-2)*W+j].append(i*W+j)
                if S[i-2][j-1]:
                    warp[i*W+j].append((i-2)*W+j-1)
                    warp[(i-2)*W+j-1].append(i*W+j)
            else:
                if S[i][j-1]:
                    walk[i*W+j].append(i*W+j-1)
                    walk[i*W+j-1].append(i*W+j)
                if S[i-1][j]:
                    walk[i*W+j].append((i-1)*W+j)
                    walk[(i-1)*W+j].append(i*W+j)
                if S[i-1][j-1]:
                    warp[i*W+j].append((i-1)*W+j-1)
                    warp[(i-1)*W+j-1].append(i*W+j)
                if S[i][j-2]:
                    warp[i*W+j].append(i*W+j-2)
                    warp[i*W+j-2].append(i*W+j)
                if S[i-1][j-2]:
                    warp[i*W+j].append((i-1)*W+j-2)
                    warp[(i-1)*W+j-2].append(i*W+j)
                if S[i-2][j]:
                    warp[i*W+j].append((i-2)*W+j)
                    warp[(i-2)*W+j].append(i*W+j)
                if S[i-2][j-1]:
                    warp[i*W+j].append((i-2)*W+j-1)
                    warp[(i-2)*W+j-1].append(i*W+j)
                if S[i-2][j-2]:
                    warp[i*W+j].append((i-2)*W+j-2)
                    warp[(i-2)*W+j-2].append(i*W+j)
            if j<W-1:
                if S[i-1][j+1]:
                    warp[i*W+j].append((i-1)*W+j+1)
                    warp[(i-1)*W+j+1].append(i*W+j)
                if S[i-2][j+1]:
                    warp[i*W+j].append((i-2)*W+j+1)
                    warp[(i-2)*W+j+1].append(i*W+j)
                if j<W-2:
                    if S[i-1][j+2]:
                        warp[i*W+j].append((i-1)*W+j+2)
                        warp[(i-1)*W+j+2].append(i*W+j)
                    if S[i-2][j+2]:
                        warp[i*W+j].append((i-2)*W+j+2)
                        warp[(i-2)*W+j+2].append(i*W+j)

Submission status: Wrong Answer

Solution code:
H,W = [int(a) for a in input().split()]
s = [int(a) for a in input().split()]
e = [int(a) for a in input().split()]
S = [None]*H
for h in range(H):
    S[h] = [1 if c=='.' else 0 for c in input()]
#print( H,W,s,e,S,sep='\n')
walk=[[] for _ in range(H*W)]
warp=[[] for _ in range(H*W)]
#print(walk,warp,sep='\n')
for i in range(H):
    for j in range(W):
        if S[i][j]==0:continue
        if i==0:
            if j==0:pass
            elif j==1:
                if S[i][j-1]:
                    walk[i*W+j].append(i*W+j-1)
                    walk[i*W+j-1].append(i*W+j)
            else:
                if S[i][j-1]:
                    walk[i*W+j].append(i*W+j-1)
                    walk[i*W+j-1].append(i*W+j)
                if S[i][j-2]:
                    warp[i*W+j].append(i*W+j-2)
                    warp[i*W+j-2].append(i*W+j)
        elif i==1:
            if j==0:
                if S[i-1][j]:
                    walk[i*W+j].append((i-1)*W+j)
                    walk[(i-1)*W+j].append(i*W+j)
            elif j==1:
                if S[i][j-1]:
                    walk[i*W+j].append(i*W+j-1)
                    walk[i*W+j-1].append(i*W+j)
                if S[i-1][j]:
                    walk[i*W+j].append((i-1)*W+j)
                    walk[(i-1)*W+j].append(i*W+j)
                if S[i-1][j-1]:
                    warp[i*W+j].append((i-1)*W+j-1)
                    warp[(i-1)*W+j-1].append(i*W+j)
            else:
                if S[i][j-1]:
                    walk[i*W+j].append(i*W+j-1)
                    walk[i*W+j-1].append(i*W+j)
                if S[i-1][j]:
                    walk[i*W+j].append((i-1)*W+j)
                    walk[(i-1)*W+j].append(i*W+j)
                if S[i-1][j-1]:
                    warp[i*W+j].append((i-1)*W+j-1)
                    warp[(i-1)*W+j-1].append(i*W+j)
                if S[i][j-2]:
                    warp[i*W+j].append(i*W+j-2)
                    warp[i*W+j-2].append(i*W+j)
                if S[i-1][j-2]:
                    warp[i*W+j].append((i-1)*W+j-2)
                    warp[(i-1)*W+j-2].append(i*W+j)
            if j<W-1:
                if S[i-1][j+1]:
                    warp[i*W+j].append((i-1)*W+j+1)
                    warp[(i-1)*W+j+1].append(i*W+j)
                if j<W-2:
                    if S[i-1][j+2]:
                        warp[i*W+j].append((i-1)*W+j+2)
                        warp[(i-1)*W+j+2].append(i*W+j)
        else:
            if j==0:
                if S[i-1][j]:
                    walk[i*W+j].append((i-1)*W+j)
                    walk[(i-1)*W+j].append(i*W+j)
                if S[i-2][j]:
                    warp[i*W+j].append((i-2)*W+j)
                    warp[(i-2)*W+j].append(i*W+j)
            elif j==1:
                if S[i][j-1]:
                    walk[i*W+j].append(i*W+j-1)
                    walk[i*W+j-1].append(i*W+j)
                if S[i-1][j]:
                    walk[i*W+j].append((i-1)*W+j)
                    walk[(i-1)*W+j].append(i*W+j)
                if S[i-1][j-1]:
                    warp[i*W+j].append((i-1)*W+j-1)
                    warp[(i-1)*W+j-1].append(i*W+j)
                if S[i-2][j]:
                    warp[i*W+j].append((i-2)*W+j)
                    warp[(i-2)*W+j].append(i*W+j)
                if S[i-2][j-1]:
                    warp[i*W+j].append((i-2)*W+j-1)
                    warp[(i-2)*W+j-1].append(i*W+j)
            else:
                if S[i][j-1]:
                    walk[i*W+j].append(i*W+j-1)
                    walk[i*W+j-1].append(i*W+j)
                if S[i-1][j]:
                    walk[i*W+j].append((i-1)*W+j)
                    walk[(i-1)*W+j].append(i*W+j)
                if S[i-1][j-1]:
                    warp[i*W+j].append((i-1)*W+j-1)
                    warp[(i-1)*W+j-1].append(i*W+j)
                if S[i][j-2]:
                    warp[i*W+j].append(i*W+j-2)
                    warp[i*W+j-2].append(i*W+j)
                if S[i-1][j-2]:
                    warp[i*W+j].append((i-1)*W+j-2)
                    warp[(i-1)*W+j-2].append(i*W+j)
                if S[i-2][j]:
                    warp[i*W+j].append((i-2)*W+j)
                    warp[(i-2)*W+j].append(i*W+j)
                if S[i-2][j-1]:
                    warp[i*W+j].append((i-2)*W+j-1)
                    warp[(i-2)*W+j-1].append(i*W+j)
                if S[i-2][j-2]:
                    warp[i*W+j].append((i-2)*W+j-2)
                    warp[(i-2)*W+j-2].append(i*W+j)
            if j<W-1:
                if S[i-1][j+1]:
                    warp[i*W+j].append((i-1)*W+j+1)
                    warp[(i-1)*W+j+1].append(i*W+j)
                if S[i-2][j+1]:
                    warp[i*W+j].append((i-2)*W+j+1)
                    warp[(i-2)*W+j+1].append(i*W+j)
                if j<W-2:
                    if S[i-1][j+2]:
                        warp[i*W+j].append((i-1)*W+j+2)
                        warp[(i-1)*W+j+2].append(i*W+j)
                    if S[i-2][j+2]:
                        warp[i*W+j].append((i-2)*W+j+2)
                        warp[(i-2)*W+j+2].append(i*W+j)
#print(walk)
#print(warp)
from collections import deque
done = [0]*(H*W)
waiting_walk = deque()
waiting_warp = deque()
start=(s[0]-1)*W+s[1]-1
end=(e[0]-1)*W+e[1]-1
done[start] = 1
#print(start)
cnt=0
for n in warp[start]:
    waiting_warp.append(n)
for n in walk[start]:
    waiting_walk.append(n)
    if n==end:
        waiting_walk=[]
        waiting_warp=[]
warping=0
if len(waiting_walk)==0:warping=1
found=0
while len(waiting_walk) or len(waiting_warp):
    if warping:
        #print("warping")
        for i in range(len(waiting_warp)):
            to=waiting_warp[i]
            #print(to)
            if to==end:
                found=1
                cnt+=1
                break
            if done[to]!=1:
                waiting_walk.append(to)
        if to==end:break
        warping=0
        cnt+=1
        waiting_warp.clear()
    else:
        cur_node = waiting_walk.popleft()
        if done[cur_node]!=1:
            done[cur_node]=1
            #print(cur_node)
            if cur_node==end:
                found=1
                #print("found")
                break
            for n in walk[cur_node]:
                if done[n]!=1:
                    waiting_walk.append(n)
            for n in warp[cur_node]:
                if done[n]!=1:
                    waiting_warp.append(n)
        if len(waiting_walk)==0:warping=1
if found:print(cnt)
else:print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = list(map(int,input().split()))
start = list(map(lambda x:int(x)-1,input().split()))
goal = list(map(lambda x:int(x)-1,input().split()))
A = [input() for _ in range(H)]
visited = [[0]*W for _ in range(H)]
B = deque([[start[0],start[1],0]])
warp = []
for i in range(-2,3):
    for j in range(-2,3):
            warp.append([i,j])

num = 0
# print(start,warp)
while 1:
    y,x,n = B.popleft()
    if visited[y][x] == 1:continue
    if [y,x] == goal:
        num = n
        break
    visited[y][x] = 1
    for dy,dx in [[1,0],[0,1],[-1,0],[0,-1]]:
        if (y+dy<=0)|(x+dx<=0)|(y+dy>=H)|(x+dx>=W):continue
        if (A[y+dy][x+dx]==".")&(visited[y+dy][x+dx]==0):
            B.appendleft([y+dy,x+dx,n])
    for dy,dx in warp:
        if (y+dy<=0)|(x+dx<=0)|(y+dy>=H)|(x+dx>=W):continue
        if (A[y+dy][x+dx]==".")&(visited[y+dy][x+dx]==0):
            B.append([y+dy,x+dx,n+1])
    if not B:
        num = -1
        break

print(num)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = list(map(int,input().split()))
start = list(map(lambda x:int(x)-1,input().split()))
goal = list(map(lambda x:int(x)-1,input().split()))
A = [input() for _ in range(H)]
visited = [[0]*W for _ in range(H)]
B = deque([[start[0],start[1],0]])
warp = []
for i in range(-2,3):
    for j in range(-2,3):
        if (abs(i)>=2)|(abs(j)>=2):
            warp.append([i,j])

num = 0
# print(start,warp)
while 1:
    y,x,n = B.popleft()
    if visited[y][x] == 1:continue
    if [y,x] == goal:
        num = n
        break
    visited[y][x] = 1
    for dy,dx in [[1,0],[0,1],[-1,0],[0,-1]]:
        if (y+dy<=0)|(x+dx<=0)|(y+dy>=H)|(x+dx>=W):continue
        if (A[y+dy][x+dx]==".")&(visited[y+dy][x+dx]==0):
            B.appendleft([y+dy,x+dx,n])
    for dy,dx in warp:
        if (y+dy<=0)|(x+dx<=0)|(y+dy>=H)|(x+dx>=W):continue
        if (A[y+dy][x+dx]==".")&(visited[y+dy][x+dx]==0):
            B.append([y+dy,x+dx,n+1])
    if not B:
        num = -1
        break

print(num)

Submission status: Wrong Answer

Solution code:
def l():
    return [int(x) for x in input().split()]
def main():
    H,W=l()
    ch,cw=l()
    dh,dw=l()
    ch-=1
    cw-=1
    dw-=1
    dh-=1
    s=[[-2 if x=='#' else -1 for x in list(input())] for _ in range(H)]
    pad1=[-2,-2]
    pad2=[[-2]*(W+4)]*2
    s=pad2+[pad1+x+pad1 for x in s]+pad2
    move1=[(-1,0),(1,0),(0,-1),(0,1)]
    move2=list(set([(i,j) for i in range(-2,3) for j in range(-2,3)])-set(move1)-set([(0,0)]))
    q1=[(0,ch+2,cw+2)]
    q2=[]
    s[ch+2][cw+2]=0
    def mark(c,h,w):
        if 0<=h<H and 0<=w<W and s[h][w]==-1:
        #if s[h][w]==-1:
            s[h][w]=c
            q1.append((c,h,w))
    while q1:
        #print(q1)
        c,h,w=q1.pop()
        for i,j in move1:
            mark(c,h+i,w+j)
        q2.append((c+1,h,w))
        if not q1:
            for c,h,w in q2:
                for i,j in move2:
                    mark(c,h+i,w+j)
            q2=[]
    ans=s[dh+2][dw+2]
    if ans>=0:
        print(ans)
    else:
        print(-1)
main()

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs():
  d = [[float('inf')]*w for i in range(h)]
  
  dx = [1, 0, -1, 0]
  dy = [0, 1, 0, -1]
  
  que = deque([])
  que.append((ch, cw))
  d[ch][cw] = 0
  
  while que:
    p = que.popleft()
    if p[0]==dh and p[1]==dw:
      break
    for i in range(4):
      nx = p[0] + dx[i]
      ny = p[1] + dy[i]
      if 0<=nx<h and 0<=ny<w and maze[nx][ny]!='#' and d[nx][ny]==float('inf'):
        que.append((nx, ny))
        d[nx][ny] = d[p[0]][p[1]]
      elif 0<=nx<h and 0<=ny<w and maze[nx][ny]=='#':
        for j in range(-2, 3):
          for k in range(-2, 3):
            nx = p[0] + j
            ny = p[1] + k
            if 0<=nx<h and 0<=ny<w and maze[nx][ny]!='#' and d[nx][ny]==float('inf'):
              d[nx][ny] = d[p[0]][p[1]] + 1
              que.append((nx, ny))
              
  return d[dh][dw]


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
maze = [list(input()) for i in range(h)]

if bfs()!=float('inf'):
  print(bfs())
else:
  print(-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())
ch-=1
cw-=1
dh-=1
dw-=1

maze=[list(input()) for i in range(h)]
distance=[[10**10 for j in range(w)] for i in range(h)]

distance[ch][cw]=0


Q=deque()
Q.append((ch,cw,0))



while Q:
  p=Q.popleft()

  
  dx=[1,1,-1,-1]
  dy=[-1,1,-1,1]
  dddx=[0,0,2,-2,2,2,2,2,1,1,1,1,-2,-2,-2,-2,-1,-1,-1,-1]
  dddy=[2,-2,0,0,2,1,-1,-2,2,1,-1,-2,2,1,-1,-2,2,1,-1,-2]

  for i in range(4):
    nx=p[0]+dx[i]
    ny=p[1]+dy[i]

    if 0<=nx<h and 0<=ny<w and maze[nx][ny]!='#' and p[2]<distance[nx][ny]:
      Q.appendleft((nx,ny,p[2]))
      distance[nx][ny]=distance[p[0]][p[1]]


  for j in range(20):
    nnnx=p[0]+dddx[j]
    nnny=p[1]+dddy[j]

    if 0<=nnnx<h and 0<=nnny<w and maze[nnnx][nnny]!='#' and p[2]+1<distance[nnnx][nnny]:
      Q.append((nnnx,nnny,p[2]+1))
      distance[nnnx][nnny]=distance[p[0]][p[1]]+1


if distance[dh][dw]==10**10:
  print(-1)
  exit()


print(distance[dh][dw])

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())
ch-=1
cw-=1
dh-=1
dw-=1

maze=[list(input()) for i in range(h)]
distance=[[10**10 for j in range(w)] for i in range(h)]

distance[ch][cw]=0


Q=deque()
Q.append((ch,cw))



while Q:
  p=Q.popleft()

  
  dx=[1,1,-1,-1]
  dy=[-1,1,-1,1]
  dddx=[0,0,2,-2,2,2,2,2,1,1,1,1,-2,-2,-2,-2,-1,-1,-1,-1]
  dddy=[2,-2,0,0,2,1,-1,-2,2,1,-1,-2,2,1,-1,-2,2,1,-1,-2]

  for i in range(4):
    nx=p[0]+dx[i]
    ny=p[1]+dy[i]

    if 0<=nx<h and 0<=ny<w and maze[nx][ny]!='#' and distance[p[0]][p[1]]<distance[nx][ny]:
      Q.appendleft((nx,ny))
      distance[nx][ny]=distance[p[0]][p[1]]


  for j in range(20):
    nnnx=p[0]+dddx[j]
    nnny=p[1]+dddy[j]

    if 0<=nnnx<h and 0<=nnny<w and maze[nnnx][nnny]!='#' and distance[p[0]][p[1]]+1<distance[nnnx][nnny]:
      Q.append((nnnx,nnny))
      distance[nnnx][nnny]=distance[p[0]][p[1]]+1


if distance[dh][dw]==10**10:
  print(-1)
  exit()


print(distance[dh][dw])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
moveA_q = deque()
moveB_q = deque()
moveA_q.append([sW, sH])
moveB_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while moveA_q or moveB_q:
    if scores[gH][gW] != float('inf'):
        break
    # 移動AでBFS
    while moveA_q:
        x, y = moveA_q.pop()
        # moveB_q.append([x, y])
        for dx, dy in zip(dx_list, dy_list):
            nx, ny = x + dx, y + dy
            if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                continue
            # if scores[ny][nx] == float('inf'):
            if scores[ny][nx] > scores[y][x]:
                scores[ny][nx] = scores[y][x]
                moveA_q.append([nx, ny])
                moveB_q.append([nx, ny])

    # 移動bで動けるマスをmodeA_qに格納
    while moveB_q:
        x, y = moveB_q.pop()
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                    continue
                # if scores[ny][nx] == float('inf'):
                if scores[ny][nx] > scores[y][x]:
                    moveA_q.append([nx, ny])
                    scores[ny][nx] = scores[y][x] + 1

# print(*scores,sep='\n')
if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
moveA_q = deque()
moveB_q = deque()
moveA_q.append([sW, sH])
moveB_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while moveA_q or moveB_q:
    if scores[gH][gW] != float('inf'):
        break
    # 移動AでBFS
    while moveA_q:
        x, y = moveA_q.pop()
        for dx, dy in zip(dx_list, dy_list):
            nx, ny = x + dx, y + dy
            if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                continue
            # if scores[ny][nx] == float('inf'):
            if scores[ny][nx] > scores[y][x]:
                scores[ny][nx] = scores[y][x]
                moveA_q.append([nx, ny])
                moveB_q.append([nx, ny])

    # 移動bで動けるマスをmodeA_qに格納
    while moveB_q:
        x, y = moveB_q.pop()
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                    continue
                # if scores[ny][nx] == float('inf'):
                if scores[ny][nx] > scores[y][x]:
                    moveA_q.append([nx, ny])
                    scores[ny][nx] = scores[y][x] + 1

# print(*scores,sep='\n')
if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
moveA_q = deque()
moveB_q = deque()
moveA_q.append([sW, sH])
moveB_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while moveA_q or moveB_q:
    if scores[gH][gW] != float('inf'):
        break
    # 移動AでBFS
    while moveA_q:
        x, y = moveA_q.pop()
        # moveB_q.append([x, y])
        for dx, dy in zip(dx_list, dy_list):
            nx, ny = x + dx, y + dy
            if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                continue
            # if scores[ny][nx] == float('inf'):
            if scores[ny][nx] > scores[y][x]:
                scores[ny][nx] = scores[y][x]
                moveA_q.append([nx, ny])
                moveB_q.append([x, y])

    # 移動bで動けるマスをmodeA_qに格納
    while moveB_q:
        x, y = moveB_q.pop()
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                    continue
                # if scores[ny][nx] == float('inf'):
                if scores[ny][nx] > scores[y][x]:
                    moveA_q.append([nx, ny])
                    scores[ny][nx] = scores[y][x] + 1

# print(*scores,sep='\n')
if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])

Submission status: Wrong Answer

Solution code:
def l():
    return [int(x) for x in input().split()]
def main():
    H,W=l()
    ch,cw=l()
    dh,dw=l()
    ch-=1
    cw-=1
    dw-=1
    dh-=1
    s=[[-2 if x=='#' else -1 for x in list(input())] for _ in range(H)]
    move1=[(-1,0),(1,0),(0,-1),(0,1)]
    move2=list(set([(i,j) for i in range(-2,3) for j in range(-2,3)])-set(move1)-set([(0,0)]))
    q1=[(0,ch,cw)]
    q2=[]
    s[ch][cw]=0
    def mark(c,h,w):
        if 0<=h<H and 0<=w<W and s[h][w]==-1:
            s[h][w]=c
            q1.append((c,h,w))
    while q1:
        #print(q1)
        c,h,w=q1.pop()
        for i,j in move1:
            mark(c,h+i,w+j)
        q2.append((c+1,h,w))
        if not q1:
            for c,h,w in q2:
                for i,j in move2:
                    mark(c,h+i,w+j)
            q2=[]
    ans=s[dh][dw]
    if ans>=0:
        print(ans,s)
    else:
        print(-1)
main()

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
moveA_q = deque()
moveB_q = deque()
moveA_q.append([sW, sH])
moveB_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while moveA_q:
    if scores[gH][gW] != float('inf'):
        break
    # 移動AでBFS
    x, y = moveA_q.pop()
    # moveB_q.append([x, y])
    for dx, dy in zip(dx_list, dy_list):
        nx, ny = x + dx, y + dy
        if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
            continue
        if scores[ny][nx] == float('inf'):
            scores[ny][nx] = scores[y][x]
            moveA_q.append([nx, ny])
            moveB_q.append([x, y])
    if not moveA_q:
        # 移動bで動けるマスをmodeA_qに格納
        while moveB_q:
            x, y = moveB_q.pop()
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    nx, ny = x + dx, y + dy
                    if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                        continue
                    if scores[ny][nx] == float('inf'):
                        moveA_q.append([nx, ny])
                        scores[ny][nx] = scores[y][x] + 1

# print(*scores,sep='\n')
if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])

Submission status: Wrong Answer

Solution code:
from collections import deque
def l():
    return [int(x) for x in input().split()]
def main():
    H,W=l()
    ch,cw=l()
    dh,dw=l()
    ch-=1
    cw-=1
    dw-=1
    dh-=1
    s=[[-2 if x=='#' else -1 for x in list(input())] for _ in range(H)]
    move1=[(-1,0),(1,0),(0,-1),(0,1)]
    move2=list(set([(i,j) for i in range(-2,3) for j in range(-2,3)])-set(move1)-set([(0,0)]))
    q=deque([(0,ch,cw)])
    s[ch][cw]=0
    def mark(c,h,w,f):
        if not (0<=h<H and 0<=w<W):
            return
        c0=s[h][w]
        if c0==-2:
            return
        if c0==-1 or c0>c:
            s[h][w]=c
            f((c,h,w))
    while q:
        c,h,w=q.pop()
        for i,j in move1:
            mark(c,h+i,w+j,q.append)
        for i,j in move2:
            mark(c+1,h+i,w+j,q.appendleft)
    ans=s[dh][dw]
    if ans>=0:
        print(ans,s)
    else:
        print(-1)
main()

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
moveA_q = deque()
moveB_q = deque()
moveA_q.append([sW, sH])
moveB_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while moveA_q:
    if scores[gH][gW] != float('inf'):
        break
    # 移動AでBFS
    x, y = moveA_q.pop()
    moveB_q.append([x, y])
    for dx, dy in zip(dx_list, dy_list):
        nx, ny = x + dx, y + dy
        if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
            continue
        if scores[ny][nx] == float('inf'):
        # if scores[ny][nx] > scores[y][x]:
            scores[ny][nx] = scores[y][x]
            moveA_q.append([nx, ny])

    if not moveA_q:
        # 移動bで動けるマスをmodeA_qに格納
        while moveB_q:
            x, y = moveB_q.pop()
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    nx, ny = x + dx, y + dy
                    if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                        continue
                    if scores[ny][nx] == float('inf'):
                    # if scores[ny][nx] > scores[y][x]:
                        moveA_q.append([nx, ny])
                        scores[ny][nx] = scores[y][x] + 1

print(*scores,sep='\n')
if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
moveA_q = deque()
moveB_q = deque()
moveA_q.append([sW, sH])
moveB_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while moveA_q or moveB_q:
    if scores[gH][gW] != float('inf'):
        break
    # 移動AでBFS
    while moveA_q:
        x, y = moveA_q.pop()
        for dx, dy in zip(dx_list, dy_list):
            nx, ny = x + dx, y + dy
            if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                continue
            # if scores[ny][nx] == float('inf'):
            if scores[ny][nx] > scores[y][x]:
                scores[ny][nx] = scores[y][x]
                moveA_q.appendleft([nx, ny])
                moveB_q.append([nx, ny])

    # 移動bで動けるマスをmodeA_qに格納
    while moveB_q:
        x, y = moveB_q.pop()
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                    continue
                # if scores[ny][nx] == float('inf'):
                if scores[ny][nx] > scores[y][x]:
                    moveA_q.append([nx, ny])
                    scores[ny][nx] = scores[y][x] + 1

# print(*scores,sep='\n')
if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])