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:
#D
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
A= [list(input()) for _ in range(H)]
d= [ [ -1 for _ in range(W) ] for _ in range(H)]
f= [ [ False for _ in range(W) ] for _ in range(H)]
ans=0
cnt=0


v = deque([ [ch,cw] ])
d[ch][cw]=0
f[ch][cw]=True
move = [(1,0),(-1,0),(0,1),(0,-1)]  #y,xの順

while True:
    while v:
        a = v.pop()
        for mv in move:
            y = a[0]+mv[0]
            x = a[1]+mv[1]
            if 0<=y<=H-1 and 0<=x<=W-1:
                if d[y][x]== -1:
                    if A[y][x]==".":
                        d[y][x] = d[a[0]][a[1]]
                        v.append([y,x])
                        if y==dh and x==dw:
                            print(d[y][x])
                            exit()
    else:
        cnt +=1
        for i in range(0,W):
            for j in range(0,H):
                if d[j][i]==-1:
                    if A[j][i]==".":
                        d[j][i]=10**6
                        k = max(j-2,0)
                        l = min(j+2,H-1)
                        m = max(i-2,0)
                        n = min(i+2,W-1)
                        for s in range(m,n+1):
                            for t in range(k,l+1):
                                if d[t][s]>=0:
                                    d[j][i] = min(d[j][i],d[t][s]+1)
                        if d[j][i]==10**6:
                            d[j][i]=-2
                        else:
                            v.append([j,i])
                            if j==dh and i==dw:
                                print(d[j][i])
                                exit()
        else:
            if not v:
                print(-1)
                exit()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

mX = [0, 1, 0, -1]
mY = [1, 0, -1, 0]
zX = [2, 2, 2,  2, 2, 1, 1, 1, 1, 0,  0, -1, -1, -1, -1, -2, -2, -2, -2, -2]
zY = [2, 1, 0, -1, 2, 2, 1, -1, -2, 2, -2,  2, -2, 1, -1, 2,  1,  0, -1,  2]


def bfs(u, S, M, H, W):  # u 開始点

    q = deque()
    q.append(u)
    while q:
        u = q.popleft()

        # 徒歩移動
        for i in range(4):
            nx = u[0] + mX[i]
            ny = u[1] + mY[i]
            if nx < 0 or H <= nx:
                continue
            if ny < 0 or W <= ny:
                continue
            if S[nx][ny] == "#":
                continue

            if M[nx][ny] == -1 or M[nx][ny] > M[u[0]][u[1]]:  # state を確認
                M[nx][ny] = M[u[0]][u[1]]  # 徒歩移動
                q.append([nx, ny])

        # 魔法移動
        for i in range(20):
            wx = u[0] + zX[i]
            wy = u[1] + zY[i]
            if wx < 0 or H <= wx:
                continue
            if wy < 0 or W <= wy:
                continue
            if S[wx][wy] == "#":
                continue
            if M[wx][wy] == -1:  # state を確認
                M[wx][wy] = M[u[0]][u[1]] + 1
                q.append([wx, wy])


def main():

    H, W = map(int, sys.stdin.readline().rstrip().split())
    Ch, Cw = map(int, sys.stdin.readline().rstrip().split())
    Dh, Dw = map(int, sys.stdin.readline().rstrip().split())

    S = []
    for i in range(H):
        S.append(sys.stdin.readline().rstrip())

    M = [[-1 for _ in range(W)] for _ in range(H)]

    if S[Ch - 1][Cw - 1] == "#":
        print(-1)
        return

    M[Ch - 1][Cw - 1] = 0
    bfs([Ch - 1, Cw - 1], S, M, H, W)

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


main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(u, n, g):
    queue = deque([u])
    d = [None] * n  # uからの距離の初期化
    d[u] = 0  # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d


def main():
    h, w = map(int, input().split())
    c_h, c_w = map(lambda x: int(x) - 1, input().split())
    d_h, d_w = map(lambda x: int(x) - 1, input().split())
    s = [None] * h
    for i in range(h):
        s[i] = input()
    area = [[None] * w for i in range(h)]
    area_cnt = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue

            if i > 0 and area[i - 1][j] is not None:
                area[i][j] = area[i - 1][j]
            elif j > 0 and area[i][j - 1] is not None:
                area[i][j] = area[i][j - 1]
            else:
                area[i][j] = area_cnt
                area_cnt += 1

    c_area = area[c_h][c_w]
    d_area = area[d_h][d_w]

    if c_area == d_area:
        print(0)
        return

    can_move = [set([]) for _ in range(area_cnt)]
    for i in range(h):
        for j in range(w):
            if area[i][j] is None:
                continue
            for k in range(-2, 3):
                if i + k < 0 or area_cnt <= i + k:
                    continue
                for m in range(-2, 3):
                    try:
                        if j + m < 0 or area_cnt <= j + m:
                            continue
                        if area[i + k][j + m] is None:
                            continue
                        if area[i][j] != area[i + k][j + m]:
                            can_move[area[i][j]].add(area[i + k][j + m])
                            can_move[area[i + k][j + m]].add(area[i][j])
                    except IndexError:
                        pass
    d = bfs(c_area, area_cnt, can_move)[d_area]
    if d is None:
        print(-1)
    else:
        print(d)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

h,w = map(int, sys.stdin.readline().rstrip("\n").split())
sh,sw = map(int, sys.stdin.readline().rstrip("\n").split())
sh,sw = sh-1,sw-1
gh,gw = map(int, sys.stdin.readline().rstrip("\n").split())
gh,gw = gh-1,gw-1
labyrinth = [ line.rstrip("\n") for line in sys.stdin ]
done = [[False]*w for _ in range(h)]
move = [(1,0),(-1,0),(0,1),(0,-1)]
warp = [(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(2,1),(2,2),(1,2),(0,2),(-2,2),(-1,2),(-2,1),(-2,0),(-2,-1),(-2,-2),(-1,-2),(0,-2),(1,-2),(2,-2),(2,-1)]

d = deque()
d.append((sh,sw,0))
done[sh][sw] = True
warpmin = -1
while d:
    ph,pw,pwarp = d.popleft()
    if not done[ph][pw] :
        done[ph][pw] = True
    if ph == gh and pw == gw:
        warpmin = pwarp
        break
    cm = 0
    for m in move:
        nh,nw = ph+m[0],pw+m[1]
        if 0<=nh<h and 0<=nw<w and labyrinth[nh][nw] == '.' and (not done[nh][nw]):
            done[nh][nw] = True
            d.appendleft((nh,nw,pwarp))
            cm = 1
    if cm == 0:
        for m in warp:
            nh,nw = ph+m[0],pw+m[1]
            if 0<=nh<h and 0<=nw<w and labyrinth[nh][nw] == '.' and (not done[nh][nw]):
                d.append((nh,nw,pwarp+1))

print(warpmin)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
c = list(map(int,input().split()))
d = list(map(int,input().split()))
s = [list(input()) for _ in range(h)]

c[0] -= 1
c[1] -= 1
d[0] -= 1
d[1] -= 1

stack = []
q = [[c, 0]]
ans = -1
dt = [[h*w for _ in range(w)] for _ in range(h)]
dt[c[0]][c[1]] = 0
for ii in range(h):
  for jj in range(w):
    pos = [ii,jj]
    time = dt[ii][jj]
    for i in range(-2,3):
      for j in range(-2,3):
        if i==0 and j==0:
          continue
        elif (i==0 and j >=-1 and j <= 1) or (j==0 and i >=-1 and i <= 1):
          if (pos[0]+i>-1 and pos[0]+i<h and pos[1]+j>-1 and pos[1]+j<w
              and s[pos[0]+i][pos[1]+j]=="." and dt[pos[0]+i][pos[1]+j]>time):
            dt[pos[0]+i][pos[1]+j] = time
        else:
          if (pos[0]+i>-1 and pos[0]+i<h and pos[1]+j>-1 and pos[1]+j<w
              and s[pos[0]+i][pos[1]+j]=="." and dt[pos[0]+i][pos[1]+j]>time+1):
            dt[pos[0]+i][pos[1]+j] = time+1

ans = dt[d[0]][d[1]]
if ans >= h*w:
  ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
maze=[]

for i in range(H):
  l=list(input())
  for j in range(len(l)):
    if l[j]=='.':l[j]=-1
    if l[j]=='#':l[j]=-2
  maze.append(l)
update_list=[]
def isIn(h,w):
  if h<0 or h>=H or w<0 or w >=W:return False
  return True
def update(maze,h,w,value):
  global update_list
  vectors=[[-1,0],[1,0],[0,1],[0,-1]]
  maze[h][w]=value
  update_list=[]
  u=[]
  for i in range(25):
    if not isIn(h+i//5-2,w+i%5-2):continue
    if maze[h+i//5-2][w+i%5-2]>maze[h][w] or maze[h+i//5-2][w+i%5-2]==-1:
      if [h+i//5-2,w+i%5-2] not in u:
        u.append([h+i//5-2,w+i%5-2])
        maze[h+i//5-2][w+i%5-2]=value+1
  for vector in vectors:
    if not isIn(h+vector[0],w+vector[1]):continue
    if maze[h+vector[0]][w+vector[1]]>maze[h][w] or maze[h+vector[0]][w+vector[1]]==-1:
      maze[h+vector[0]][w+vector[1]]=maze[h][w]
      update(maze,h+vector[0],w+vector[1],value)
      
  for h,w in u:
    if maze[h][w]==value+1 and not [h,w] in update_list:
      update_list.append([h,w])

update(maze,Ch-1,Cw-1,0)
while update_list:
  for h,w in update_list:
    update(maze,h,w,maze[h][w])
print(maze[Dh-1][Dw-1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

input=sys.stdin.readline

H,W=list(map(int,input().split()))

sh,sw = list(map(int,input().split()))
gh,gw = list(map(int,input().split()))

sh-=1
sw-=1
gh-=1
gw-=1

c=[]
seen=[]
for i in range(H):
    c+=[input()]
    seen+=[[False]*W]

dx=[1,0,-1,0]
dy=[0,1,0,-1]

hop=0
ans=10000000

def dfs(c,h,w,hop):
    global seen,dx,dy,H,W,ans
    seen[h][w]=True
    #print(h,w,hop)

    for i in range(4):
        nh=h+dy[i]
        nw=w+dx[i]

        if nh<0 or nh>=H or nw<0 or nw>=W:
            continue
        if c[nh][nw] == "#":
            for j in range(-2,3):
                for k in range(-2,3):
                    if not ((j==1 and k==0)or(j==0 and k==1)or(j==-1 and k==0)or(j==0 and k==-1)or(j==0 and k==0)):
                        if 0<=h+j and h+j<H and 0<=w+k and w+k<W:
                            if c[h+j][w+k]=="." and seen[h+j][w+k]==False:
                                nh=h+j
                                nw=w+k
                                hop+=1
                                if nh==gh and nw==gw:
                                    seen[nh][nw]=True
                                    if ans>hop:
                                        ans=hop
                                    return True
                                else:
                                    dfs(c,nh,nw,hop)    
            continue
        if seen[nh][nw]:
            continue
        if nh==gh and nw==gw:
            seen[nh][nw]=True
            if ans>hop:
                ans=hop
            return True
        if dfs(c,nh,nw,hop):
            return True

dfs(c,sh,sw,hop)
if seen[gh][gw]:
    print(ans)
else:
    print("-1")

Submission status: Wrong Answer

Solution code:
from collections import deque
from sys import stdin
input=stdin.readline
n,m=map(int,input().split())
a,b=map(int,input().split())
x,y=map(int,input().split())
x=x-1
y=y-1
arr=[]
from math import inf
for i in range(n):
    arr.append(list(input().strip()))
def isvalid(x,y):
    if x<0 or y<0 or x>=n or y>=m or arr[x][y]=="#" or vis[x][y]==1:
        return False
    return True
vis=[[0]*m for i in range(n)]
stack=deque([[a-1,b-1,0]])
mi=inf
while(stack):
    xx,yy,cost=stack.popleft()
    vis[xx][yy]=1

    if xx==x and yy==y:
        mi=min(mi,cost)

    for i in range(-2,3,1):
        for j in range(-2, 3, 1):
            if isvalid(xx+i,yy+j):
                if -1<=i<=1 and -1<=j<=1 and i!=j:
                    stack.append([xx+i,yy+j,cost])
                else:
                    stack.append([xx + i, yy + j, cost+1])
if mi==inf:
    print(-1)
else:
    print(mi)

Submission status: Wrong Answer

Solution code:
from collections import deque
import time


def f1(x,y,xa,ya):
    if reach[xa][ya] == -1 or reach[xa][ya] > reach[x][y]:
         if c[xa][ya] == ".":
            reach[xa][ya] = reach[x][y]
            r.append([xa,ya])
            q.append([xa,ya])

def f2(x,y,xa,ya):
    if 0 <= xa <= h+1 and 0 <= ya <= w+1:
    
        if reach[xa][ya] == -1 or reach[xa][ya] > reach[x][y] + 1:
            if c[xa][ya] == ".":
                reach[xa][ya] = reach[x][y] + 1
                q.append([xa,ya])

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

t0 = time.time()

c = [0]*(h+2)
for i in range(1,h+1):
    c[i] = [0] + list(input()) + [0]
c[0]  = [0]*(w+2)
c[-1] = [0]*(w+2)

reach = [[-1 for j in range(w+2)] for i in range(h+2)]
q = deque([])

reach[cx][cy] = 0
q.append([cx,cy])

ans = 0

while q:
    
    if time.time() - t0 >= 1.5:
        break

    
    
    x,y = q.popleft()
    
    r = deque()
    r.append([x,y])
    while r:
        xx,yy = r.popleft()
        
        f1(xx,yy,xx-1,yy)
        f1(xx,yy,xx+1,yy)
        f1(xx,yy,xx,yy-1)
        f1(xx,yy,xx,yy+1)
    
    for i in range(-2,3):
        for j in range(-2,3):
            f2(x,y,x+i,y+j)


print(reach[dx][dy])

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



def clear_maze(h, w, ch, cw, dh, dw, S):
    visited = [[-1] * w for _ in range(h)]
    visited[ch - 1][cw - 1] = 0
    queue = deque([[ch - 1 , cw - 1]])
    while queue:
        y, x = queue.popleft()
        if [y, x] == [dh - 1, dw - 1]:
            return visited[y][x]
        num = 0
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            n_y = y + i
            n_x = x + j
            if n_y >= 0 and n_y < h and n_x >= 0 and n_x < w and S[n_y][n_x] == '.':
                if visited[n_y][n_x] == -1:
                    visited[n_y][n_x] = visited[y][x]
                    queue.append([n_y, n_x])
                else:
                    visited[n_y][n_x] = min(visited[n_y][n_x], visited[y][x])
                # queue.append([n_y, n_x])
        for i in range(-2, 2 + 1):
            for j in range(-2, 2 + 1):
                if not [i, j] in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                    n_y = y + i
                n_x = x + j
                if n_y >= 0 and n_y < h and n_x >= 0 and n_x < w and S[n_y][n_x] == '.' and visited[n_y][n_x] == -1:
                    visited[n_y][n_x] = visited[y][x] + 1
                    queue.append([n_y, n_x])
    return -1

print(clear_maze(h, w, ch, cw, dh, dw, S))

Submission status: Wrong Answer

Solution code:
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

start = (Ch, Cw)

S = ['#'*(W+4)]
S.append('#'*(W+4))
for k in range(H):
  S.append('##' + input() + '##')
S.append('#'*(W+4))
S.append('#'*(W+4))

counter = [[-1 for _ in range(W+4)] for _ in range(H+4)]
for k in range(2, H+2):
  for j in range(2, W+2):
    if S[k][j] == '.':
      counter[k][j] = 10**6

counter[Ch][Cw] = 0

#print(counter)
#print(S)

now = [start]
for item in now:
  x = item[0]
  y = item[1]
  if counter[x+1][y] == 10**6:
    counter[x+1][y] = 0
    now.append((x+1, y))
  if counter[x][y+1] == 10**6:
    counter[x][y+1] = 0
    now.append((x, y+1))
  if counter[x-1][y] == 10**6:
    counter[x-1][y] = 0
    now.append((x-1, y))
  if counter[x][y-1] == 10**6:
    counter[x][y-1] = 0
    now.append((x, y-1))

#print(counter)
if counter[Dh][Dw] == 0:
  print(0)
  exit()
ans = 0
while counter[Dh][Dw] == 10**6:
  if len(now) == 0 and counter[Dh][Dw] == 10**6:
    print(-1)
    exit() 
  nextlist = []
  ans += 1
  for item in now:
    if item == (Dh, Dw):
      print(ans)
      exit()
    x = item[0]
    y = item[1]
    if counter[x+2][y+2] > ans:
      counter[x+2][y+2] = ans
      nextlist.append((x+2, y+2))
    if counter[x+2][y+1] > ans:
      counter[x+2][y+1] = ans
      nextlist.append((x+2, y+1))
    if counter[x+2][y] > ans:
      counter[x+2][y] = ans
      nextlist.append((x+2, y))
    if counter[x+2][y-1] > ans:
      counter[x+2][y-1] = ans
      nextlist.append((x+2, y-1))
    if counter[x+2][y-2] > ans:
      counter[x+2][y-2] = ans
      nextlist.append((x+2, y-2))
    if counter[x+1][y+2] > ans:
      counter[x+1][y+2] = ans
      nextlist.append((x+1, y+2))
    if counter[x+1][y-2] > ans:
      counter[x+1][y-2] = ans
      nextlist.append((x+1, y-2))
    if counter[x][y+2] > ans:
      counter[x][y+2] = ans
      nextlist.append((x, y+2))
    if counter[x][y-2] > ans:
      counter[x][y-2] = ans
      nextlist.append((x, y-2))
    if counter[x-2][y+2] > ans:
      counter[x-2][y+2] = ans
      nextlist.append((x-2, y+2))
    if counter[x-2][y+1] > ans:
      counter[x-2][y+1] = ans
      nextlist.append((x-2, y+1))
    if counter[x-2][y] > ans:
      counter[x-2][y] = ans
      nextlist.append((x-2, y))
    if counter[x-2][y-1] > ans:
      counter[x-2][y-1] = ans
      nextlist.append((x-2, y-1))
    if counter[x-2][y-2] > ans:
      counter[x-2][y-2] = ans
      nextlist.append((x-2, y-2))
    if counter[x-1][y+2] > ans:
      counter[x-1][y+2] = ans
      nextlist.append((x-1, y+2))
    if counter[x-1][y-2] > ans:
      counter[x-1][y-2] = ans
      nextlist.append((x-1, y-2))
  if len(nextlist) == 0:
    print(-1)
    exit()
  now = nextlist  
  for item in now:
    if item == (Dh, Dw):
      print(ans)
      exit()
    x = item[0]
    y = item[1]
    if counter[x+1][y] > ans:
      counter[x+1][y] = ans
      now.append((x+1, y))
    if counter[x][y+1] > ans:
      counter[x][y+1] = ans
      now.append((x, y+1))
    if counter[x-1][y] > ans:
      counter[x-1][y] = ans
      now.append((x-1, y))
    if counter[x][y-1] > ans:
      counter[x][y-1] = ans
      now.append((x, y-1))
  if ans > 200000:
    print(-1)
    exit()
print(ans)

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=[""]
for i in range(h):
    S.append("#"+input())
        
V=[[999999 for i in range(w+1)] for q in range(h+1)]

V[ch][cw]=0
que=[(ch,cw)]
head=0

    
def ex(nx,ny):
    return ((nx+1,ny),(nx-1,ny),(nx,ny+1),(nx,ny-1))

def ex3(nx,ny):
    return ((nx+1,ny+1),(nx-1,ny-1),(nx-1,ny+1),(nx+1,ny-1))

def ex2(nx,ny):
    return ((nx+1,ny+1),(nx-1,ny-1),(nx-1,ny+1),(nx+1,ny-1),(nx+1,ny),(nx-1,ny),(nx,ny+1),(nx,ny-1))

def calc(nx,ny):
    if S[nx][ny]==".":
        return 0
    else:
        return 1

while len(que)>head:
    now=que[head]
    head+=1
    x=now[0]
    y=now[1]
    if S[x][y]==".":
        for nex in  ((x+1,y+1),(x-1,y-1),(x-1,y+1),(x+1,y-1)):
            nx=nex[0]
            ny=nex[1]
            if 0<nx<=h and 0<ny<=w:
                flg=calc(nx,ny)
                if flg==0:
                    continue
                if V[x][y]+flg<V[nx][ny]:
                    V[nx][ny]= V[now[0]][now[1]]+flg
                    que.append((nx,ny))
        for nex in ((x+1,y),(x-1,y),(x,y+1),(x,y-1)):
            nx=nex[0]
            ny=nex[1]
            if 0<nx<=h and 0<ny<=w:
                flg=calc(nx,ny)
                if V[x][y]+flg<V[nx][ny]:
                    V[nx][ny]= V[x][y]+flg
                    que.append((nx,ny))
    else:
        for nex in ((x+1,y+1),(x-1,y-1),(x-1,y+1),(x+1,y-1),(x+1,y),(x-1,y),(x,y+1),(x,y-1)):
            nx=nex[0]
            ny=nex[1]
            if 0<nx<=h and 0<ny<=w:
                flg=calc(nx,ny)*1000000
                if V[x][y]+flg<V[nx][ny]:
                    V[nx][ny]= V[x][y]+flg
                    que.append((nx,ny))

if V[dh][dw]==999999:
    print(-1)
else:
    print(V[dh][dw])

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

H, W = map(int, input().split())
ori = list(map(int, input().split()))
dis = list(map(int, input().split()))
S = [0] * H
for i in range(H):
    S[i] = input()

D = 10 ** 7

def co_num(h, w):
    return h * W + w

row = []
col = []
dist = []
for h in range(H):
    for w in range(W):
        if S[h][w] == '#': continue
        for hh in range(3):
            if not 0 <= h + hh < H: continue
            for ww in range(-2, 3):
                if not (0 <= h + hh < H and 0 <= w + ww < W): continue
                if hh == ww == 0: continue
                if S[h+hh][w+ww] == '#': continue
                if abs(hh) + abs(ww) == 1:
                    d = 1
                else:
                    d = D
                row.append(co_num(h, w))
                col.append(co_num(h+hh, w+ww))
                dist.append(d)
                col.append(co_num(h, w))
                row.append(co_num(h+hh, w+ww))
                dist.append(d)
                
d = dijkstra(csr_matrix((dist, (row, col)), shape=[H*W, H*W]), directed=True, indices=co_num(ori[0]-1, ori[1]-1))

if d[co_num(dis[0]-1, dis[1]-1)] == np.inf:
    print(-1)
else:
    print(int(d[co_num(dis[0]-1, dis[1]-1)] // D))

# d.reshape([H, W])

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    Ch, Cw = (int(i)-1 for i in input().split())
    Dh, Dw = (int(i)-1 for i in input().split())
    A = [input() for i in range(H)]
    V = [-1]*((H-1)*W + W)  # 頂点i

    def bfs_2d(sy, sx, v):
        que = deque()
        V[sy*W+sx] = v
        que.append(sy*W+sx)
        d = ((0, -1), (0, 1), (-1, 0), (1, 0))
        while que:
            u = que.popleft()
            uh, uw = u//W, u % W
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if V[next_h*W+next_w] != -1:
                    continue
                if A[next_h][next_w] == '#':
                    continue
                V[next_h*W+next_w] = v
                que.append(next_h*W + next_w)

    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" or V[h*W+w] != -1:
                continue
            bfs_2d(h, w, vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#":
                continue
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h*W+w] == V[(h+dh)*W + w+dw]:
                        continue
                    if V[(h+dh)*W + w+dw] in used[V[h*W+w]]:
                        continue
                    G[V[h*W+w]].append(V[(h+dh)*W + w+dw])
                    used[V[h*W+w]].add(V[(h+dh)*W + w+dw])

    # print(V)
    # for i in range(vertex):
    #     print(G[i])

    def bfs(s, g, N):
        que = deque([0])
        dist = [-1]*N
        dist[s] = 0
        while que:
            v = que.popleft()
            for i in G[v]:
                if dist[i] != -1:
                    continue
                que.append(i)
                dist[i] = dist[v] + 1
        return dist[g]

    s = V[Ch*W+Cw]
    g = V[Dh*W+Dw]
    ans = bfs(s, g, vertex)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
from heapq import heapify, heappush, heappop
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]

def main():
    from builtins import int, map
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Ch, Cw = Ch - 1, Cw - 1
    Dh, Dw = Dh - 1, Dw - 1
    S = [list(input()) for _ in range(H)]
    num_con = {}
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                num_con[h, w] = None
    ncon_num = 0
    for h in range(H):
        for w in range(W):
            # 既に決まっていたらいらない
            if S[h][w] != '.' or num_con[h, w] != None:
                continue
            num_con[h, w] = ncon_num
            dist = defaultdict(lambda: float("inf"))
            dist[h, w] = 0
            queue = []
            heappush(queue, (0, (h, w)))
            visited = set({})

            while queue:
                d, (nh, nw) = heappop(queue)
                dist[nh, nw] = d
                num_con[nh, nw] = ncon_num
                visited.add((nh, nw))

                if dist[nh, nw] < d:
                    continue

                for i in range(4):
                    nnh, nnw = nh + dh[i], nw + dw[i]
                    if 0 <= nnh < H and 0 <= nnw < W and S[nnh][nnw] != '#':
                        if num_con[nnh, nnw] is None:
                            heappush(queue, (d + 1, (nnh, nnw)))
            else:
                ncon_num += 1 # 次

    if ncon_num == 1:
        print(0)
        exit()
            
    con_nodes = defaultdict(set)
    start_con, goal_con = None, None
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                con_nodes[num_con[h, w]].add((h, w))
                if (h, w) == (Ch, Cw):
                    start_con = num_con[h, w]
                if (h, w) == (Dh, Dw):
                    goal_con = num_con[h, w]
    ncon = len(con_nodes)

    # pair-wiseに調べる
    # print(ncon, start_con, goal_con)
    edges = [[] for _ in range(ncon)]
    dist_mat = [[float("inf")] * ncon for _ in range(ncon)]
    for g1 in range(ncon):
        for g2 in range(g1 + 1, ncon):
            flag = False
            for (h1, w1) in con_nodes[g1]:
                for (h2, w2) in con_nodes[g2]:
                    ddh = abs(h1 - h2)
                    ddw = abs(w1 - w2)
                    if ddh <= 2 and ddw <= 2:
                        flag = True
                        break
                if flag:
                    break
            if flag:
                edges[g1].append((g2, 1))
                edges[g2].append((g1, 1))

    # Dijkstra
    d = [float("inf")] * ncon
    used = [True] * ncon
    d[start_con] = 0
    used[start_con] = False
    edgelist = []
    for e in edges[start_con]:
        heappush(edgelist, e)
    
    while len(edgelist):
        minedge = heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edges[v]:
            if used[e[1]]:
                heappush(edgelist,[e[0]+d[v],e[1]])

    if d[goal_con] == float("inf"):
        print(-1)
    else:
        print(d[goal_con])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right
from copy import deepcopy

def grid_wall(grid, h, w, wall='#'):
    G = [[wall]*(w+2) for _ in range(h+2)]
    for hi in range(h):
        G[hi+1][1:w+1] = grid[hi]
    return G

def solve():
    H, W = MI()
    ch, cw = MI()
    dh, dw = MI()
    G = LLS(H)
    GW = grid_wall(G, H, W)
    GW[dh][dw] = 'G'
    # print(GW)

    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    d = deque([(ch, cw)])

    used = deepcopy(GW)
    used[ch][cw] = '#'
    mp = 0
    WP = deque([d])

    # for _ in range(5):
    while WP:
        # print('WP', WP)
        d = WP.popleft()
        e = deque(list(d))
        # print(d, mp)
        # print(mp, used)

        while d:
            h, w = d.popleft()

            for dh, dw in move:
                nh, nw = h+dh, w+dw
                if used[nh][nw] == '#':
                    continue
                elif used[nh][nw] == 'G':
                    print(mp)
                    return
                d.append((nh, nw))
                used[nh][nw] = '#'

        mp = mp + 1
        tmp = []
        while e:
            h, w = e.popleft()
            used[h][w] = '#'
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    nh, nw = dh+h, dw+w
                    if not 0 <= nh <= H or not 0 <= nw <= W:
                        continue
                    if used[nh][nw] == '#':
                        continue
                    elif used[nh][nw] == 'G':
                        print(mp)
                        return
                    # print(nh, nw, used[nh][nw])
                    tmp.append((nh, nw))
                    # print(WP)

                    # used[nh][nw] = '#'
        if not tmp:
            print(-1)
            return
        WP.append(deque(tmp))

    print(-1)

if __name__ == '__main__':
    solve()