Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
S = []
C_h -= 1
C_w -= 1
D_h -= 1
D_w -= 1
for h in range(H):
    tmp = [x for x in input()]
    S.append(tmp)

ans = 0
warp = [2, 1, -1, -2]
while D_h != C_h or D_w != C_w:
    if D_h - C_h > 0:
        dir_h = 1
    else:
        dir_h = -1

    if D_w - C_w > 0:
        dir_w = 1
    else:
        dir_w = -1

    while True:
        if D_h == C_h:
            break
        if S[C_h + dir_h][C_w] == '#':
            break
        C_h += dir_h
    
    if C_h + dir_h == H or C_h + dir_h < 0:
        dir_h = 0

    while True:
        if D_w == C_w:
            break
        if S[C_h][C_w + dir_w] == '#':
            break
        C_w += dir_w
    
    if C_w + dir_w == W or C_w + dir_w < 0:
        dir_w = 0

    if D_h == C_h and D_w == C_w:
        break
    
    flag = 0
    for h in warp:
        if flag == 0:
            for w in warp:
                if 0 < C_h + h * dir_h < H and 0 < C_w + w * dir_w < W:
                    if S[C_h + h * dir_h][C_w + w * dir_w] == '.':
                        ans += 1
                        C_h += h * dir_h
                        C_w += w * dir_w
                        flag = 1
                        break
        else:
            break
    
    if flag == 0:
        ans = -1
        break

print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int, input().split())
ch,hw = map(int, input().split())
dh,dw = map(int, input().split())

sx,sy=ch-1,hw-1
gx,gy=dw-1,dh-1

l = [None]*h
for i in range(h):
    l[i] = list(input())

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

from collections import deque
def walk(warped,cnt):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    Q = deque(warped)
    walked=warped
    changed=False
    while Q:
        p = Q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < w and 0 <= ny < h:
                if l[ny][nx]=="." and dist[ny][nx]==-1:
                    changed=True
                    Q.append([nx, ny])
                    walked.append([nx,ny])
                    dist[ny][nx] = cnt
                    if nx==gx and ny==gy:
                        print(cnt)
                        exit()
    return walked,changed
def warp(walked,cnt):
    warped=[]
    changed=False

    for x,y in walked:
        for dx in [-2,-1,0,1,2]:
            for dy in [-2,-1,0,1,2]:
                #if abs(dx)+abs(dy)<=1:
                #    continue

                nx=x+dx
                ny=y+dy
                if 0 <= nx < w and 0 <= ny < h:
                    if l[ny][nx]=="." and dist[ny][nx]==-1:
                        changed=True
                        warped.append([nx,ny])
                        dist[ny][nx] = cnt
                        if nx==gx and ny==gy:
                            print(cnt)
                            exit()
    return warped,changed

cnt=0

warped=[[sx,sy]]

while True:
    walked,walkchange= walk(warped,cnt)
    cnt+=1
    warped,warpchange=warp(walked,cnt)
    if not walkchange and not warpchange:
        print(-1)
        exit()

Submission status: Wrong Answer

Solution code:
import copy
from collections import deque

H, W = [int(i) for i in input().split()]
C = tuple([int(i) - 1 for i in input().split()])
D = tuple([int(i) - 1 for i in input().split()])
S = []
for i in range(H):
  s = list(input())
  S.append(s)
  
  
# 領域を計算
def dfs(arr, h, w):
  arr[h][w] = "#"
  region = set([tuple([h, w])])
  for i, j in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
      nh = h + i
      nw = w + j
      if 0 <= nh and 0 <= nw and nh < H and nw < W and arr[nh][nw] == ".":
        region |= dfs(arr, nh, nw)
  return region

regions = []
field = copy.deepcopy(S)

for h in range(H):
  for w in range(W):
    if field[h][w] == ".":
      region = dfs(field, h, w);
      regions.append(region)

s_reg = -1
g_reg = -1

for i in range(len(regions)):
  if C in regions[i]:
    s_reg = i
  if D in regions[i]:
    g_reg = i

count = 0
d = deque()
arrived = set()
arrived_pos = set()
d.append(s_reg)
arrived.add(s_reg)

while d:
  pos = d.popleft()
  if pos == g_reg:
    break
  # ワープできる領域を計算
  for p in regions[pos]:
    for h in range(-2, 3):
      for w in range(-2, 3):
        ph = p[0] + h
        pw = p[1] + w
        if pw < 0 or W <= pw or ph < 0 or H <= ph:
          # 欄外
          continue
        if tuple([ph, pw]) in arrived_pos:
          continue
        arrived_pos.add(tuple([ph, pw]))
        for i in range(len(regions)):
          if i not in arrived:
            if tuple([ph, pw]) in regions[i]:
              print(i, regions[i])
              arrived.add(i)
              d.append(i)
  count += 1
  

print(regions, arrived, count)  

if g_reg not in arrived:
  print(-1)
else:
  print(count)

Submission status: Wrong Answer

Solution code:
import heapq
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
road_map = []
for i in range(h):
    road = input()
    road_map.append(road)
queue = []
heapq.heappush(queue,[0,ch-1,cw-1])
used_map = [[-1]*w for _ in range(h)]

layer_set = set()
layer_set.add((ch-1,cw-1))
loop = 0
while layer_set != set():
    layer_set = set()
    #move walk
    while queue != []:
        dot = heapq.heappop(queue)
        if dot[1] < 0 or dot[2] < 0 or dot[1] >= h or dot[2] >= w:
            continue
        if used_map[dot[1]][dot[2]] > -1 and used_map[dot[1]][dot[2]] <= dot[0]:
            continue
        if road_map[dot[1]][dot[2]] == "#":
            continue
        used_map[dot[1]][dot[2]] = dot[0]
        layer_set.add((dot[1],dot[2]))

        if not (dot[2] - 1 < 0):
            heapq.heappush(queue,[dot[0],dot[1],dot[2]-1])
        if not (dot[2] + 1 >= w):
            heapq.heappush(queue,[dot[0],dot[1],dot[2]+1])
        if not (dot[1]+1 >= h):
            heapq.heappush(queue,[dot[0],dot[1]+1,dot[2]])
        if not (dot[1]-1 < 0):
            heapq.heappush(queue,[dot[0],dot[1]-1,dot[2]])

    temp = []
    for s in layer_set:
        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if not(s[0]+ x < 0 or s[1]+y < 0 or s[0]+x >= h or s[1]+y >= w):
                    if used_map[s[0]+x][s[1]+y] == -1 and road_map[s[0]+x][s[1]+y] == ".":
                        temp = [s[0]+x,s[1]+y]
                if temp != []:
                    break
            if temp != []:
                break
        if temp != []:
            break 
    if temp != []:
        heapq.heappush(queue,[loop+1,temp[0],temp[1]])
    loop+=1
    
print(used_map[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()


def main():
    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
    s2 = [list(input()) for i in range(h)]
    s2[Ch][Cw] = 0
    d = deque()
    d.append([Ch, Cw])
    dict1={1:[[-2,2],[-1,1],[-1,2],[0,2],[1,1],[1,2],[2,2]],2:[[2,-2],[2,-1],[2,0],[2,-1],[2,-2],[1,-1],[1,1]],3:[[-2,-2],[-2,-1],[-2,0],[-2,-1],[-2,-2],[-1,-1],[-1,1]],4:[[-2,-2],[-1,-1],[-1,-2],[0,-2],[1,-1],[1,-2],[2,-2]]}
    dict2={1:[0,1],2:[1,0],3:[-1,0],4:[0,-1]}
    while d:
        nowh, noww = d.popleft()
        for m in [1,2,3,4]:
            i,j=dict2[m]
            if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                if s2[nowh+i][noww+j] == '.':
                    s2[nowh+i][noww+j] = s2[nowh][noww]
                    d.appendleft([nowh+i, noww+j])
                elif s2[nowh+i][noww+j] != '#':
                    if s2[nowh+i][noww+j] > s2[nowh][noww]:
                        s2[nowh+i][noww+j] = s2[nowh][noww]
                        d.append([nowh+i, noww+j])
                else:
                    for i2,j2 in dict1[m]:
                        if ((0 <= nowh+i2 < h) and (0 <= noww+j2 < w)):
                            if s2[nowh+i2][noww+j2] == '.':
                                s2[nowh+i2][noww+j2] = s2[nowh][noww]+1
                                d.append([nowh+i2, noww+j2])
                            elif s2[nowh+i2][noww+j2] != '#':
                                if s2[nowh+i2][noww+j2] > s2[nowh][noww]+1:
                                    s2[nowh+i2][noww+j2] = s2[nowh][noww]+1
                                    d.append([nowh+i2, noww+j2])
        

    if s2[Dh][Dw] == '.':
        print(-1)
    else:
        print(s2[Dh][Dw])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
from collections import deque
#======================================================#
def main():
    h, w = MII()
    ch, cw = MII()
    dh, dw = MII()
    maze = []
    for i in range(2):
        maze.append(['#']*(w+4))
    for i in range(h):
        maze.append(['#']*2 + list(IS()) + ['#']*2)
    for i in range(2):
        maze.append(['#']*(w+4))

    seen = maze[:]
    def bfs(maze, y, x):
        dq = deque()
        dq.append((y, x, 0))
        ret = []
        while dq:
            now_y, now_x, now_count = dq.popleft()
            if now_y == dh+1 and now_x == dw+1:
                ret.append(now_count)
            seen[now_y][now_x] = '#'
            for dx, dy in [(1,0), (-1,0), (0, 1), (0, -1)]:
                nx = now_x + dx
                ny = now_y + dy
                if seen[ny][nx] == '#':
                    continue
                seen[ny][nx] == '#'
                dq.append((ny, nx, now_count))
            for dx in range(-2, 3, 1):
                for dy in range(-2, 3, 1):
                    nx = now_x + dx
                    ny = now_y + dy
                    if seen[ny][nx] == '#':
                        continue
                    dq.append((ny, nx, now_count+1))
        return ret

    # res = dfs(maze, ch+1, cw+1)
    res = bfs(maze, ch+1, cw+1)
    if res:
        print(min(res))
    else:
        print(-1)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij4=[(0,1),(1,0),(-1,0),(0,-1)]
dijx=[(1,1),(-1,1),(1,-1),(-1,-1)]
dij8=[(0,1),(1,0),(-1,0),(0,-1),(1,-1),(1,1),(-1,-1),(-1,1)]

from collections import deque

def solve():
    q = []
    q.append((si, sj, 0))
    aa[si][sj] = 0
    wall=[]

    while q:
        while q:
            i, j, d = q.pop()
            for di, dj in dij4:
                ni, nj = i + di, j + dj
                if ni < 0 or ni >= h or nj < 0 or nj >= w: continue
                if aa[ni][nj]!=-1:continue
                if ss[ni][nj]:
                    aa[ni][nj]=d+1
                    wall.append((ni,nj,d+1))
                else:
                    aa[ni][nj]=d
                    q.append((ni,nj,d))
        while wall:
            i, j, d = wall.pop()
            for di, dj in dij4+dijx:
                ni, nj = i + di, j + dj
                if ni < 0 or ni >= h or nj < 0 or nj >= w: continue
                if aa[ni][nj]!=-1:continue
                if ss[ni][nj]:continue
                aa[ni][nj]=d
                q.append((ni,nj,d))

    print(aa[gi][gj])


h,w=MI()
si,sj=MI1()
gi,gj=MI1()
ss=[[1 if c=="#" else 0 for c in SI()] for _ in range(h)]
aa=[[-1]*w for _ in range(h)]
#p2D(ss)
solve()

Submission status: Wrong Answer

Solution code:
import pprint
import sys
sys.setrecursionlimit(10**8)
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

city = []
for i in range(H):
    city.append(input())

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

def dfs(x, y, count):

    if (not (0 <= x < W)) or (not (0 <= y < H)):
        return

    if visited[y][x] > -1:
        return

    if x == Dw and y == Dh:
        pprint.pprint(visited)
        visited[y][x] = count
        print(count)
        exit()

    if city[y][x] == "#":
        return

    if visited[y][x] == -1:
        visited[y][x] = count

    dfs(x+1, y, count)
    dfs(x, y+1, count)
    dfs(x-1, y, count)
    dfs(x, y-1, count)

    for i in range(-2, 3):
        for j in range(-2, 3):
            if (not (0 <= x+j < W)) or (not (0 <= y+i < H)):
                continue
            if visited[y+i][x+j] > -1:
                continue
            if city[y+i][x+j] == "#":
                continue

            dfs(x+j, y+i, count+1)



dfs(Cw, Ch, 0)

print(visited[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())
maze = [list(map(str, input().split())) for i in range(H)]
inf = float("inf")
dp = [[inf for i in range(W)] for i in range(H)]
dp[Ch-1][Cw-1] = 0
move = [[-1, 0], [0, -1], [0, 1], [1, 0]]

for A in range(3):
  for i in range(H):
    for j in range(W):
      if maze[i][0][j] == "#":
        continue
      for k,l in move:
        if 0 <= i+k <= H-1 and 0 <= j+l <= W-1:
          if maze[i+k][0][j+l] == ".":
            dp[i][j] = min(dp[i+k][j+l], dp[i][j])      
      for m in range(-2, 3):
        for n in range(-2, 3):
          if not m and not n:
            continue
          if 0 <= i+m <= H-1 and 0 <= j+n <= W-1:
            if maze[i+m][0][j+n] == ".":
              dp[i][j] = min(dp[i+m][j+n]+1, dp[i][j])

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
def solve():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch -= 1
    Cw -= 1
    Dh,Dw = map(int,input().split())
    Dh -= 1
    Dw -= 1

    S = [list(input()) for _ in range(H)]
    area_num = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                dfs(h,w,H,W,S,area_num)
                area_num += 1

    start_area_num = int(S[Ch][Cw])
    goal_area_num = int(S[Dh][Dw])

    G = defaultdict(set)

    for h in range(H):
        for w in range(W):
            from_area_num = S[h][w]
            if from_area_num == '#':
                continue
            from_area_num = int(from_area_num)

            d = ((0,-1),(0,1),(-1,0),(1,0))
            close_to_wall = False
            for dh, dw in d:
                if dh+h < 0 or dh+h >= H:
                    continue
                if dw+w < 0 or dw+w >= W:
                    continue

                if S[dh+h][dw+w] == '#':
                    close_to_wall = True
            
            if not close_to_wall:
                continue

            # for dh in range(-2,2+1):
            for dh in range(1):
                if h+dh < 0 or h+dh >= H:
                    continue
                # for dw in range(-2, 2+1):
                for dw in range(1):
                    if w+dw < 0 or w+dw >= W:
                        continue
                    to_area_num = S[h+dh][w+dw]
                    if to_area_num == '#':
                        continue
                    to_area_num = int(to_area_num)
                    if from_area_num != to_area_num:
                        G[to_area_num].add(from_area_num)
                        G[from_area_num].add(to_area_num)
    
    area_num_count = area_num + 1
    visited = [False] * area_num_count
    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        visited[cur_area_num] = True
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                q.append((next_area_num,warp_cnt+1))
    else:
        print(-1)

def dfs(h,w,H,W,S,area_num):
    if 0 <= h < H and 0 <= w < W and S[h][w] == '.':
        S[h][w] = str(area_num)
        dfs(h+1,w,H,W,S,area_num)
        dfs(h,w+1,H,W,S,area_num)
        dfs(h-1,w,H,W,S,area_num)
        dfs(h,w-1,H,W,S,area_num)

def mod_graph(G,including_area_num_set):
    for area_num_from in including_area_num_set:
        for area_num_to in including_area_num_set:
            G[area_num_from].add(area_num_to)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
import sys
sys.setrecursionlimit(10**8)

def bfs(a,b):
    if a == dh+1 and b == dw+1:
        exit(0) 

    if s[a+1,b]=='.': 
        q.append([a+1,b])
        s[a+1,b]=int(s[a,b])
    elif [a,b] not in wq:
            wq.append([a,b])
    if s[a,b+1]=='.':
        q.append([a,b+1])
        s[a,b+1]=int(s[a,b])
    elif [a,b] not in wq:
            wq.append([a,b])
    if s[a-1,b]=='.':
        q.append([a-1,b])
        s[a-1,b]=int(s[a,b])
    elif [a,b] not in wq:
            wq.append([a,b])
    if s[a,b-1]=='.':
        q.append([a,b-1])
        s[a,b-1]=int(s[a,b])
    elif [a,b] not in wq:
            wq.append([a,b])
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.pop(0)
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return

def worp(a,b):
    for ii in range(-2,3):
        for jj in range(-2,3):
            if s[a+ii,b+jj]=='.':
                q.append([a+ii,b+jj])
                s[a+ii,b+jj]=int(s[a,b])+1
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.pop(0)
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return   

H,W=map(int, input().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
s=np.array([list(input()) for _ in range(H)],dtype=object)
q = deque([])
wq= []

hbmp=['#']*(W)
s=np.vstack((hbmp,hbmp,s,hbmp,hbmp))
vbmp=[['#']]*(H+4)
s=np.hstack((vbmp,vbmp,s,vbmp,vbmp))

ch,cw=ch+1,cw+1
s[ch,cw]=int(0)

bfs(ch,cw)

Submission status: Wrong Answer

Solution code:
h, w = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
dh, dw = list(map(int, input().split()))
dp = [[1e9 for __ in range(w)] for _ in range(h)]
isFirst = True
S = [[] for _ in range(h)]
for i in range(h):
    S[i] = list(input())
    for j in range(w):
        if S[i][j] == '#':
            dp[i][j] = -1
            continue
        if isFirst:
            dp[i][j] = 0
            isFirst = False
        
        t = max(0, i-2)
        b = min(h-1, i+2)
        l = max(0, j-2)
        r = min(w-1, j+2)
        magic = dp[i][j]+1
        for wi in range(t, b+1):
            for wj in range(l, r+1):
                dp[wi][wj] = min(dp[wi][wj], magic)

        if i-1 >= 0:
            dp[i-1][j] = min(dp[i-1][j], dp[i][j])
        if i+1 < h:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if j-1 >= 0:
            dp[i][j-1] = min(dp[i][j-1], dp[i][j])
        if j+1 < w:
            dp[i][j+1] = min(dp[i][j+1], dp[i][j])
# print(dp)
if dp[ch-1][cw-1] == 1e9 or dp[dh-1][dw-1] == 1e9:
    print(-1)
else:
    print(abs(dp[ch-1][cw-1] - dp[dh-1][dw-1]))

Submission status: Wrong Answer

Solution code:
from collections import deque

h,w=map(int,input().split())
cch,ccw=map(int,input().split())
ddh,ddw=map(int,input().split())
s=[[c for c in input()] for _ in range(h)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def convert(ch,cw):
    return ch*w+cw


uf=UnionFind(w*h)

visit=[[0]*w for _ in range(h)]

node=0
dic={}
for hh in range(h):
    for ww in range(w):
        if visit[hh][ww]==0 and s[hh][ww]=='.':
            stack=[(hh,ww)]
            dic[convert(hh,ww)]=node
            node+=1
            while len(stack)>0:
                ch,cw=stack.pop()

                visit[ch][cw]=1

                uf.union(convert(hh,ww),convert(ch,cw))

                for dh,dw in [(1,0),(-1,0),(0,1),(0,-1)]:
                    nh=ch+dh
                    nw=cw+dw
                    if 0<=nh<h and 0<=nw<w and s[nh][nw]=='.' and visit[nh][nw]==0:
                        stack.append((nh,nw))

edge=[set() for _ in range(node)]
visit=[[0]*w for _ in range(h)]
for hh in range(h):
    for ww in range(w):
        if s[hh][ww]=='#' or visit[hh][ww]==1:
            continue
        visit[hh][ww]=1
        for dh in range(-2,3):
            for dw in range(-2,3):
                if dh==0 and dw==0:
                    continue
                nh=hh+dh
                nw=ww+dw
                if 0<=nh<h and 0<=nw<w and s[nh][nw]=='.' and visit[nh][nw]==0:
                    if uf.same(convert(hh,ww),convert(nh,nw))==False:
                        p1=uf.find(convert(hh,ww))
                        p2=uf.find(convert(nh,nw))
                        
                        edge[dic[p1]].add(dic[p2])
                        edge[dic[p2]].add(dic[p1])
                        visit[nh][nw]=1

start=dic[uf.find(convert(cch-1,ccw-1))]
end=dic[uf.find(convert(ddh-1,ddw-1))]

q=deque([(start,0)])
visit=[0]*node

while len(q)>0:
    u,cnt=deque.popleft(q)

    visit[u]=1

    if end==u:
        print(cnt)
        exit(0)
    
    for v in edge[u]:
        if visit[v]==1:
            continue

        deque.append(q,(v,cnt+1))

print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10000)

H, W = map(int, input().split())
C = tuple(map(int, input().split()))
D = tuple(map(int, input().split()))
S = [list(input()) for _ in range(H)]

d = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def dfs(h, w, i):
    S[h][w] = i

    for dh, dw in d:
        nh = h + dh
        nw = w + dw
        if nh < 0 or nh >= H or nw < 0 or nw >= W:
            continue
        if S[nh][nw] != '.':
            continue
        dfs(nh, nw, i)

# 番号を振る
count = 1
for h in range(H):
    for w in range(W):
        if S[h][w] != '.':
            continue
        dfs(h, w, count)
        count += 1

# グラフを構築
graph = {}
for i in range(1, count):
    graph[i] = set()

for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue

        for dh in range(-2, 3):
            for dw in range(-2, 3):
                nh = h + dh
                nw = w + dw
                if nh < 0 or nh >= H or nw < 0 or nw >= W:
                    continue
                if S[nh][nw] == '#':
                    continue
                graph[S[h][w]].add(S[nh][nw])

start = S[C[0]-1][C[1]-1]
goal = S[D[0]-1][D[1]-1]

# 最短経路を求める
def bfs(start, goal):
    queue = deque([start])
    visited = set()
    visited.add(start)
    depth = 0
    while queue:
        current_vertex = queue.popleft()
        if current_vertex == goal:
            return depth
        depth += 1
        for v in graph[current_vertex]:
            if v not in visited:
                visited.add(v)
                queue.append(v)
    return -1

ans = bfs(start, goal)

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):
    F = 0
    z += 1
    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)
lisy = [-2,-1,0,1,2]
lis = []
for i in range(5):
    for j in range(5):
      lis.append([lisy[i],lisy[j]])
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 abs(nh-h) > 2 or abs(nw-w) > 2:
            continue
        if dist[nh][nw] == -1:
            bfs(nh,nw,n)
print(-1)

Submission status: Wrong Answer

Solution code:
def main(H,W,ch,cw,dh,dw,S):
    q=np.zeros((3*10**7,3),dtype=np.int32)
    q[0][0],q[0][1],q[0][2]=ch-1,cw-1,0
    v=-np.ones((H,W),dtype=np.int32)
    x=[[1,0],[-1,0],[0,-1],[0,1]]
    y=[[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]
    l,r=0,1
    while l<r:
        h,w,d=q[l][0],q[l][1],q[l][2]
        l+=1
        if v[h][w]<0:
            v[h][w]=d
        for k in range(4):
            i,j=x[k][0],x[k][1]
            if 0<=h+i<H and 0<=w+j<W and S[h+i][w+j] and v[h+i][w+j]<0:
                q[r][0],q[r][1],q[r][2]=h+i,w+j,d
                r+=1
        for k in range(20):
            i,j=y[k][0],y[k][1]
            if 0<=h+i<H and 0<=w+j<W and S[h+i][w+j] and v[h+i][w+j]<0:
                q[r][0],q[r][1],q[r][2]=h+i,w+j,d+1
                r+=1
    return v[dh-1][dw-1]
import sys
import numpy as np
readline=sys.stdin.buffer.readline
read=sys.stdin.buffer.read
if sys.argv[-1]=='ONLINE_JUDGE':
    from numba import*
    from numba.pycc import CC
    cc=CC('my_module')
    def cc_export(f,s):
        cc.export(f.__name__,s)(f)
        return njit(f)
    main=cc_export(main,(i4,i4,i4,i4,i4,i4,i4[:,:]))
    cc.compile()
    exit()
H,W=map(int,readline().split())
ch,cw=map(int,readline().split())
dh,dw=map(int,readline().split())
S=np.array([[1 if c=='.' else 0 for c in readline().strip()] for i in range(H)],dtype=np.int32)
from my_module import main
print(main(H,W,ch,cw,dh,dw,S))