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
class G:
    def __init__(self, c):
        self.c = c
        self.reached = False
        self.searched = False
        self.range = 0

    
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()]
S = [['.' for j in range(W)] for i in range(H) ]
for i in range(H):
    tmp = list(input())
    for j in range(W):
        S[i][j] = G(tmp[j])

def neighbors(y, x):
    s = []
    if x != 0:
        if S[y][x-1].reached == False and S[y][x-1].c == '.':
            s.append((y, x-1))
    if x != W-1:
        if S[y][x+1].reached == False and S[y][x-1].c == '.':
            s.append((y, x+1))
    if y != 0:
        if S[y-1][x].reached == False  and S[y][x-1].c == '.':
            s.append((y-1, x))
    if y != H-1:
        if S[y+1][x].reached == False  and S[y][x-1].c == '.':
            s.append((y+1, x))
    return s

def jump(x, y, d):
    S[y][x].searched = True
    for i in range(max(x-2, 0), min(x+3, W)):
        for j in range(max(y-2, 0), min(y+3, H)):
            if S[j][i].reached == False and S[j][i].c == '.':
                d.append((j, i))

def DFS(S, d):
    while True:
        if len(d) == 0:
            break
        q = d.popleft()
        S[q[0]][q[1]].reached = True
        for each in neighbors(q[0], q[1]):
            S[each[0]][each[1]].reached = True
            if S[each[0]][each[1]].c == '.':
                d.append(each)

counter = 0
d = deque([])
S[Ch][Cw].reached = True
d.append((Ch, Cw))
flag = False
while True:
    if len(d) == 0:
        flag = True
        break
    DFS(S, d)
    if S[Dh][Dw].reached:
        break
    counter += 1
    for i in range(H):
        for j in range(W):
            if S[i][j].reached and S[i][j].c == '.' and S[i][j].searched == False:
                jump(j, i, d)


if flag:
    print(-1)
else:
    print(counter)

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappush, heappop
from heapq import _heapify_max, _heappop_max
import heapq

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)

"""
method:
    heapify(x): ヒープに変換
    heappush(heap, item): itemをheapにpush
    heappop(heap): heapから最小値を取得 空の場合はIndexError
note:
    max heapにする場合は、prefix: _ とsuffix: _maxをつければ良い
"""

def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    inf = 10**7
    dp = [[inf]*w for _ in range(h)]
    s = [input() for _ in range(h)]
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    dxy = list(zip(dx, dy))
    
    rx = (2, 1, 0, -1, -2)
    ry = (2, 1, 0, -1, -2)
    
    dp[ch-1][cw-1] = 0
    
    q = []
    heappush(q, (0, ch-1, cw-1))
    flag = False
    for i in range(h):
        if "#" in s[i]:
            flag = True
            break
    if flag == False:
        print(-1)
        return
    while q:
        cnt = 0
        cost, px, py = heappop(q)
        for xi, yj in dxy:
            x = px + xi
            y = py + yj
            if x >= h or x < 0 or y >= w or y < 0 or s[x][y] == "#":
                continue
            cnt += 1
            if dp[x][y] > cost:
                dp[x][y] = cost
                heappush(q, (cost, x, y))
        
                
        if cnt != 4:
            cost += 1
            for di in rx:
                x = px + di
                if x >= h or x < 0:
                    continue
                sx = s[x]
                dpx = dp[x]
                for dj in ry:
                    y = py + dj
                    if y >= w or y < 0 or sx[y] == "#":
                        continue
                    if dpx[y] > cost:
                        dpx[y] = cost
                        heappush(q, (cost, x, y))
    if dp[dh-1][dw-1] == inf:
        print(-1)
    else:
        print(dp[dh-1][dw-1])

if __name__ == "__main__":
    main()

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

que = deque()
que.append([ch - 1, cw - 1, 0])
memo = {}
memo[(ch - 1, cw - 1)] = 0
ans = float("inf")
while len(que) != 0:
    sh, sw, count = que.popleft()
    #print(sh, sw, count)
    #print(sh, sw, count)
    # if sh == dh - 1 and sw == dw - 1:
    #     if ans > count:
    #         memo[(sh, sw)] = count
    #         ans = count
    #     continue
    for ph, pw in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
        if 0 <= sh + ph < h and 0 <= sw + pw < w:
            if sh + ph == dh - 1 and sw + pw == dw - 1:
                print(count)
                exit()
            if (sh + ph, sw + pw) in memo and memo[(sh + ph, sw + pw)] <= count:
                continue
            if slist[sh + ph][sw + pw] == ".":
                que.append([sh + ph, sw + pw, count])
                memo[(sh + ph, sw + pw)] = count

    for ph in range(-2, 3):
        for pw in range(-2, 3):
            if [ph, pw] not in [[-1, 0], [1, 0], [0, 1], [0, -1], [0, 0]]:
                if 0 <= sh + ph < h and 0 <= sw + pw < w:
                    if sh + ph == dh - 1 and sw + pw == dw - 1:
                        print(count + 1)
                        exit()
                    if (sh + ph, sw + pw) in memo and memo[(sh + ph, sw + pw)] <= count + 1:
                        continue
                    if slist[sh + ph][sw + pw] == ".":
                        que.append([sh + ph, sw + pw, count + 1])
                        memo[(sh + ph, sw + pw)] = count + 1


print(-1)

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

import sys

stack = [[Ch-1,Cw-1]] #現在地を指定
visited_stack = [[Ch-1,Cw-1]]
visited = [[0 for w in range(W)] for h in range(H)]
visited[Ch-1][Cw-1]=1
S[Dh-1][Dw-1]='G'

dh_dw=[[1,0],[0,1],[-1,0],[0,-1]]
warph_warpw=[]
for i in range(-2,3):
    for j in range(-2,3):
        if i!=0 and j!=0:
            warph_warpw.append([i,j])

warp_cnt=0
while stack:
    h,w = stack.pop() #現在地
    for i in range(4):
        nh,nw=h+dh_dw[i][0],w+dh_dw[i][1] #移動後の現在地
        #print(nh,nw,visited[nh][nw],S[nh][nw])
        if 0<=nh<H and 0<=nw<W and visited[nh][nw] == 0 and S[nh][nw] != '#':
            #print(nh,nw)
            visited[nh][nw] = 1
            stack.append([nh,nw])
            visited_stack.append([nh,nw])
    
    #stackがなくなったら
    if len(stack)==0:
        warp_cnt+=1
        while visited_stack:
            h,w=visited_stack.pop()
            for i in range(len(warph_warpw)):
                nh,nw = h+warph_warpw[i][0],w+warph_warpw[i][1]
                if 0<=nh<H and 0<=nw<W and visited[nh][nw] == 0 and S[nh][nw] != '#':
                    visited[nh][nw] = 1
                    stack.append([nh,nw])
                    #visited_stack.append([nh,nw])
    
    if visited[Dh-1][Dw-1]==1: #Gowlに到達
        print(warp_cnt)
        sys.exit()

print("No")

Submission status: Wrong Answer

Solution code:
import os
import heapq
import sys
import math
import operator
from collections import defaultdict,deque
from io import BytesIO, IOBase


"""def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)"""

"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""



def inpt():
    return [int(k) for k in input().split()]


def main():
    n,m=map(int,input().split())
    p1,p2=map(int,input().split())
    t1, t2 = map(int, input().split())
    ar=[]
    for i in range(n):
        ar.append(list(input()))
    if(ar[t1-1][t2-1]=='#'):
        print('-1')
        exit()
    st1=set()
    dif=[(-1,0),(1,0),(0,-1),(0,1)]
    ct=0
    for p in range(n):
        for r in range(m):
            if(ar[p][r]=='.'):
                ct+=1
                q = deque()
                q.append((p,r))
                while(q):
                    i,j=q.popleft()
                    ar[i][j] = ct
                    for a,b in dif:
                        if(0<=i+a<n and 0<=j+b<m):
                            if(ar[i+a][j+b]=='.'):
                                q.append((i+a,j+b))

    start=ar[p1-1][p2-1]
    end=ar[t1-1][t2-1]
    d=defaultdict(int)
    st=set()
    q=deque()
    if(start==end):
        print(0)
        exit()
    for i in range(n):
        for j in range(m):
            if(ar[i][j]==start):
                st.add((i,j))
                q.append((i,j))
    # print(st)
    # print(q)
    # print(d)
    # d[start]=0
    ans=-1
    while(q):
        i,j=q.popleft()
        st.remove((i,j))
        for x in range(1,3):
            for y in range(1,3):
                temp=[(-x,y),(-x,-y),(x,-y),(x,y)]
                for a,b in temp:
                    c1,c2=i+a,j+b
                    if(0<=c1<n and 0<=c2<m and ar[c1][c2]!='#' and ar[c1][c2]!=ar[i][j]):
                        if((c1,c2) in st):
                            continue

                        if((c1,c2) in d):
                            d[ar[c1][c2]]=min(d[ar[c1][c2]],d[ar[i][j]]+1)
                        else:
                            d[ar[c1][c2]]=d[ar[i][j]]+1
                        st.add((c1,c2))
                        q.append((c1,c2))
                        if(ar[c1][c2]==end):
                            ans=d[ar[c1][c2]]
    print(ans)



    # print(start,end)
    # for i in ar:
    #     print(i)












BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class Grid:
    def __init__(self, H, W, grid, road_wall=(".", "#")):
        self.road, self.wall = road_wall
        self.H = H
        self.W = W
        self.grid = grid
        self.parent = [[-1] * self.W for _ in range(self.H)]
        self.move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補
        self.move2 = dict()
        self.move2[(1,0)] = [(2,-2),(2,-1),(2,0),(2,1),(2,2),(1,1),(1,-1)]
        self.move2[(-1,0)] = [(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,-2),(-1,-1),(-1,1)]
        self.move2[(0,1)] = [(2,2),(1,2),(0,2),(-1,2),(-2,2),(-1,1),(1,1)]
        self.move2[(0,-1)] = [(-2,-2),(1,-2),(0,-2),(-1,-2),(2,-2),(1,-1),(-1,-1)]

    def bfs(self, start=(0,0), goal=-3, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if save:
            parent = self.parent
        else:
            parent = [[-1] * self.W for _ in range(self.H)]
        p, t = start, time
        parent[p[0]][p[1]] = -2
        next_set = deque([(p, t)])
        broken_set = deque([])
        while next_set:
            while next_set:
                p, t = next_set.popleft()
                h, w = p
                for dh, dw in self.move:
                    q = (h + dh, w + dw)
                    if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                        continue
                    if parent[q[0]][q[1]] != -1:
                        continue
                    if q == goal:
                        return t
                    parent[q[0]][q[1]] = p
                    if self.grid[q[0]][q[1]] == self.wall:         # 壁があったら進まない
                        for dh2, dw2 in self.move2[(dh,dw)]:
                            r = (h + dh2, w + dw2)
                            broken_set.append((r, t))
                        continue
                    #### (debug code) ######
                    # self.debug(start, goal, q, t)
                    ########################
                    next_set.append((q, t))
            while broken_set:
                q, t = broken_set.popleft()
                if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                    continue
                if parent[q[0]][q[1]] != -1:
                    continue
                if self.grid[q[0]][q[1]] == self.wall:  # 壁があったら進まない
                    continue
                if q == goal:
                    return t + 1
                #### (debug code) ######
                # self.debug(start, goal, q, t)
                ########################
                next_set.append((q, t+1))
        return -1

    def debug(self, start, goal, p, t):
        player = p
        debug_grid = list(list(self.grid[h]) for h in range(self.H))
        if start != (None, None):
            debug_grid[start[0]][start[1]] = "S"
        if goal != -3:
            debug_grid[goal[0]][goal[1]] = "G"
        debug_grid[player[0]][player[1]] = "P"
        print("~~~~~~~~~ t = " + str(t + 1) + "  ~~~~~~~~")
        for debug_h in range(self.H):
            print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W)))


############################################################################################

from collections import deque
import sys
input = sys.stdin.readline

road, wall = ".", "#"                         # (進行可能を意味する記号, 進行不可を意味する記号)

H, W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)
x, y = map(int, input().split())
start = (x-1,y-1)
x, y = map(int, input().split())
goal = (x-1,y-1)
grid = []
for h in range(H):
    grid.append(input().rstrip())

g = Grid(H, W, grid, (road, wall))
res = g.bfs(start=start, goal=goal)
print(res)

"""
5 6
5 6
1 1
.###.#
######
#..##.
######
#####.
"""

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

import heapq

#点の数が10**5のオーダー以下で使える
#計算量はO(MlogN) M : 辺の数、N　：　頂点数
#頂点sからの各頂点への最短距離を出力
def dijkstra(s, n, edge): #s:始点、n:頂点の数、edge:重み付き辺の配列（edge[i]:iから出るtuple[重み、行き先]の配列)
    INF = 10**20
    d = [INF]*n # d[i]: sと点iとの距離
    used = [True]*n #Trueは未確定
    d[s] = 0 #初期条件
    used[s] = False # 初期条件
    edge_list = []
    for a, b in edge[s]:
        heapq.heappush(edge_list, a*(10**6)+b) #heapqの中に重みと辺の抱き合わせた情報を入れる
    while len(edge_list):
        min_edge = heapq.heappop(edge_list) #まだ使われていない頂点の中から最小の重みのものを取りだす
        if not used[min_edge%(10**6)]: # 確定していたらcontinue、確定していない時のみ以下の処理を行う
            continue
        v = min_edge%(10**6) #行き先の情報を復元
        d[v] = min_edge // (10**6) #重みの情報を復元し、sとvの最短距離d[v]を更新する
        used[v] = False
        for e in edge[v]:
            if used[e[1]]: #その行き先がまだ未確定の場合
                heapq.heappush(edge_list, (e[0]+d[v])*(10**6) + e[1])
        
    return d
#d[i] : 始点から i までの距離
h, w = map(int, input().split())
edge = [[] for _ in range((h+4)*(w+4))] # edge:重み付き辺の配列（edge[i]:iから出るtuple(重み、行き先)の配列)
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
start = (ch, cw)
end = (dh, dw)
g = []
g.append([1]*(w+4))
g.append([1]*(w+4))
for i in range(h):
    s = list(input())
    tmp = [1,1]
    for j in s:
        if j == '.':
            tmp.append(0)
        else:
            tmp.append(1)
    tmp.append(1)
    tmp.append(1)
    g.append(tmp)
g.append([1]*(w+4))
g.append([1]*(w+4))
#print(g)
def pp(height, width):
    return height*(w+4)+width
d = []
for i in range(-2, 3):
    for j in range(-2,3):
        if i < 0 and j < 0:
            continue
        d.append((i, j))
d2 = [(1, 0), (0,1)]

#print(d2)
for i in range(2, h+2):
    for j in range(2, w+2):
        for q in d:
            x, y = q
            if g[i][j] == 0 and g[i+x][j+y] == 0:
                edge[pp(i, j)].append((1, pp(i+x, j+y)))
        for q in d2:
            x, y = q
            if g[i][j] == 0 and g[i+x][j+y] == 0:
                edge[pp(i, j)].append((0, pp(i+x, j+y)))
#print(edge)
                
d = dijkstra(pp(ch+1, cw+1), (h+4)*(w+4), edge)

if d[pp(dh+1, dw+1)] >= 10**20:
    print(-1)
    #print(d[pp(dh+1, dw+1)])
    #print(pp(ch+1, cw+1))
    #print(pp(dh+1, dw+1))
else:
    print(d[pp(dh+1, dw+1)])

Submission status: Wrong Answer

Solution code:
from collections import deque

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

C = list(map(int,input().split()))
D = list(map(int,input().split()))

S = [input() for i in range(H)]

ido = [[1,0],[0,1],[-1,0],[0,-1]]

warp = [[2,2],[2,1],[1,2],[0,2],[2,0],[-2,-2],[-2,-1],[-1,-2],[0,-2],[-2,0],[2,-2],[2,-1],[1,-2],[-2,2],[-2,1],[-1,2],[1,1],[1,-1],[-1,1],[-1,-1]]

d = deque()
d.append([C[1]-1,C[0]-1])
cost = [[100000000 for i in range(W)] for j in range(H)]
flg = [[-1 for i in range(W)] for j in range(H)]

cost[C[0]-1][C[1]-1] = 0
flg[C[0]-1][C[1]-1] = 1

while d:
    x,y = d.popleft()
    for dx, dy in ido:
        nx = x + dx
        ny = y + dy

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

        if  S[ny][nx] == "#":
            continue

        cost[ny][nx] = min(cost[y][x],cost[ny][nx])
        if flg[ny][nx] != -1 :
            continue
        d.append([nx,ny])
        flg[ny][nx] = 1

    for dx, dy in warp:
        nx = x + dx
        ny = y + dy

        if 0 > nx or W <= nx or 0 > ny or H <= ny:
            continue
        if  S[ny][nx] == "#":
            continue

        cost[ny][nx] = min(cost[y][x]+1, cost[ny][nx])
        if flg[ny][nx] != -1:
            continue
        d.append([nx, ny])
        flg[ny][nx] = 1

answer = cost[D[0]-1][D[1]-1]
if answer == 100000000:
    print(-1)
else:
    print(answer)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(int(10e7))

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [None]*(H+4)
S[0] = S[1] = S[H+2] = S[H+3] = ["#"]*(W+4)
for i in range(2, H+2):
    S[i] = ["#"] + ["#"] + list(input()) + ["#"] + ["#"]

Ch += 1
Cw += 1
Dh += 1
Dw += 1

del_h = Dh - Ch
del_w = Dw - Cw

ans = int(10e9)
# print("\n".join(map(str, S)))

def warp(i, j, nxt):
    for h in range(i-2, i+3):
        for w in range(j-2, j+3):
            # print(h, w, i, j)
            # print(S[h][w])
            if S[h][w] == ".":
                nxt.append([h, w, 1])
    
    return 

def dfs(i, j, S, cnt):
    if i == Dh and j == Dw:
        global ans
        ans = min(ans, cnt)
        return 
    
    no_warp = 0

    S[i][j] = "#"
    nxt = list()
    if S[i][j-1] == ".":
        nxt.append([i, j-1, 0])
        no_warp = 1
    if S[i][j+1] == ".":
        nxt.append([i, j+1, 0])
        no_warp = 1
    if S[i-1][j+1] == ".":
        nxt.append([i-1, j, 0])
        no_warp = 1
    if S[i+1][j] == ".":
        nxt.append([i+1, j, 0])
        no_warp = 1
    if no_warp == 0:
        warp(i, j, nxt)
    

    for point in nxt:
        dfs(point[0], point[1], S, cnt+point[2])
    
    # S[i][j] = "."

dfs(Ch, Cw, S, 0)
if ans == int(10e9):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
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 make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

h,w = lr()
ch,cw = lr()
ch-=1
cw-=1
dh, dw = lr()
dh-=1
dw-=1
s = [input() for i in range(h)]
visited = [[inf for j in range(w)] for i in range(h)]
visited[ch][cw] = 0
q = deque([[ch, cw]])
dq = deque([[ch, cw]])
dir = [[0,1], [0,-1], [-1,0], [1,0]]
while q:
    y,x = q.popleft()
    c = visited[y][x]
    for dy,dx in dir:
        ny,nx = y+dy,x+dx
        if 0<=ny<h and 0<=nx<w:
            if s[ny][nx] == '.':
                if visited[ny][nx] == inf:
                    visited[ny][nx] = min(c,visited[ny][nx])
                    q.append([ny,nx])
                    dq.append([ny,nx])
    if len(q) == 0:
        # ワープ処理
        while dq:
            ry,rx = dq.popleft()
            ty,tx = ry-2, rx-2
            for i in range(5):
                for j in range(5):
                    ny, nx = ty+i, tx+j
                    if 0<=ny<h and 0<=nx<w:
                        if s[ny][nx]=='.':
                            if visited[ny][nx] == inf:
                                visited[ny][nx] = min(c+1,visited[ny][nx])
                                q.append([ny,nx])
if visited[dh][dw] != inf:
    print(visited[dh][dw])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from functools import reduce
from queue import Queue

H, W = list(map(int, input().split(" ")))
current_h, current_w = list(map(int, input().split(" ")))
current_h -= 1
current_w -= 1
goal_h, goal_w = list(map(int, input().split(" ")))
goal_h -= 1
goal_w -= 1

table = [list(input()) for _ in range(H)]


class DFS:

    def __init__(self, table, current_h, current_w):
        self.table = table
        self.current_h = current_h
        self.current_w = current_w
        self.islands = []
        self.start_island_index = -1
        self.end_island_index = -1

    def delta(self, h, w):
        return [(h+1, w), (h, w-1), (h, w), (h, w+1), (h-1, w)]

    def dfs(self, start_h, start_w):
        next = self.delta(start_h, start_w)
        island = [(start_h, start_w)]
        if start_h == self.current_h and start_w == self.current_w:
            self.start_island_index = len(self.islands)

        for h, w in next:
            if h == self.current_h and w == self.current_w:
                self.start_island_index = len(self.islands)
            if h == goal_h and w == goal_w:
                self.end_island_index = len(self.islands)
            if not(0 <= h < H and 0 <= w < W):
                continue
            elif self.table[h][w] == "#":
                continue
            else:
                island.append((h, w))
                self.table[h][w] = "#"
                next.extend(self.delta(h, w))
        self.islands.append(island)

    def make_islands(self):
        for h in range(H):
            for w in range(W):
                if self.table[h][w] == ".":
                    self.dfs(h, w)

    def delta_five(self, pos):
        delta = []
        h = pos[0]
        w = pos[1]
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                if dh == 0 and dw == 0:
                    continue
                delta.append((h+dh, w+dw))
        return delta

    def make_islands_graph(self):
        islands_graph = []
        for start_island_index in range(len(self.islands)):
            for end_island_index in range(len(self.islands)):
                if start_island_index == end_island_index:
                    continue
                if self.is_connect(self.islands[start_island_index], self.islands[end_island_index]):
                    islands_graph.append((start_island_index, end_island_index))
        return islands_graph

    def is_connect(self, islands_a, islands_b):
        a = set(reduce(lambda a, b: a + b, map(self.delta_five, islands_a)))
        for h, w in islands_b:
            if (h, w) in a:
                return True
        return False

class BFS:

    def __init__(self, length_of_islands, graph, start_island_index, end_island_index):
        self.islands = [0 for i in range(0, length_of_islands)]
        self.graph = graph
        self.start = start_island_index
        self.end = end_island_index

    def bfs(self, start, end):
        q = Queue()
        q.put(start)
        count = 0
        while not q.empty():
            now = q.get()
            if now == end:
                return count
            if self.islands[now] == -1:
                continue
            for s, e in self.graph:
                if self.islands[s] == -1:
                    continue
                if s == now:
                    q.put(e)
            self.islands[now] = -1
            count += 1
        return -1

dfs = DFS(table, current_h, current_w)
dfs.make_islands()
graph = dfs.make_islands_graph()
# bfs = BFS(len(dfs.islands), graph, dfs.start_island_index, dfs.end_island_index)
# print(bfs.bfs(dfs.start_island_index, dfs.end_island_index))

Submission status: Wrong Answer

Solution code:
import collections
import sys
import math
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())
def NIJIGEN(H): return [list(input()) for i in range(H)]
def dfs(i,j):
  if i+1!=H:
    if L[i+1][j]!="#":
      if str(i+1)+" "+str(j) not in finish:
        finish.add(str(i+1)+" "+str(j))
        if L[i+1][j]==".":
          L[i+1][j]=p
          dfs(i+1,j)
        else:
          print(p)
          exit()
  if i!=0:
    if L[i-1][j]!="#":
      if str(i-1)+" "+str(j) not in finish:
        finish.add(str(i-1)+" "+str(j))
        if L[i-1][j]==".":
          L[i-1][j]=p
          dfs(i-1,j)
        else:
          print(p)
          exit()
  if j+1!=W:
    if L[i][j+1]!="#":
      if str(i)+" "+str(j+1) not in finish:
        finish.add(str(i)+" "+str(j+1))
        if L[i][j+1]==".":
          L[i][j+1]=p
          dfs(i,j+1)
        else:
          print(p)
          exit()
  if j!=0:
    if L[i][j-1]!="#":
      if str(i)+" "+str(j-1) not in finish:
        finish.add(str(i)+" "+str(j-1))
        if L[i][j-1]==".":
          L[i][j-1]=p
          dfs(i,j-1)
        else:
          print(p)
          exit()
H,W=MAP()
st1,st2=MAP()
go1,go2=MAP()
L=NIJIGEN(H)
st1-=1
st2-=1
go1-=1
go2-=1
ans=0
L[go1][go2]="$"
for p in range(100000):
  if p==0:
    c=st1
    d=st2
    L[c][d]=p
    finish=set()
    finish.add(str(c)+" "+str(d))
    dfs(c,d)
    continue
  finish2=set([i for i in finish])
  for j in finish2:
    a,b=j.split()
    a=int(a)
    b=int(b)
    for k in range(25):
      n=k//5
      m=k%5
      c=a-2+n
      d=b-2+m
      if 0<=c<H and 0<=d<W:
        if L[c][d]=="." or L[c][d]=="$":
          if L[c][d]=="$":
            print(p)
            exit()
          ans+=1
          L[c][d]=p
          finish=set()
          finish.add(str(c)+" "+str(d))
          dfs(c,d)
print(-1)