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 sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W = map(int, readline().split())
    sh, sw = map(int, readline().split())
    sh -= 1
    sw -= 1
    gh, gw = map(int, readline().split())
    gh -= 1
    gw -= 1
    S = [readline().rstrip() for _ in range(H)]
    
    dist = [[INF] * W for _ in range(H)]
    walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    warp = [(1, 1), (1, -1), (-1, 1), (-1, -1),
            (2, 0), (2, 1), (2, 2), (2, -1), (2, -2),
            (-2, 0), (-2, 1), (-2, 2), (-2, -1), (-2, -2),
            (0, 2), (1, 2), (-1, 2), (0, -2), (1, -2), (-1, -2)]
    
    Q = deque()
    Q.append((sh, sw))
    dist[sh][sw] = 0
    
    while Q:
        h, w = Q.popleft()
        if h == gh and w == gw:
            continue
        flag = 0
        d = dist[h][w]
        for dh, dw in walk:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if S[nh][nw] == '.':
                    if dist[nh][nw] > d:
                        dist[nh][nw] = d
                        Q.append((nh, nw))
                else:
                    flag = 1
        
        if flag:
            for dh, dw in warp:
                nh = h + dh
                nw = w + dw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                    if dist[nh][nw] > d + 1:
                        dist[nh][nw] = d + 1
                        Q.append((nh, nw))

    if dist[gh][gw] == INF:
        print(-1)
    else:
        print(dist[gh][gw])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
####################################################################
import sys
def _p(*_a):
  #return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
####################################################################
def _pa(_aa):
  #return
  for _a in _aa: _p(_a)
####################################################################
H,W = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
M = list( list(input()) for _ in range(H) )

INF = 10**18

for h in range(H):
  for w in range(W):
    if M[h][w] == ".": M[h][w] = INF
    # if M[h][w] == "#": M[h][w] = -1

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

M[ch][cw] = 0
# M[dh][dw] = "G"

# _pa(M)


from collections import deque
Q = deque()
Q.append((ch,cw))

ans = INF

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

  for ih,iw in [(1,0), (-1,0), (0,1), (0,-1)]:
    nh = h + ih
    nw = w + iw
    if nh < 0 or H <= nh: continue
    if nw < 0 or W <= nw: continue
    if M[nh][nw] == "#": continue

    if nh == dh and nw == dw:
      M[nh][nw] = min(M[h][w], M[dh][dw])
      ans = min(ans, M[nh][nw])
      continue

    if M[h][w] < M[nh][nw]:
      M[nh][nw] = M[h][w]
      Q.append((nh,nw))
      continue

    if M[h][w] > M[nh][nw]:
      M[h][w] = M[nh][nw]
      Q.append((h,w))

  for ih,iw in [(1,1), (1,-1), (-1,1), (-1,-1), (2,0), (2,1), (2,2), (2,-1), (2,-2), (1,2), (1,-2), (0,2), (0,-2), (-1,2), (-1,-2), (-2,0), (-2,1), (-2,-2), (-2,-1), (-2,-2)]:
    nh = h + ih
    nw = w + iw
    if nh < 0 or H <= nh: continue
    if nw < 0 or W <= nw: continue
    if M[nh][nw] == "#": continue

    if nh == dh and nw == dw:
      M[nh][nw] = min(M[h][w]+1, M[dh][dw])
      ans = min(ans, M[nh][nw])
      continue

    if M[h][w]+1 < M[nh][nw]:
      M[nh][nw] = M[h][w]+1
      Q.append((nh,nw))
      continue

    if M[h][w] > M[nh][nw]+1:
      M[h][w] = M[nh][nw]+1
      Q.append((h,w))

# _pa(M)

if ans == INF: ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

def bfs(x,y,z):
    if x == Dh and y == Dw:
        print(z)
        exit()
    F = 0
    dist[x][y] = 1
    que = deque([[x, y]])
    while que:
        h, w = que.pop()
        for dh, dw in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            nh = h + dh
            nw = w + dw
            if nh < 0 or nw < 0 or nh >= H or nw >= W:
                continue
            if maze[nh][nw] == '#':
                F = 1
                continue
            if dist[nh][nw] == -1:
                if nh == Dh and nw == Dw:
                    print(z)
                    exit()
                dist[nh][nw] = 1
                que.appendleft([nh, nw])
        if F == 1 and (h,w,z) not in li:
            li.append((h,w,z))
            que2.append((h,w,z))

H,W = I()
Ch,Cw = I()
Dh,Dw = I()
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
li = deque([])
maze = [list(s()) for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
dist[Ch][Cw] = 1
que = deque([[Ch, Cw]])
while que:
    F = 0
    h, w = que.pop()
    for dh, dw in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = h + dh
        nw = w + dw
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if maze[nh][nw] == '#':
            F = 1
            continue
        if dist[nh][nw] == -1:
            if nh == Dh and nw == Dw:
                print(0)
                exit()
            dist[nh][nw] = 1
            que.appendleft([nh, nw])
    if F == 1:
        li.append((h,w,0))
que2 = copy(li)
lis = [[2,2],[2,-2],[-2,2],[-2,-2],[2,1],[2,-1],[-2,1],[-2,-1],[1,2],[1,-2],[-1,2],[-1,-2],[2,0],[-2,0],[0,2],[0,-2],[1,1],[1,-1],[-1,1],[-1,-1]]
while que2:
    h,w,n = que2.pop()
    if h == Dh and w == Dw:
        print(n)
        exit()
    for dh, dw in lis:
        nh = h + dh
        nw = w + dw
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if maze[nh][nw] == '#':
            continue
        if dist[nh][nw] == -1:
            bfs(nh,nw,n+1)
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

def solve2(s_flag,h,w,dh,dw,que):
    while que:
        ch,cw=que.popleft()
        now=s_flag[ch][cw]
        for d_ch,d_cw in [(1,0),(0,1),(0,-1),(-1,0)]:
            if ch+d_ch<0 or h-1<ch+d_ch:
                continue
            if cw+d_cw<0 or w-1<cw+d_cw:
                continue
            dist=s_flag[ch+d_ch][cw+d_cw]
            if dist=='#': ## wall
                jump=[(d_ch*2,d_cw*2)]
                for tmp in range(1,3):
                    jump.append((d_ch*2+d_cw*tmp,d_cw*2+d_ch*tmp))
                    jump.append((d_ch*2-d_cw*tmp,d_cw*2-d_ch*tmp))
                for jump_ch,jump_cw in jump:
                    if ch+jump_ch<0 or h-1<ch+jump_ch:
                        continue
                    if cw+jump_cw<0 or w-1<cw+jump_cw:
                        continue
                    dist_jump=s_flag[ch+jump_ch][cw+jump_cw]
                    if dist_jump!='#' and dist_jump>now+1:
                        s_flag[ch+jump_ch][cw+jump_cw]=now+1
                        que.append([ch+jump_ch,cw+jump_cw])
            else:
                if dist>now:
                    s_flag[ch+d_ch][cw+d_cw]=now
                    que.append([ch+d_ch,cw+d_cw])
    return s_flag[dh][dw]

def solve(s_flag,h,w,ch,cw,jump_cnt):
    # print(ch,cw,jump_cnt)
    # print(s_flag)
    if s_flag[ch][cw]==-1:
        return [(ch,cw,jump_cnt)]
    s_flag[ch][cw]=1 ## 1:visited
    for d_ch,d_cw in [(1,0),(0,1),(0,-1),(-1,0)]:
        if ch+d_ch<0 or h-1<ch+d_ch:
            continue
        if cw+d_cw<0 or w-1<cw+d_cw:
            continue
        if s_flag[ch+d_ch][cw+d_cw]==2: ## 2:wall
            jump=[(d_ch*2,d_cw*2)]
            for tmp in range(1,3):
                jump.append((d_ch*2+d_cw*tmp,d_cw*2+d_ch*tmp))
                jump.append((d_ch*2-d_cw*tmp,d_cw*2-d_ch*tmp))
            for jump_ch,jump_cw in jump:
                if ch+jump_ch<0 or h-1<ch+jump_ch:
                    continue
                if cw+jump_cw<0 or w-1<cw+jump_cw:
                    continue
                if s_flag[ch+jump_ch][cw+jump_cw]<=0:
                    route=solve(s_flag,h,w,ch+jump_ch,cw+jump_cw,jump_cnt+1)
                    if route:
                        return [(ch,cw,jump_cnt)]+route
        elif s_flag[ch+d_ch][cw+d_cw]<=0: ## 0:road -1:goal
            route=solve(s_flag,h,w,ch+d_ch,cw+d_cw,jump_cnt)
            if route:
                return [(ch,cw,jump_cnt)]+route


def main():
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch,cw=ch-1,cw-1
    dh,dw=map(int,input().split())
    dh,dw=dh-1,dw-1
    s=[input() for i in range(h)]
    ## .=0 #=2 visited=1 goal=-1
    # s_flag=[[0 if s[i][j]=='.' else 2 for j in range(w)] for i in range(h)]
    # s_flag[ch][cw]=1
    # s_flag[dh][dw]=-1
    # ans=solve(s_flag,h,w,ch-1,cw-1,0)
    # if not ans:
    #     ans=-1
    # else:
    #     ans=ans[-1][2]
    # return ans
    ## .=inf #=# visited=cost
    s_flag=[[math.inf if s[i][j]=='.' else '#' for j in range(w)] for i in range(h)]
    s_flag[ch][cw]=0
    que=deque([[ch,cw]])
    ans2=solve2(s_flag,h,w,dh,dw,que)
    if ans2==math.inf:
        ans2=-1
    return ans2

if __name__=='__main__':
    ans=main()
    print(ans)

Submission status: Wrong Answer

Solution code:
import copy
import math
import time
import statistics
import math
import itertools
import bisect
import sys
from decimal import *
from collections import deque


def get_int():
    return int(input())

def get_string():
    return input()

def get_int_list():
    return [int(x) for x in input().split()]

def get_string_list():
    return input().split()

def get_int_multi():
    return map(int, input().split())

def get_string_char_list():
    return list(str(input()))

# print("{} {}".format(a, b))
# a_list = [0] * a
sys.setrecursionlimit(10 ** 6)

def main():
    start = time.time()

    h, w = get_int_list()
    sr, sc = get_int_list()
    er, ec = get_int_list()

    d = [[-1] * (w+2) for _ in range(h+2)]

    for i in range(h):
        wk = get_string()
        for ii in range(w):
            if wk[ii] == ".":
                d[i+1][ii+1] = 10 ** 6

    d[sr][sc] = 0
    q = deque([])
    q.append([sr,sc])

    def idou(i,ii,cnt_mahou):
        if d[i][ii] == 10 ** 6:
            q.append([i, ii])
            d[i][ii] = cnt_mahou

    ans = -1
    flg = True
    finish = False
    while flg:
        flg = False
        while q:
            wk = q.popleft()
            i = wk[0]
            ii = wk[1]
            cnt_mahou = d[i][ii]

            idou(i - 1, ii, cnt_mahou)
            idou(i + 1, ii, cnt_mahou)
            idou(i, ii - 1, cnt_mahou)
            idou(i, ii + 1, cnt_mahou)

            if d[er][ec] != 10 ** 6:
                ans = d[er][ec]
                finish = True
                break

        if finish:
            break

        for iii in range(h):
            for iiii in range(w):
                if cnt_mahou == d[iii][iiii]:

                    # 魔法を使う
                    for wk in range(-2, 3):
                        for wk2 in range(-2, 3):
                            if abs(wk) + abs(wk2) > 1:
                                flg = True
                                idou(iii + wk, iiii + wk2, cnt_mahou + 1)




    print(ans)

    #print(time.time() - start)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def main():

    input = sys.stdin.readline

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

    S=[list(map(str,list(input()[:-1]))) for i in range(H)]
    F=[ [-1] * W for i in range(H)]
    dist=[ [10000000] * W for i in range(H)]

    dh = (1, 0, -1, 0)
    dw = (0, 1, 0, -1)
    warph = (2, 2, 2, 2 ,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2)
    warpw = (-2, -1, 0, 1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2)

    d = deque()

    d.append((Ch-1,Cw-1))

    F[Ch-1][Cw-1] = 0
    dist[Ch-1][Cw-1] = 0

    while len(d) > 0:
        Ph,Pw = d.popleft()

        # if (Ph == Dh-1) & (Pw == Dw-1):
        #     goal = True
        #     break

        for i in range(4):
            nh = Ph + dh[i]
            nw = Pw + dw[i]
            if (nh < 0) | (nh >= H) | (nw < 0) | (nw >= W):
                continue
            if S[nh][nw] == "#":
                continue
            if F[nh][nw] == -1:
                d.appendleft((nh,nw))
                F[nh][nw] = 0

            dist[nh][nw] = min(dist[nh][nw],dist[Ph][Pw])

        for i in range(20):
            nh = Ph + warph[i]
            nw = Pw + warpw[i]
            if (nh < 0) | (nh >= H) | (nw < 0) | (nw >= W):
                continue
            if S[nh][nw] == "#":
                continue
            if F[nh][nw] == -1:
                d.append((nh,nw))
                F[nh][nw] = 0
            dist[nh][nw] = min(dist[nh][nw],dist[Ph][Pw]+1)

    if dist[Dh-1][Dw-1] >= 10000000:
        print("-1")
    else:
        print(dist[Dh-1][Dw-1])
         

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def dfs(xt, yt, S, V, w):
    B = set()
    while(len(S) > 0):
        xi, yi = S.pop()
        A = []
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                xj, yj = xi + i, yi + j
                if xj < 0 or len(V) <= xj or yj < 0 or len(V[0]) <= yj:
                    continue
                if -1 <= i <= 1 and -1 <= j <= 1 and i * j == 0:
                    A.append((xj, yj))
                else:
                    B.add((xj, yj))

        for xj, yj in A:
            if xj == xt and yj == yt:
                return False, B, V, w
            if V[xj][yj] > 0:
                V[xj][yj] = -1
                S.append((xj, yj))

    B_new = []
    for x, y in B:
        if x == xt and y == yt:
            return False, B, V, w + 1
        if V[x][y] > 0:
            V[x][y] = -1
            B_new.append((x, y))
    return True, B_new, V, w

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

s = [list(map(lambda x: int(x == '.'), list(input()))) for _ in range(h)]

flag = True
B = [(ch, cw)]
w = -1
s[ch][cw] = -1
while flag:
    flag, B, s, w = dfs(dh, dw, B, s, w + 1)
    if len(B) == 0:
        print(-1)
        break
else:
    print(w)

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())
maze = [[9]*(w+2)]
for i in range(h):
  s = input()
  tmp = [9]
  for i in s:
    if i == "#":
      tmp.append(9)
    else:
      tmp.append(0)
  tmp.append(9)
  maze.append(tmp)
maze.append([9]*(w+2))
#print(maze)

pos = deque()
pos.append([ch,cw,0])
while len(pos)>0:
  x, y, hop = pos.pop()
  #print(x,y,hop)
  if (x,y) == (dh,dw):
    print(hop)
    break
    
  maze[x][y] = 2
  
  flag = 0
  if maze[x-1][y] <2:
    pos.append([x-1,y,hop])
    flag = 1
  if maze[x+1][y] <2:
    pos.append([x+1,y,hop])
    flag = 1
  if maze[x][y-1] <2:
    pos.append([x,y-1,hop])
    flag = 1
  if maze[x][y+1] <2:
    pos.append([x,y+1,hop])
    flag = 1
    
  if flag == 0:
    try:
      if maze[x-2][y] <2:
        pos.append([x-2,y,hop+1])
    except:
      pass
    
    try:
      if maze[x-2][y+1] <2:
        pos.append([x-2,y+1,hop+1])
    except:
      pass
        
    try: 
      if maze[x-2][y+2] <2:
        pos.append([x-2,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x-2][y-1] <2:
        pos.append([x-2,y-1,hop+1])
    except:
      pass
    
    try:
      if maze[x-2][y-2] <2:
        pos.append([x-2,y-2,hop+1])
    except:
      pass
    
    try:
      if maze[x+2][y] <2:
        pos.append([x+2,y,hop+1])
    except:
      pass
    try:
      if maze[x+2][y-1] <2:
        pos.append([x+2,y-1,hop+1])
    except:
      pass
    try:
      if maze[x+2][y-2] <2:
        pos.append([x+2,y-2,hop+1])
    except:
      pass
    try:
      if maze[x+2][y+1] <2:
        pos.append([x+2,y+1,hop+1])
    except:
      pass
    
    try:
      if maze[x+2][y+2] <2:
        pos.append([x+2,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x][y-2] <2:
        pos.append([x,y-2,hop+1])
    except:
      pass
    
    try:
      if maze[x+1][y-2] <2:
        pos.append([x+1,y-2,hop+1])
    except:
      pass
    try:
      if maze[x-1][y-2] <2:
        pos.append([x-1,y-2,hop+1])
    except:
      pass
    
    try:
      if maze[x][y+2] <2:
        pos.append([x,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x+1][y+2] <2:
        pos.append([x+1,y+2,hop+1])
    except:
      pass
    
    try:
      if maze[x-1][y+2] <2:
        pos.append([x-1,y+2,hop+1])
    except:
      pass
    if maze[x-1][y-1] <2:
      pos.append([x-1,y-1,hop+1])
    if maze[x-1][y+1] <2:
      flag=1
      pos.append([x-1,y+1,hop+1])
    if maze[x+1][y-1] <2:
      flag=1
      pos.append([x+1,y-1,hop+1])
    if maze[x+1][y+1] <2:
      flag=1
      pos.append([x+1,y+1,hop+1])
    
else:
  print(-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])
while(len(q) != 0):
  tmp = q.popleft()
  nowH = tmp[0]
  nowW = tmp[1]
  for i in range(-2,2+1):
    for j in range(-2,2+1):
      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 countWarp[DH,DW] == H*W:
  print(-1)
else:
  print(int(countWarp[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())
field = set()

cnt = 0
for i in range(h):
  s = input()
  for j in range(w):
    if s[j] == ".":
      field.add((i, j))
      cnt += 1

ans = 0
dq = deque()
dq.append((ch - 1, cw - 1))

while (dh - 1, dw - 1) in field:
  field2 = set()
  field3 = set()
  while len(dq) > 0:
    now_h, now_w = dq.popleft()
    if (now_h, now_w) in field:
      field.remove((now_h, now_w))
      field2.add((ch - 1, cw - 1))
      cnt -= 1
    if (now_h - 1, now_w) in field:
      dq.append((now_h - 1, now_w))
    if (now_h + 1, now_w) in field:
      dq.append((now_h + 1, now_w))
    if (now_h, now_w - 1) in field:
      dq.append((now_h, now_w - 1))
    if (now_h, now_w + 1) in field:
      dq.append((now_h, now_w + 1))
  
  if (dh - 1, dw - 1) in field:
    flag = False
    for _h, _w in field2:
      for i in range(-2, 3):
        for j in range(-2, 3):
          if (_h + i, _w + j) in field and (_h + i, _w + j) not in field3:
            ans += 1
            dq.append((_h + i, _w + j))
            field3.add((_h + i, _w + j))
            flag = True
    if not flag:
      break

print(ans if cnt == 0 else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import itertools
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
maze = [input() for _ in range(H)]

#bfsは同じエリアを染める。
#スタートはエリアのスタートでゴールは全体のゴール
def bfs(maze, visited, sy, sx, gy, gx):
    flag = 0#ゴールできるか
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0#今回はワープ回数
    while queue:
        y, x = queue.popleft()
        
        if [y,x] == [gy, gx]:
            flag = 1
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):#まずは縦横から。
            new_y, new_x = y+j, x+k
            if new_y >= 0 and new_y < H and new_x >= 0 and new_x < W:
                if maze[new_y][new_x] == ".":
                    if visited[new_y][new_x] == -1:
                        visited[new_y][new_x] = visited[y][x]#ワープしないから同じ
                        queue.append([new_y, new_x])#キューを追加
                    else:#訪れたことがある
                        visited[new_y][new_x] = min(visited[y][x],visited[new_y][new_x])
        for j in range(-2,3):
            for k in range(-2,3):
                new_y, new_x = y+j, x+k
                if new_y >= 0 and new_y < H and new_x >= 0 and new_x < W:
                    if (j,k) not in [[1, 0], [-1, 0],[0,0], [0, 1], [0, -1]]:
                        
                        if maze[new_y][new_x] == ".":
                            if visited[new_y][new_x] == -1:
                                 visited[new_y][new_x] = visited[y][x] + 1
                                 queue.append([new_y, new_x])#キューを追加
                            else:
                                visited[new_y][new_x] = min(visited[y][x]+1,visited[new_y][new_x])
    if flag == 0:
        return -1

visited = [[-1]*W for j in range(H)]
print(bfs(maze, visited, Ch-1, Cw-1, Dh-1, Dw-1))

Submission status: Wrong Answer

Solution code:
import collections

h, w = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
dh, dw = list(map(int, input().split()))
s = [list(input()) for _ in range(h)]

g = {}

def dump():
    print('map')
    for row in s:
        print(''.join(row))
    print('graph')
    print(g)
    print()

def check_range(x, y):
    return (0 <= x < h) and (0 <= y < w)

deq = collections.deque()
ident = 0
def reveal_cluster():
    global ident
    while len(deq):
        x, y, no = deq.popleft()
        if not check_range(x, y):
            continue
        if s[x][y] != '.':
            continue
        
        if no is None:
            ident += 1
            g[ident] = set()

        s[x][y] = str(ident)

        # 移動A
        for dx, dy in [(0, -1), (0, +1), (-1, 0), (+1, 0)]:
            nx, ny = x + dx, y + dy
            if check_range(nx, ny) and s[nx][ny] == '.':
                deq.append((nx, ny, ident))

deq.append((ch - 1, cw - 1, None))
reveal_cluster()

deq.append((dh - 1, dw - 1, None))
reveal_cluster()

for i in range(h):
    for j in range(w):
        deq.append((i, j, None))
        reveal_cluster()
#dump()

def check_cluster_connectivity():
    while len(deq):
        x, y, prev = deq.popleft()

        if not check_range(x, y):
            continue
        if s[x][y] == '#':
            continue

        curr = s[x][y]
        curr = int(curr)
        if prev is not None and curr != prev:
            k = int(s[x][y])
            g[prev].add(k)

        _prev = int(s[x][y])

        s[x][y] = '#'

        # 移動B
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if check_range(nx, ny) and s[nx][ny] != '#' and s[nx][ny] != s[x][y]:
                    v = (nx, ny, _prev)
                    deq.append(v)

for i in range(h):
    for j in range(w):
        v = (i, j, None)
        deq.append(v)
        check_cluster_connectivity()

dist = {k:None for k in g}
def bfs(pos, d):
    if dist[2] is not None:
        return
    if dist[pos] is not None:
        return
    dist[pos] = d
    for e in g[pos]:
        bfs(e, d + 1)

if len(g) == 1:
    # スタート = ゴール
    print(0)
else:
    bfs(1, 0)
    
    a = dist[2]
    if a is None:
        # 経路なし
        print(-1)
    else:
        # 経路あり
        print(a)

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)]

# 島がいくつあるか検索
# nは何個目の島か
next_list = [[ch-1,cw-1]]
n = 0

def dfs(h_i, w_i, n):
  S[h_i][w_i] = n
  
  if not next_list:
    for i in range(max(h_i-2,0), min(h_i+3,h))[::-1]:
      for j in range(max(w_i-2,0), min(w_i+3,w))[::-1]:
        if S[i][j]=='.':
          next_list.append([i,j])
          break
    
  for dh, dw in [[1,0], [0,-1], [-1,0], [0,1]]:
    if 0<=h_i+dh<=h-1 and 0<=w_i+dw<=w-1:
      if S[h_i+dh][w_i+dw]=='.':
        dfs(h_i+dh, w_i+dw, n)

while next_list:
  h_i, w_i = next_list.pop(0)
  if S[h_i][w_i]=='.':
    dfs(h_i, w_i, n)
    n += 1

print(-1 if S[dh-1][dw-1]=='.' else S[dh-1][dw-1])