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


def bfs():


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

    tests = (0, 1), (1, 0), (-1, 0), (0, -1)
    warps = (
        (1, 1),
        (-1, 1),
        (-1, -1),
        (1, -1),
        (2, 0),
        (2, -1),
        (2, -2),
        (1, -2),
        (0, -2),
        (-1, -2),
        (-2, -2),
        (-2, -1),
        (-2, 0),
        (-2, 1),
        (-2, 2),
        (-1, 2),
        (0, 2),
        (1, 2),
        (2, 2),
        (1, 2),
    )

    start = (C[0] - 1, C[1] - 1, 0)
    goal = (D[0] - 1, D[1] - 1, 0)

    queue = deque()
    # (x, y, ワープ回数)
    queue.append(start)

    while queue:
        next_queue = deque()

        for _ in range(len(queue)):
            x, y, w_n = queue.pop()

            # 通常移動
            for dx, dy in tests:
                nx = x + dx
                ny = y + dy

                if nx < 0 or nx >= H or ny < 0 or ny >= W:
                    break

                if S[nx][ny] != "#":
                    if S[nx][ny] != "." and w_n >= S[nx][ny]:
                        continue
                    else:
                        S[nx][ny] = w_n
                        next_queue.append((nx, ny, w_n))

            # warp
            w_n += 1
            for dx, dy in warps:
                nx = x + dx
                ny = y + dy

                if nx < 0 or nx >= H or ny < 0 or ny >= W:
                    break

                if S[nx][ny] != "#":
                    if S[nx][ny] != "." and w_n >= S[nx][ny]:
                        continue
                    else:
                        S[nx][ny] = w_n
                        next_queue.append((nx, ny, w_n))

        queue = next_queue


    if S[goal[0]][goal[1]] == ".":
        print(-1)
    else:
        print(S[goal[0]][goal[1]])



bfs()

Submission status: Wrong Answer

Solution code:
from math import trunc
import sys
import copy
from collections import deque
import collections
import itertools
stdin = sys.stdin
import math

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces


h, w = na()
sh, sw = na()
gh, gw = na()

map = []
for _ in range(h):
    s = ns()
    map.append([0 if i=="." else 1 for i in s])

visited = [[10000000 for j in range(w)] for i in range(h)]

def warp(nh, nw, now_warp):
    next_p = []
    topleft = [nh-2, nw-2]
    for i in range(5):
        for j in range(5):
            neh = topleft[0]+i
            new = topleft[1]+j
            if check_position(neh, new, now_warp+1):
                next_p.append([neh, new])
    return next_p


def check_position(hi, wi, now_warp):
    if hi<0 or hi>=h or wi<0 or wi>=w or map[hi][wi]==1 or visited[hi][wi] <= now_warp:
        return False
    return True


positions = deque()
positions.append([sh-1, sw-1, 0])
while len(positions)>0:
    warp_positions = deque()
    while len(positions)>0:
        nh, nw, now_warp = positions.popleft()

        if now_warp >= visited[nh][nw]:
            continue

        visited[nh][nw] = now_warp
        move_cnt = 0
        if check_position(nh+1, nw, now_warp):
            positions.append([nh+1, nw, now_warp])
            move_cnt += 1
        
        if check_position(nh, nw+1, now_warp):
            positions.append([nh, nw+1, now_warp])
            move_cnt += 1
        
        if check_position(nh-1, nw, now_warp):
            positions.append([nh-1, nw, now_warp])
            move_cnt += 1
        
        if check_position(nh, nw-1, now_warp):
            positions.append([nh, nw-1, now_warp])
            move_cnt += 1

        if move_cnt<4:
            warp_positions.append([nh, nw, now_warp])
    
    while len(warp_positions)>0:
        nh, nw, now_warp = warp_positions.popleft()
        next_warps = warp(nh, nw, now_warp)
        for p in next_warps:
            positions.append([p[0], p[1], now_warp+1])

print(-1 if visited[gh-1][gw-1]==100000 else visited[gh-1][gw-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split())
sy,sx = map(int,input().split())
sy -= 1
sx -= 1
gy,gx = map(int,input().split())
grid = [0]*H
for i in range(H):
    grid[i] = input()
cost = [[float('inf')]*W for _ in range(H)]
cost[sy][sx] = 0
done = [[0]*W for _ in range(H)]
done[sy][sx] = 1
walk_q = deque()
walk_q.append([sy,sx])
magic_q = deque()
magic_q.append([sy,sx])
def walk(y,x):
    for new_y, new_x in [[y+1,x],[y,x+1],[y-1,x],[y,x-1]]:
        if 0 <= new_y < H and 0 <= new_x < W and grid[new_y][new_x] == '.':
            if cost[new_y][new_x] > cost[y][x]:
                cost[new_y][new_x] = cost[y][x]
                walk_q.append([new_y,new_x])
                magic_q.append([new_y,new_x])
                done[new_y][new_x] = 1
def magic(y,x):
    for y_add in [i for i in range(-2,3)]:
        for x_add in [i for i in range(-2,3)]:
            if 0 <= y+y_add < H and 0 <= x+x_add < W and grid[y+y_add][x+x_add] == '.':
                if cost[y+y_add][x+x_add] > cost[y][x]+1:
                    cost[y+y_add][x+x_add] = min(cost[y+y_add][x+x_add],cost[y][x]+1)
                    walk_q.append([y+y_add,x+x_add])
                    done[y+y_add][x+x_add] = 1

while walk_q or magic_q:
    while walk_q:
        y,x = walk_q.popleft()
        walk(y,x)
    while magic_q:
        y,x = magic_q.popleft()
        magic(y,x)
if not done[gy-1][gx-1]:
    print(-1)
else:
    print(cost[gy-1][gx-1])

Submission status: Wrong Answer

Solution code:
def main():
    import time
    import sys
    input = sys.stdin.readline
    from heapq import heappop, heappush
    s = time.time()
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    S = [['#'] * (W + 4)]
    tmp = ['#'] * (W + 4)
    S.append(tmp)

    for _ in range(H):
        tmp = ['#', '#'] + list(input()) + ['#']
        S.append(tmp)

    tmp = ['#'] * (W + 4)
    S.append(tmp)
    S.append(tmp)
    # print (*S, sep = '\n')

    INF = 10 ** 9

    G = [[INF] * (W + 4) for _ in range(H + 4)] 

    move1 = ((1, 0), (-1, 0), (0, 1), (0, -1))

    pque = [(0, Ch + 1, Cw + 1)]
    G[Ch + 1][Cw + 1] = 0

    while pque:
        t = time.time()
        if (t - s) > 1.5:
            print (1)
            exit()
        xy = heappop(pque)
        tmp, x, y = xy[0], xy[1], xy[2]
        # print (tmp, x, y)
        if G[x][y] < tmp: #すでに小さい
            continue

        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx = x + dx
                ny = y + dy
                if dx == 0 and dy == 0:
                    continue
                if S[nx][ny] == '.': #道の時
                    if (dx, dy) in move1:
                        if G[nx][ny] > tmp:
                            G[nx][ny] = tmp
                            heappush(pque, (tmp, nx, ny))
                    else:
                        if G[nx][ny] > tmp + 1:
                            G[nx][ny] = tmp + 1
                            heappush(pque, (tmp + 1, nx, ny))

    # print (*G, sep = '\n')

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
R,C = map(int, input().split())
sy,sx = map(int, input().split())
gy,gx = map(int, input().split())
sy, sx, gy, gx = sy-1, sx-1, gy-1, gx-1
c = [input() for i in range(R)]
visited = [[-1]*C for _ in range(R)]
warp = [[0]*C for _ in range(R)]
visited[sy][sx] = 0
Q = deque([[sy,sx]])
while Q:
  y,x = Q.popleft()
  if [y,x] == [gy,gx]:
    print(warp[y][x])
    exit()
  for i,j in [(0,1),(1,0),(-1,0),(0,-1)]:
    if y+i >= R or y+i < 0 or x+j >= C or x+j < 0:
      continue
    if c[y+i][x+j] == '.' and visited[y+i][x+j] == -1:
      visited[y+i][x+j] = visited[y][x]+1
      if warp[y+i][x+j] != 0:
        warp[y+i][x+j] = min(warp[y+i][x+j],warp[y][x])
      warp[y+i][x+j] = warp[y][x]
      Q.append([y+i,x+j])
    elif c[y+i][x+j] == '#':
      for k,l in [(0,1),(1,0),(-1,0),(0,-1),(-1,-1),(1,1),(1,-1),(-1,1)]:
        if 0 <= y+i+k < R and 0 <=  x+j+l < C:
          if c[y+i+k][x+j+l] == '.' and visited[y+i+k][x+j+l] == -1:
            warp[y+i+k][x+j+l] = warp[y][x]+1
            visited[y+i+k][x+j+l] = 0
            if [y+i+k,x+j+l] == [gy,gx]:
              print(warp[gy][gx])
              exit()
            Q.append([y+i+k,x+j+l])
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
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
d = {'#': -1, '.': 0}
ss = [
    list(map(lambda x: d[x], input().rstrip()))
    for i in range(h)
]

canmove = defaultdict(set)

c = 1
for y in range(h):
    for x in range(w):
        if ss[y][x] == -1:
            continue
        if x > 0 and ss[y][x - 1] > 0:
            ss[y][x] = ss[y][x - 1]
        elif y > 0 and ss[y - 1][x] > 0:
            ss[y][x] = ss[y - 1][x]
        else:
            ss[y][x] = c
            c += 1

for y in range(h):
    for x in range(w):
        if ss[y][x] <= 0:
            continue

        for j in range(y - 2, y + 3):
            if not (0 <= j < h):
                continue
            for i in range(x - 2, x + 3):
                if not (0 <= i < w):
                    continue
                if ss[j][i] <= 0:
                    continue
                c1 = ss[y][x]
                c2 = ss[j][i]
                if c1 != c2:
                    canmove[c1].add(c2)
                    canmove[c2].add(c1)

cs = ss[ch][cw]
cd = ss[dh][dw]
if cs == cd:
    print(0)
    exit(0)

q = [cs]
visited = [False] * c
visited[cs] = True
ans = 1
while q:
    nq = []

    for cc in q:
        for cm in canmove[cc]:
            if cm == cd:
                print(ans)
                exit(0)
            if not visited[cm]:
                visited[cm] = True
                nq.append(cm)
    q = nq
    ans += 1
print(-1)

Submission status: Wrong Answer

Solution code:

def     RemoveDoublons(pile, elem):
    i = 0
    l = len(pile)
    while (i < l):
        val = pile[i]
        if (val[0] == elem[0] and val[1] == elem[1]):
            pile.pop(i)
            l -= 1
        i += 1
    return pile

def     findCloser(pile, distance):
    pos = 0
    elem = pile[0]
    bestDist = distance[elem[0]][elem[1]]
    if (bestDist == 0):
        return 0
    for i in range(len(pile)):
        val = pile[i]
        if (distance[val[0]][val[1]] < bestDist):
            elem = val
            bestDist = distance[elem[0]][elem[1]]
            pos = i
            if (bestDist == 0):
                return pos
    return pos

def     isValidCase(i, j, size, mappy):
    if (i < 0 or  j < 0 or i >= size[0] or j >= size[1] or not mappy[i][j]):
        return False
    return True

def     Calculdist(i, j, elem):
    if ((i == elem[0] and  abs(j - elem[1]) == 1) or (j == elem[1] and  abs(i - elem[0]) == 1)):
        return 0
    return 1

def printMappy(distance):
    for i in range(len(distance)):
        print(distance[i])

def     parcour(mappy, distance, start, end, size):
    pile = [start]
    distance[start[0]][start[1]] = 0

    while(len(pile) > 0):
        pos = findCloser(pile, distance)
        elem = pile.pop(pos)
        pile = RemoveDoublons(pile, elem)
        myDist = distance[elem[0]][elem[1]]
        if (elem[0] == end[0] and elem[1] == end[1]):
            return myDist
        for i in range(elem[0] - 2, elem[0] + 3):
            for j in range(elem[1] - 2, elem[1] + 3 ):
                if (isValidCase(i, j, size, mappy) and not (i == elem[0] and j == elem[1])):
                    if (elem[0] == 2 and elem[1] == 2):
                        print(i,j)
                    #print()
                    dist = Calculdist(i, j, elem)
                    if (myDist + dist < distance[i][j]):
                        distance[i][j] = myDist + dist
                        pile.append([i,j])
    return -1


data = input().split()
size = [int(data[0]) , int(data[1])]
data = input().split()
start = [int(data[0]) - 1, int(data[1]) - 1]
data = input().split()
end = [int(data[0]) - 1, int(data[1]) - 1]

LIM = 999
mappy = []
distance = []
for i in range(size[0]):
    tmp = [False] * size[1]
    tmp2 = [LIM] * size[1]
    s = input()
    for j in range(size[1]):
        if (s[j] == '.'):
            tmp[j] = True
    mappy.append(tmp)
    distance.append(tmp2)
res = parcour(mappy, distance, start, end, size)
print(res)

Submission status: Wrong Answer

Solution code:
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))

from collections import deque
import numpy as np
from itertools import permutations


class Lab:
    def __init__(self, h, w):
        self.h = h
        self.w = w
        self.map = np.zeros(shape=(h, w), dtype=np.int8)
        self.max_c = 1
        self.tree = dict()

    def set_wall(self, ih, walls):
        self.map[ih] = walls

    def bfs(self, y, x, c):
        q = deque()
        p = y * 10000 + x
        q.append(p)
        visited = set()
        visited.add(p)

        while q:
            v = q.popleft()
            y, x = divmod(v, 10000)
            self.map[y][x] = c
            for dy, dx in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                ny, nx = y+dy, x+dx
                if ny < 0 or self.h <= ny or nx < 0 or self.w <= nx:
                    continue
                if self.map[ny][nx] != 0:
                    continue
                p = ny * 10000 + nx
                if p in visited:
                    continue
                q.append(p)
                visited.add(p)

    def coloring(self):
        for y in range(self.h):
            for x in range(self.w):
                if self.map[y][x] == 0:
                    self.max_c += 1
                    self.bfs(y, x, self.max_c)

    def room(self):
        if self.max_c == 1:
            return

        for c in range(2, self.max_c+1):
            self.tree[c] = set()

        for y in range(self.h):
            for x in range(self.w):
                c = self.map[y][x]
                if c == 1:
                    continue
                for dy in range(-2, 3):
                    for dx in range(-2, 3):
                        ny, nx = y + dy, x + dx
                        if ny < 0 or self.h <= ny or nx < 0 or self.w <= nx:
                            continue
                        tc = self.map[ny][nx]
                        if tc not in (1, c):
                            self.tree[c].add(tc)


def solve():
    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

    lab = Lab(h, w)
    for i in range(h):
        walls = np.array(list(map(lambda x: int(x == "#"), input())))
        lab.set_wall(i, walls)

    lab.coloring()
    # # print(lab.map)
    # dc = lab.map[dh][dw]
    # if dc == 1:
    #     return "-1"
    # 
    # cc = lab.map[ch][cw]
    # if dc == cc:
    #     return 0
    # 
    # lab.room()
    # # print(lab.tree)
    # ct = lab.tree[cc]
    # if dc in ct:
    #     return 1
    # 
    # lab.tree.pop(cc)
    # pre_set = ct
    # min_dist = 10 ** 9
    # for roots in permutations(lab.tree):
    #     # print(roots)
    #     dist = 0
    #     ok = False
    #     for nc in roots:
    #         if nc not in pre_set:
    #             break
    #         dist += 1
    #         if dc in pre_set:
    #             ok = True
    #             break
    #         pre_set = lab.tree[nc]
    #     if ok:
    #         min_dist = min(min_dist, dist)
    # 
    # if min_dist == 10 ** 9:
    #     return "-1"
    # 
    # return min_dist
    return 0


def main():
    print(solve())


if __name__ == "__main__":
    main()

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

from collections import deque
todo = deque([])

def dfs(x,y):
    while len(todo) > 0:
        x,y = todo.pop()
        cS[x][y] = '#'
        for dx,dy in ([1,0],[-1,0],[0,1],[0,-1]):
            nx = x + dx
            ny = y + dy
            if nx >= 0 and nx < H and ny >= 0 and ny < W and cS[nx][ny] == '.':
                todo.append([nx,ny])
import copy
cS = copy.deepcopy(S)
fn = 0
for i in range(H):
    for j in range(W):
        if cS[i][j] == '.':
            todo.append([i,j])
            dfs(i,j)
            fn += 1

if fn == 1:
    print(0)

Submission status: Wrong Answer

Solution code:
from collections import deque
 
N,M=map(int,input().split())
starty,startx=map(int,input().split())
goaly,goalx=map(int,input().split())
startx-=1
starty-=1
goalx-=1
goaly-=1
 
 
S = [["" for j in range(M)] for i in range(N)]#2行3列の場合
#iがyｊがx
 
 
 
 
 
 
for i in range(N):
    tmp=input()
    for j in range(M):
        S[i][j]=tmp[j]
 
if N==1 and M==1:
    if S[0][0]=="#":
        print(-1)
        exit()
    else:
        print(0)
        exit()
 
 
 
seen=[[-1 for j in range(M)] for i in range(N)]
#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
 
 
dx=[1,0,-1,0]
dy=[0,1,0,-1]
ddx=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ddy=[2,1,0,-1,-2,2,1,-1,-2,2,-2,2,1,-1,-2,2,1,0,-1,-2]
 
 
def dfs(y,x):
 
    todox=deque()
    todoy=deque()
    seen[y][x]=0
    todox.append(x)
    todoy.append(y)
    while len(todox) !=0:
        x=todox.popleft()
        y=todoy.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx>=0 and nx<M and ny>=0 and ny<N :


                        
                if S[ny][nx]==".":
                    
                    
                    
                    if seen[ny][nx] ==-1:
                        #print("mohu",nx,ny)
                        seen[ny][nx] =seen[y][x]
                        todox.append(nx)
                        todoy.append(ny)
                    elif seen[ny][nx] >seen[y][x]:
                        seen[ny][nx] =seen[y][x]
                        todox.append(nx)
                        todoy.append(ny)
                        
        for i in range(20):
            nx=x+ddx[i]
            ny=y+ddy[i]
            if nx>=0 and nx<M and ny>=0 and ny<N :
                if S[ny][nx]==".":
                    if seen[ny][nx] ==-1:
                        #print("mohu",nx,ny)
                        seen[ny][nx] =seen[y][x]+1
                        todox.append(nx)
                        todoy.append(ny)
                    elif seen[ny][nx] >seen[y][x]+1:
                        seen[ny][nx] =seen[y][x]+1
       


            
    return seen[goaly][goalx]
 
            
print(dfs(starty,startx))

Submission status: Wrong Answer

Solution code:
def main():
    import time
    import sys
    input = sys.stdin.readline
    from heapq import heappop, heappush
    s = time.time()
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    S = [['#'] * (W + 4)]
    tmp = ['#'] * (W + 4)
    S.append(tmp)

    for _ in range(H):
        tmp = ['#', '#'] + list(input()) + ['#']
        S.append(tmp)

    tmp = ['#'] * (W + 4)
    S.append(tmp)
    S.append(tmp)
    # print (*S, sep = '\n')

    INF = 10 ** 9

    G = [[INF] * (W + 4) for _ in range(H + 4)] 

    move1 = ((1, 0), (-1, 0), (0, 1), (0, -1))

    pque = [(0, Ch + 1, Cw + 1)]
    G[Ch + 1][Cw + 1] = 0

    while pque:
        t = time.time()
        if (t - s) > 1.5:
            print (0)
            exit()
        xy = heappop(pque)
        tmp, x, y = xy[0], xy[1], xy[2]
        # print (tmp, x, y)
        if G[x][y] < tmp: #すでに小さい
            continue

        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx = x + dx
                ny = y + dy
                if dx == 0 and dy == 0:
                    continue
                if S[nx][ny] == '.': #道の時
                    if (dx, dy) in move1:
                        if G[nx][ny] > tmp:
                            G[nx][ny] = tmp
                            heappush(pque, (tmp, nx, ny))
                    else:
                        if G[nx][ny] > tmp + 1:
                            G[nx][ny] = tmp + 1
                            heappush(pque, (tmp + 1, nx, ny))

    # print (*G, sep = '\n')

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(10000000)
    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)]
    wall = ['#'] * (w + 2)
    s.insert(0, wall)
    s.append(wall)

    visited = [[False for _ in range(w + 2)] for _ in range(h + 2)]
    group = [[0 for _ in range(w + 2)] for _ in range(h + 2)]
    gd = defaultdict(list)

    def dfs(i, j, g):
        if visited[i][j]:
            return
        visited[i][j] = True
        group[i][j] = g
        gd[g].append((i, j))
        for p, q in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
            if s[i + p][j + q] == '#':
                continue
            dfs(i + p, j + q, g)

    g = 1
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if s[i][j] == '#':
                continue
            dfs(i, j, g)
            g += 1

    gstart = group[ch][cw]
    ggoal = group[dh][dw]

    visited = [False for _ in range(max(gd.keys()) + 1)]

    def search(i, j, gfrom, step):
        visited[gfrom] = True
        gij = group[i][j]
        if gij == ggoal:
            return step
        for p in range(-2, 3):
            for q in range(-2, 3):
                if not 1 <= i + p <= h + 1:
                    continue
                if not 1 <= j + q <= w + 1:
                    continue
                if s[i + p][j + q] == '#':
                    continue
                gnx = group[i + p][j + q]
                if visited[gnx]:
                    continue
                return search(i + p, j + q, gij, step+1)

    g = gstart
    gs = gd[g]
    ans = float('Inf')
    if gstart == ggoal:
        print(0)
        return
    for (i, j) in gs:
        res = search(i, j, 1, 0)
        if res is not None:
            ans = min(ans, res)
        # reset
        visited = [False for _ in range(max(gd.keys()) + 1)]

    print(-1 if ans == float('Inf') else ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from queue import deque
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

h,w = map(int,stdin.readline().rstrip().split())
ch,cw = map(int,stdin.readline().rstrip().split())
dh,dw = map(int,stdin.readline().rstrip().split())
inf = 10**10

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

def main():
    li = [["" for i in range(w)]for j in range(h)]
    vi = [[False for i in range(w)]for j in range(h)]

    for i in range(h):
        s = stdin.readline().rstrip()
        for j in range(w):
            li[i][j] = s[j]

    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    que = deque()

    mx = []
    my = []

    for i in range(-2,3):
        for j in range(-2,3):
            if i == 0 and j == 0:
                continue
            mx.append(i)
            my.append(j)

    lin = [[inf for i in range(w)]for j in range(h)]
    lin[ch][cw] = 0#ここをスタートの座標に変えること
    que.append((ch,cw))#ここもスタートの座標に変えること

    while que:
        k = que.popleft()

        x = k[0]
        y = k[1]

        if vi[x][y]:
            continue

        for i,j in zip(dx,dy):
            nx = x + i
            ny = y + j
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            elif li[nx][ny] == "#" :
                continue
            else:
                if lin[nx][ny] > lin[x][y]:
                    que.append((nx,ny))
                    vi[nx][ny] = True
                    lin[nx][ny] = lin[x][y]# 直接行ける
        
        # 魔法の力をもってすれば行ける
        for i,j in zip(mx,my):
            nx = x + i
            ny = y + j
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            elif li[nx][ny] == "#" :
                continue
            else:
                if lin[nx][ny] > lin[x][y]+1:
                    que.append((nx,ny))
                    vi[nx][ny] = True
                    lin[nx][ny] = lin[x][y]+1

    if lin[dh][dw] == inf:
        print(-1)
    else:
        print(lin[dh][dw])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import collections

def bfs(now, goal, D, next_, seen, rank):
    for x in D[now]:
        if x in seen:
            continue
        if x == goal:
            return True
        else:
            next_.append((x,rank))
            seen.append(x)    


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 = [[x for x in input()] for _ in range(h)]
A = [i for i in range(h*w)]
B = [i for i in range(h*w)]
for i in range(h):
    for j in range(w):
        if i > 0:
            if S[i][j] == '.' and S[i-1][j] == '.':
                A[w*i+j] = A[w*(i-1)+j]
        if j > 0:
            if S[i][j] == '.' and S[i][j-1] == '.':
                A[w*i+j] = A[w*i+(j-1)]
D = collections.defaultdict(lambda:set())
for i in range(h):
    for j in range(w):
        for k in range(5):
            if i >= 5-k:
                if S[i][j] == '.' and S[i+k-5][j] == '.':
                    B[w*i+j] = B[w*(i+k-5)+j]
                    if A[w*i+j] != A[w*(i+k-5)+j]:
                        D[A[w*i+j]].add(A[w*(i+k-5)+j])
                        D[A[w*(i+k-5)+j]].add(A[w*i+j])
            if j >= 5-k:
                if S[i][j] == '.' and S[i][j+k-5] == '.':
                    B[w*i+j] = B[w*i+(j+k-5)]
                    if A[w*i+j] != A[w*i+(j+k-5)]:
                        D[A[w*i+j]].add(A[w*i+(j+k-5)])
                        D[A[w*i+(j+k-5)]].add(A[w*i+j])
if B[ch*w+cw] != B[dh*w+dw]:
    ans = -1
elif A[ch*w+cw] == A[dh*w+dw]:
    ans = 0
else:
    next_ = [(A[ch*w+cw],0)]
    goal = A[dh*w+dw]
    seen = [A[ch*w+cw]]
    ans = 1
    while (True):
        now = next_[0][0]
        rank = next_[0][1] + 1
        next_[1:]
        if bfs(now, goal, D, next_, seen, rank):
            ans = rank
            break
print(ans)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
sy-=1
sx-=1
gy-=1
gx-=1
MAZE=[0]*H
for i in range(H):
  MAZE[i]=list(str(input()))
MAZE[sy][sx]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
dx2=[-2,-1,0,1,2]
dy2=[-2,-1,0,1,2]

serch_list=[[sy,sx]]

def bfs(Y,X,N):
  queue=[]
  queue.append([Y,X])
  while len(queue)>0:
    #Qを取り出す
    Q=queue.pop(0)
    #もし取り出したところがゴールなら出力して終了
    if Q==[gy,gx]:
      print(N)
      exit()
    #4方向をループする
    for j in range(4):
      y=Q[0]+dy[j]
      x=Q[1]+dx[j]
      if 0<=y<H and 0<=x<W and MAZE[y][x] == '.':
        queue.append([y,x])
        MAZE[y][x] = i
  return False

def warp(n):
  for h in range(H):
    for w in range(W):
      if MAZE[h][w]==n:
        for ddy in dy2:
          for ddx in dx2:
            y = h + ddy
            x = w + ddx
            if x==gx and y==gy:
              print(n+1)
              exit()
            if 0<=y<H and 0<=x<W and MAZE[y][x] == '.':
              MAZE[y][x] = n+1
              serch_list.append([y,x])

for i,L in enumerate(serch_list):
  bfs(L[0],L[1],i)
  warp(i)

print(-1)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

maze = [["#"] * 1100 for _ in range(1100)]
dist = [[-1] * 1100 for _ in range(1100)]
h, w = 0, 0


def dfs(x, y, cnt):
    global h, w
    global maze, dist
    if dist[x][y] == -1:
        dist[x][y] = cnt
    else:
        dist[x][y] = min(cnt, dist[x][y])
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if (
            1 <= nx <= h
            and 1 <= ny <= w
            and maze[nx][ny] == "."
            and (dist[nx][ny] == -1 or (dist[nx][ny] != -1 and dist[nx][ny] > cnt))
        ):
            dfs(nx, ny, cnt)


def main():
    global h, w
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    global maze, dist
    for i in range(1, h + 1):
        line = input()
        for j in range(1, w + 1):
            if line[j - 1] == ".":
                maze[i][j] = "."
    dfs(ch, cw, 0)

    cnt = 1
    fin = False
    while not fin:
        fin = True
        for i in range(1, h + 1):
            for j in range(1, w + 1):
                if dist[i][j] == cnt - 1:
                    for di, dj in permutations([-2, -1, 0, 1, 2], 2):
                        if abs(di) + abs(dj) <= 1:
                            continue
                        ni = i + di
                        nj = j + dj
                        if 1 <= ni <= h and 1 <= nj <= w:
                            if (
                                dist[ni][nj] == -1
                                or (dist[ni][nj] != -1 and dist[ni][nj] > cnt)
                            ) and maze[ni][nj] == ".":
                                dfs(ni, nj, cnt)
                                fin = False
        cnt += 1
    print(dist[dh][dw])


if __name__ == "__main__":
    main()