Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

1

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

Note that he cannot walk diagonally.

Sample Input 2

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

Sample Output 2

-1

He cannot move from there.

Sample Input 3

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

Sample Output 3

0

No use of magic is needed.

Sample Input 4

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

Sample Output 4

2



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


Sample output:
1

Submission status: Wrong Answer

Solution code:
import sys
INF = 10**18
sys.setrecursionlimit(10**6)
from collections import defaultdict
def li():
    return [int(x) for x in input().split()]
from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

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

def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch-1][Cw-1] = 0
    que = deque([])
    que.append((Cw, Ch))

    while que:
        # print(que)
        # 左から取り出す
        x, y = que.popleft()
        # 通常移動パターン
        for i in range(len(v)):
            nx = x + v[i][0]
            ny = y + v[i][1]
            # バリデーション
            if nx <= 0 or nx > W or ny <= 0 or ny > H:
                continue
            if S[ny-1][nx-1] != '.':
                continue
            # 初探索 or コストが下がる場合
            if costmap[ny-1][nx-1] == -1 or costmap[y-1][x-1] < costmap[ny-1][nx-1]:
                # コストゼロは左から
                que.appendleft((nx, ny))
                costmap[ny-1][nx-1] = costmap[ny-1][nx-1]
        # 特殊移動パターン
        for i in range(x-2, x+3):
            for j in range(y-2, y+3):
                nx, ny = i, j
                # バリデーション
                if nx <= 0 or nx > W or ny <= 0 or ny > H:
                    continue
                if S[ny-1][nx-1] != '.':
                    continue
                # 初探索 or コストが下がる場合
                if costmap[ny-1][nx-1] == -1 or costmap[ny-1][nx-1] < costmap[ny-1][nx-1]:
                    # コスト1は右から
                    que.append((nx, ny))
                    costmap[ny-1][nx-1] = costmap[ny-1][nx-1] + 1
    return costmap

costmap = bfs()
# print(costmap)
print(costmap[Dh-1][Dw-1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Aug 31 10:54:09 2020

@author: Kozu
"""
from collections import deque
import numpy as np    

#標準入力
H, W = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
S = []
for i in range(H):    
  S.append(list(input()))
  
#定数
Wall = -1
WildArea = 9999
#変数
T = np.full([H + 4,W + 4],Wall)
t = 0
Deque = deque()
#右上左下
dx = [1,0,-1,0]
dy = [0,1,0,-1]


#初期処理
for i in range(2):
    C[i] -= 1
    D[i] -= 1
    
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            T[i + 2][j + 2] = Wall
        if S[i][j] == '.':
            T[i + 2][j + 2] = WildArea


T[C[0]][C[1]] = 0
Deque.append(C)


while True:
    n = Deque.pop()
    
    t = T[n[0]][n[1]]
    
    #BFS 幅優先探索
    for i in range(4):
        if T[n[0] + dx[i]][n[1] + dy[i]] == Wall:
            continue
        if T[n[0] + dx[i]][n[1] + dy[i]] <= t:
            continue
        
        T[n[0] + dx[i]][n[1] + dy[i]] = t
        Deque.append([n[0] + dx[i],n[1] + dy[i]])
    
    #Warp　ワープ
    for i in range(-2,3):
        for j in range(-2,3):
            if T[n[0]+ i][n[1] + j] == Wall:
                continue
            if T[n[0]+ i][n[1] + j] <= t + 1:
                continue
            T[n[0]+ i][n[1] + j] = t + 1
            Deque.appendleft([n[0]+ i,n[1] + j])            

    if len(Deque) <= 0:
        break;

            
            
ans = T[D[0]+2][D[1]+2]
if ans == WildArea:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Aug 31 10:54:09 2020

@author: Kozu
"""
from collections import deque
import numpy as np    

#標準入力
H, W = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
S = []
for i in range(H):    
  S.append(list(input()))
  
#定数
Wall = -1
WildArea = 9999
#変数
T = np.full([H + 4,W + 4],Wall)
t = 0
Deque = deque()
#右上左下
dx = [1,0,-1,0]
dy = [0,1,0,-1]


#初期処理
for i in range(2):
    C[i] -= 1
    D[i] -= 1
    
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            T[i + 2][j + 2] = Wall
        if S[i][j] == '.':
            T[i + 2][j + 2] = WildArea


T[C[0]][C[1]] = 0
Deque.append(C)


while True:
    n = Deque.pop()
    
    t = T[n[0]][n[1]]
    
    #BFS 幅優先探索
    for i in range(4):
        if T[n[0] + dx[i]][n[1] + dy[i]] == Wall:
            continue
        if T[n[0] + dx[i]][n[1] + dy[i]] <= t:
            continue
        
        T[n[0] + dx[i]][n[1] + dy[i]] = t
        Deque.append([n[0] + dx[i],n[1] + dy[i]])
    
    #Warp　ワープ
    for i in range(-2,3):
        for j in range(-2,3):
            if T[n[0]+ i][n[1] + j] == Wall:
                continue
            if T[n[0]+ i][n[1] + j] <= t + 1:
                continue
            T[n[0]+ i][n[1] + j] = t + 1
            Deque.appendleft([n[0]+ i,n[1] + j])            

    if len(Deque) <= 0:
        break;

            
            
ans = T[D[0]][D[1]]
if ans == WildArea:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    h, w = map(int,input().strip().split(" "))

    ch, cw = map(int,input().strip().split(" "))
    dh, dw = map(int,input().strip().split(" "))

    def rotate90Clockwise(A):
        N = len(A[0])
        for i in range(N // 2):
            for j in range(i, N - i - 1):
                temp = A[i][j]
                A[i][j] = A[N - 1 - j][i]
                A[N - 1 - j][i] = A[N - 1 - i][N - 1 - j]
                A[N - 1 - i][N - 1 - j] = A[j][N - 1 - i]
                A[j][N - 1 - i] = temp

    ar = []
    for i in range(h):
            temp=input()
            t=[]
            for i in temp:
                t.append(i)
            ar.append(t)
            
            
    sh = min(ch, dh)
    eh = max(ch, dh)
    sw = min(cw, dw)
    ew = max(cw, dw)
    fin = []
    for i in range(sh - 1, eh):
        fin.append(ar[i][sw - 1:ew])

    t1=min((ch,cw),(dh,dw))
    t2=max((ch,cw),(dh,dw))
    if t1[1]>t2[1]:
        rotate90Clockwise(fin)
    n = eh - sh + 1
    m = ew - sw + 1
    inf = 9999999999999999999
    dp = [[inf for _ in range(m + 5)] for _ in range(n + 5)]
    dp[n - 1][m - 1] = 0


    def is_valid(i, j):
        if 0 <= i < n and 0 <= j < m and fin[i][j] == ".":
            return True
        return False

    moves = [(0, 1), (1, 0)]
    magic = [(0, 2), (2, 0), (1, 1), (1, 2), (2, 1), (2, 2)]
    for j in range(m - 1, -1, -1):
        for i in range(n - 1, -1, -1):
            if fin[i][j]=="#":
                dp[i][j]=inf
                continue
            for mov in moves:
                x, y = i + mov[0], j + mov[1]
                if is_valid(x, y):
                    dp[i][j] = min(dp[i][j], dp[x][y]+1)
            for mag in magic:
                x, y = i + mag[0], j + mag[1]
                if is_valid(x, y):
                    dp[i][j] = min(dp[i][j], dp[x][y] + 1)
    if dp[0][0]==inf:
        print(-1)
    else:
        print(dp[0][0])

solve()

Submission status: Wrong Answer

Solution code:
def solve():
    h, w = map(int,input().strip().split(" "))

    ch, cw = map(int,input().strip().split(" "))
    dh, dw = map(int,input().strip().split(" "))

    def rotate90Clockwise(A):
        N = len(A[0])
        for i in range(N // 2):
            for j in range(i, N - i - 1):
                temp = A[i][j]
                A[i][j] = A[N - 1 - j][i]
                A[N - 1 - j][i] = A[N - 1 - i][N - 1 - j]
                A[N - 1 - i][N - 1 - j] = A[j][N - 1 - i]
                A[j][N - 1 - i] = temp

    ar = []
    for i in range(h):
            temp=input()
            t=[]
            for i in temp:
                t.append(i)
            ar.append(t)
            
            
    sh = min(ch, dh)
    eh = max(ch, dh)
    sw = min(cw, dw)
    ew = max(cw, dw)
    fin = []
    for i in range(sh - 1, eh):
        fin.append(ar[i][sw - 1:ew])

    t1=min((ch,cw),(dh,dw))
    t2=max((ch,cw),(dh,dw))
    if t1[1]>t2[1]:
        rotate90Clockwise(fin)
    n = eh - sh + 1
    m = ew - sw + 1
    inf = 9999999999999999999
    dp = [[inf for _ in range(m + 5)] for _ in range(n + 5)]
    dp[n - 1][m - 1] = 0


    def is_valid(i, j):
        if 0 <= i < n and 0 <= j < m and fin[i][j] == ".":
            return True
        return False

    moves = [(0, 1), (1, 0)]
    magic = [(0, 2), (2, 0), (1, 1), (1, 2), (2, 1), (2, 2)]
    for j in range(m - 1, -1, -1):
        for i in range(n - 1, -1, -1):
            if fin[i][j]=="#":
                dp[i][j]=inf
                continue
            for mov in moves:
                x, y = i + mov[0], j + mov[1]
                if is_valid(x, y):
                    dp[i][j] = min(dp[i][j], dp[x][y])
            for mag in magic:
                x, y = i + mag[0], j + mag[1]
                if is_valid(x, y):
                    dp[i][j] = min(dp[i][j], dp[x][y] + 1)
    if dp[0][0]==inf:
        print(-1)
    else:
        print(dp[0][0])

solve()

Submission status: Wrong Answer

Solution code:
def solve():
    h, w = map(int,input().strip().split(" "))

    ch, cw = map(int,input().strip().split(" "))
    dh, dw = map(int,input().strip().split(" "))

    def rotate90Clockwise(A):
        N = len(A[0])
        for i in range(N // 2):
            for j in range(i, N - i - 1):
                temp = A[i][j]
                A[i][j] = A[N - 1 - j][i]
                A[N - 1 - j][i] = A[N - 1 - i][N - 1 - j]
                A[N - 1 - i][N - 1 - j] = A[j][N - 1 - i]
                A[j][N - 1 - i] = temp

    ar = []
    for i in range(h):
            temp=input()
            t=[]
            for i in temp:
                t.append(i)
            ar.append(t)
            
            
    sh = min(ch, dh)
    eh = max(ch, dh)
    sw = min(cw, dw)
    ew = max(cw, dw)
    fin = []
    for i in range(sh - 1, eh):
        fin.append(ar[i][sw - 1:ew])

    t1=min((ch,cw),(dh,dw))
    t2=max((ch,cw),(dh,dw))
    if t1[1]>t2[1]:
        rotate90Clockwise(fin)
    n = eh - sh + 1
    m = ew - sw + 1
    inf = 9999999999999999999
    dp = [[inf for _ in range(m + 5)] for _ in range(n + 5)]
    dp[n - 1][m - 1] = 0


    def is_valid(i, j):
        if 0 <= i < n and 0 <= j < m and fin[i][j] == ".":
            return True
        return False

    moves = [(0, 1), (1, 0)]
    magic = [(0, 2), (2, 0), (1, 1), (1, 2), (2, 1), (2, 2)]
    for j in range(m - 1, -1, -1):
        for i in range(n - 1, -1, -1):
            for mov in moves:
                x, y = i + mov[0], j + mov[1]
                if is_valid(x, y):
                    dp[i][j] = min(dp[i][j], dp[x][y])
            for mag in magic:
                x, y = i + mag[0], j + mag[1]
                if is_valid(x, y):
                    dp[i][j] = min(dp[i][j], dp[x][y] + 1)
    if dp[0][0]==inf:
        print(-1)
    else:
        print(dp[0][0])

solve()

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
sy, sx = map(lambda x: int(x) - 1, input().split())
gy, gx = map(lambda x: int(x) - 1, input().split())
S = [[0 if s == '.' else -1 for s in input()] for _ in range(h)]

d = deque([(sx, sy)])
cur = 1
while True:
    visited = set()
    while d:
        y, x = d.pop()
        visited.add((y, x))
        S[y][x] = cur
        if (y, x) == (gy, gx):
            print(cur - 1)
            exit()
        for dyi, dxi in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            if 0<=y+dyi<h and 0<=x+dxi<w and S[y+dyi][x+dxi] == 0:
                d.append((y+dyi, x+dxi))

    for y, x in visited:
        for dyi in range(-2, 3):
            for dxi in range(-2, 3):
                if 0<=y+dyi<h and 0<=x+dxi<w and S[y+dyi][x+dxi] == 0:
                    d.append((y+dyi, x+dxi))
    if not d:
        print(-1)
        exit()
    cur += 1

Submission status: Wrong Answer

Solution code:
import itertools
import heapq


def main():
    INF = 10 ** 7
    H, W = list(map(int, input().split()))
    CH, CW = list(map(lambda x: int(x) - 1, input().split()))
    DH, DW = list(map(lambda x: int(x) - 1, input().split()))
    S = [input() for _ in range(H)]
    if S[DH][DW] == '#':
        print(-1)
        return
    # 使うワープの最小回数
    cnt = [[INF for _ in range(W)] for _ in range(H)]

    que = [(0, DH, DW)]
    while len(que) > 0:
        c, h, w = heapq.heappop(que)
        cnt[h][w] = c
        for dh, dw in itertools.product(range(-2, 3), repeat=2):
            nh, nw = h + dh, w + dw
            if dh == dw == 0 or not (0 <= nh < H) or \
                not (0 <= nw < W) or S[nh][nw] == '#':
                continue
            nc = c
            if [dh, dw] not in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
                nc += 1
            if cnt[nh][nw] > nc:
                heapq.heappush(que, (nc, nh, nw))

    if cnt[CH][CW] == INF:
        print(-1)
    else:
        print(cnt[CH][CW])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
import heapq


def main():
    INF = 10 ** 7
    H, W = list(map(int, input().split()))
    CH, CW = list(map(lambda x: int(x) - 1, input().split()))
    DH, DW = list(map(lambda x: int(x) - 1, input().split()))
    S = [input() for _ in range(H)]
    if S[DH][DW] == '#':
        print(-1)
        return
    # 使うワープの最小回数
    cnt = [[INF for _ in range(W)] for _ in range(H)]

    que = [(0, DH, DW)]
    while len(que) > 0:
        c, h, w = heapq.heappop(que)
        cnt[h][w] = c
        for dh, dw in itertools.product(range(-2, 3), repeat=2):
            nh, nw = h + dh, w + dw
            if dh == dw == 0 or not (0 <= nh < H) or \
                not (0 <= nw < W) or S[nh][nw] == '#':
                continue
            nc = c
            if [dh, dw] not in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
                nc += 1
            if cnt[nh][nw] > nc:
                heapq.heappush(que, (nc, nh, nw))

    def dfs(h=DH, w=DW, c=0):
        if c >= cnt[h][w]:
            return
        cnt[h][w] = c
        
        for dh, dw in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
            nh, nw = h + dh, w + dw
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                dfs(nh, nw, c)
        # それ以外はワープ
        for dh, dw in itertools.product(range(-2, 3), repeat=2):
            if [dh, dw] in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
                continue
            nh, nw = h + dh, w + dw
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                 dfs(nh, nw, c + 1)

    dfs()
    if cnt[CH][CW] == INF:
        print(-1)
    else:
        print(cnt[CH][CW])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq

h, w = list(map(int, input().split()))
c_h, c_w = list(map(int, input().split()))
d_h, d_w = list(map(int, input().split()))

s = [input() for _ in range(h)]

adj = [[{} for _ in range(w)] for _ in range(h)]

for x in range(h):
    for y in range(w):
        if s[x][y] == ".":
            for i in [-2, -1, 0, 1, 2]:
                for j in [-2, -1, 0, 1, 2]:
                    if 0 <= x+i < h and 0 <= y+j < w and s[x+i][y+j] == ".":
                        if (i == 0 and abs(j) == 1) or (j == 0 and abs(i) == 1):
                            adj[x][y][(x+i, y+j)] = 0
                        elif i != 0 and j != 0:
                            adj[x][y][(x+i, y+j)] = 1

d = []

for x in range(h):
    for y in range(w):
        if x == c_h - 1 and y == c_w - 1:
            d.append([0, x, y])
        else:
            d.append([1000000, x, y])

heapq.heapify(d)

dist = [[1000000] * w for _ in range(h)]
dist[c_h-1][c_w-1] = 0

while len(d) > 0:
    e, x, y = heapq.heappop(d)
    if x == d_h-1 and y == d_w-1:
        break
    for k, v in adj[x][y].items():
        i, j = k
        if s[i][j] == "." and dist[i][j] > dist[x][y] + adj[x][y][(i, j)]:
            dist[i][j] = dist[x][y] + adj[x][y][(i, j)]
            heapq.heappush(d, [dist[i][j], i, j])

if dist[d_h-1][d_w-1] == 1000000:
    print(-1)
else:
    print(dist[d_h-1][d_w-1])

#print(dist)

Submission status: Wrong Answer

Solution code:
import heapq

h, w = list(map(int, input().split()))
c_h, c_w = list(map(int, input().split()))
d_h, d_w = list(map(int, input().split()))

s = [input() for _ in range(h)]

adj = [[{} for _ in range(w)] for _ in range(h)]

for x in range(h):
    for y in range(w):
        if s[x][y] == ".":
            for i in [-2, -1, 0, 1, 2]:
                for j in [-2, -1, 0, 1, 2]:
                    if 0 <= x+i < h and 0 <= y+j < w and s[x+i][y+j] == ".":
                        if (i == 0 and abs(j) == 1) or (j == 0 and abs(i) == 1):
                            adj[x][y][(x+i, y+j)] = 0
                        elif i != 0 and j != 0:
                            adj[x][y][(x+i, y+j)] = 1

d = []

for x in range(h):
    for y in range(w):
        if x == c_h - 1 and y == c_w - 1:
            d.append([0, x, y])
        else:
            d.append([1000000, x, y])

heapq.heapify(d)

dist = [[1000000] * w for _ in range(h)]
dist[c_h-1][c_w-1] = 0

while len(d) > 0:
    e, x, y = heapq.heappop(d)
    #if x == d_h-1 and y == d_w-1:
        #break
    for k, v in adj[x][y].items():
        i, j = k
        if s[i][j] == "." and dist[i][j] > dist[x][y] + adj[x][y][(i, j)]:
            dist[i][j] = dist[x][y] + adj[x][y][(i, j)]
            heapq.heappush(d, [dist[i][j], i, j])

if dist[d_h-1][d_w-1] == 1000000:
    print(-1)
else:
    print(dist[d_h-1][d_w-1])

#print(dist)

Submission status: Wrong Answer

Solution code:
from collections import deque

def solve(h, w, ch, cw, dh, dw, s):
    G = [[0]*w for r in range(h)]
    label = 0
    for r in range(h):
        for c in range(w):
            if (s[r][c] == '.') and (G[r][c] == 0):
                label += 1
                que = deque([(r, c)])
                G[r][c] = label
                while que:
                    cr, cc = que.popleft()
                    for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                        nr, nc = cr+dr, cc+dc
                        if (0 <= nr < h) and (0 <= nc < w) and (s[nr][nc] == ".") and (G[nr][nc] == 0):
                            G[nr][nc] = label
                            que.append((nr, nc))

    sr, sc = ch-1, cw-1
    tr, tc = dh-1, dw-1

    neighbors = [(dr, dc) for dc in range(-2, 3) for dr in range(-2, 3) if abs(dr) + abs(dc) > 0]
    used = [[(s[r][c] == "#") for c in range(w)] for r in range(h)]
    que = deque([(sr, sc, 0)])
    label_dist_mapping = [-1] * (label + 1)
    used[sr][sc] = True
    label_dist_mapping[G[sr][sc]] = 0
    while que:
        cr, cc, n = que.popleft()
        if (cr == tr) and (cc == tc):
            return n
        for dr, dc in neighbors:
            nr, nc = cr+dr, cc+dc
            if (0 <= nr < h) and (0 <= nc < w) and not used[nr][nc]:
                used[nr][nc] = True
                if G[nr][nc] == G[cr][cc]: # 同一グループ
                    que.appendleft((nr, nc, n))
                elif label_dist_mapping[G[nr][nc]] > -1:
                    que.appendleft((nr, nc, label_dist_mapping[G[nr][nc]]))
                else:
                    label_dist_mapping[G[nr][nc]] = n + 1
                    que.append((nr, nc, n+1))
    return -1

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

Submission status: Wrong Answer

Solution code:
h, w = list(map(int, input().split()))
# 魔法使い
ch, cw = list(map(int, input().split()))
start = (ch - 1, cw - 1)
# マス
dh, dw = (list((map(int, input().split()))))
goal = (dh - 1, dw - 1)
stage = []
for _ in range(h):
    stage.append(list(str(input())))

stage[goal[0]][goal[1]] = 'G'

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


# return ワープ回数
def bfs():
    # キューには、今の場所とワープ回数を入れる
    que = [[start, 0]]

    while len(que) != 0:
        position, warp = que.pop(0)
        if stage[position[0]][position[1]] == 'G':
            return warp
        # すでに歩いていたら何もしない
        if stage[position[0]][position[1]] == 'W':
            continue

        # 歩いたという履歴を残す
        stage[position[0]][position[1]] = 'W'
        # print("==========")
        # print(position)
        # print(warp)

        can_walk = False
        for tmpH, tmpW in walk_pattern:
            nh = position[0] + tmpH
            nw = position[1] + tmpW
            # print(f'tmpH: {tmpH}, tmpW: {tmpW}')

            # 移動が可能かの判定
            if 0 <= nh < h and 0 <= nw < w and (stage[nh][nw] == '.' or stage[nh][nw] == 'G'):
                # print(f'nh: {nh}, nw: {nw}')
                que.append([(nh, nw), warp])
                can_walk = True


        # ワープする処理
        if not can_walk:
            for tmpH in range(-2, 3):
                for tmpW in range(-2, 3):
                    nh = position[0] + tmpH
                    nw = position[1] + tmpW

                    # 移動が可能かの判定
                    if 0 <= nh < h and 0 <= nw < w and (stage[nh][nw] == '.' or stage[nh][nw] == 'G'):
                        que.append([(nh, nw), warp + 1])

        # print(stage)
    return -1


result = bfs()
print(result)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[list(input()) for i in range(h)]

#幅優先で解く。
dx=[1,0,-1,0]
dy=[0,1,0,-1]
def bfs():
  maze=[[-1]*w for i in range(h)]
  maze[ch-1][cw-1]=0
  qu=deque([])
  qu.append((ch-1,cw-1))
  magic=0
  
  while qu:
    x,y=qu.popleft()
    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        nx=i+x
        ny=j+y
        if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]+1):
          qu.append((nx,ny))
          maze[ny][nx]=maze[y][x]+1
    for i in range(4):
      nx=dx[i]+x
      ny=dy[i]+y
      
      if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]):
        qu.appendleft((nx,ny))
        maze[ny][nx]=maze[y][x]
  return maze
    
maze = bfs()
print(maze[dh-1][dw-1])
#for i in maze:
#  print(*i)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import queue
    
def BFS(c,t,Num):
    q = queue.Queue()
    q.put(c)
    
    while not q.empty(): 
        n = q.get()
        if t[n[0] + 1][n[1]] != -1 and t[n[0] + 1][n[1]] == 9999:
            q.put([n[0] + 1, n[1]])
            t[n[0] + 1][n[1]] = Num
    
        if t[n[0]][n[1] + 1] != -1 and t[n[0]][n[1] + 1] == 9999:
            q.put([n[0], n[1] + 1])
            t[n[0]][n[1] + 1] = Num
        
        if t[n[0] - 1][n[1]] != -1 and t[n[0] - 1][n[1]] == 9999:
            q.put([n[0] - 1, n[1] ])
            t[n[0] - 1][ n[1] ] = Num

        if t[n[0]][n[1] - 1] != -1 and t[n[0]][n[1] - 1] == 9999:
            q.put([n[0],n[1] - 1])
            t[n[0]][n[1] - 1] = Num  


def SearchNum(t, Num):
    q = queue.Queue()    
    for i in range(H + 4):
        for j in range(W + 4):
            if t[i][j] == Num:
                q.put([i,j])            
    return q

def Warp(c,t,Num):
    for i in range(c[0]-2,c[0]+3):
        for j in range(c[1]-2,c[1]+3):
            if t[i][j] == 9999:
                t[i][j] = Num
    
H, W = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
S = []
for i in range(H):    
  S.append(list(input()))

C[0] -= 1
C[1] -= 1
D[0] -= 1
D[1] -= 1

T = np.full([H + 4,W + 4],-1)

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            T[i+2][j+2] = -1
        if S[i][j] == '.':
            T[i+2][j+2] = 9999
                
T[C[0] + 2][C[1] + 2] = 0
BFS([C[0] + 2,C[1] + 2],T,0)
count = 0
while True:      
        
    for i in range(H + 4):
        for j in range(W + 4):
            if T[i][j] == count:
                Warp([i,j],T,count + 1)
    count += 1 
        
    q_BFS = SearchNum(T,count)
    while not q_BFS.empty():
        n2 = q_BFS.get()
        BFS(n2,T,count)
        
    if count > 1500:
        break
    if T[D[0] + 2][D[1] + 2] != 9999:
        break
    

if T[D[0] + 2][D[1] + 2] != 9999:
    print(T[D[0] + 2][D[1] + 2])
else:
    print(-1)            

print(T)

Submission status: Wrong Answer

Solution code:
def clear_maze(sx, sy, gx, gy, maze):

    maze_xl = len(maze)
    maze_yl = len(maze[0])
    cost = [[-1 for i in range(maze_yl)] for j in range(maze_xl)]

#BFS
    queue = []
    queue.insert(0, (sx, sy))

    cost[sx][sy] = 0

    while len(queue):
        x, y = queue.pop()
        if x == gx and y == gy:
            break

        for i in range(-2, 3):
            for j in range(-2, 3):
                if (i, j) == (0, 0):
                    continue
                nx, ny = x + i, y + j
                if (0 <= nx < maze_xl and 0 <= ny < maze_yl and maze[nx][ny] != '#' and cost[nx][ny] == -1):
                    if (-1 <= i <= 1 and -1 <= j <= 1):
                        queue.insert(0, (nx, ny))
                        cost[nx][ny] = cost[x][y]
                    else:
                        queue.append((nx, ny))
                        cost[nx][ny] = cost[x][y] + 1

    return cost[gx][gy]

H, W = (int(a) for a in input().split())
Ch, Cw = (int(a) for a in input().split())
Dh, Dw = (int(a) for a in input().split())
S = [list(input()) for i in range(0, H)]

print(clear_maze(Ch - 1, Cw - 1, Dh - 1, Dw - 1, S))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# D

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
import queue

input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

maze = [None] * H

for ind_h in range(H):
    maze[ind_h] = input()[:-1]

steps = [[float('inf')] * W for _ in range(H)]
poped = [[False] * W for _ in range(H)]
queue = deque()


def bfs(Ch, Cw):
    queue.appendleft((Ch, Cw, 0))

    while len(queue) >0:
        r, c, score = queue.popleft()
        # 通常移動
        for s in [(-1, 0), (0, 1), (1, 0), (0,1)]:
            nr, nc = s
            nr = r + nr
            nc = c + nc
            if (nr < 0) | (nr > H - 1) | (nc < 0) | (nc > W - 1):
                pass
            else:
                if maze[nr][nc] == '.' and steps[nr][nc] > score:
                    queue.appendleft((nr, nc, score))
                    steps[nr][nc] = score

        # print(queue)
        # ジャンプ
        for s in [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
                  (-1, -2), (-1, -1), (-1, 1), (-1, 2),
                  (0, -2), (-2, 2),
                  (1, -2), (1, -1), (1, 1), (1, 2),
                  (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]:
            nr, nc = s
            nr = r + nr
            nc = c + nc
            if (nr < 0) | (nr > H - 1) | (nc < 0) | (nc > W - 1):
                pass
            else:
                if maze[nr][nc] == '.' and steps[nr][nc] > score:
                    queue.append((nr, nc, score+1))
                    steps[nr][nc] = score+1


bfs(Ch, Cw)

if steps[Dh][Dw]==float('inf'):
    print('-1')
else:
    print(steps[Dh][Dw])

Submission status: Wrong Answer

Solution code:
def warp(p,h,w):
    ls = []
    for i in range(-2,3):
        for j in range(-2,3):
            ls.append([p[0]+i,p[1]+j])
    ret = []
    for i in range(len(ls)):
        if -1<ls[i][0]<h and -1 < ls[i][1] < w:
            ret.append(ls[i])
    return ret

def main():
    h,w = map(int,input().split())
    ch,cw = map(int,input().split())
    dh,dw = map(int,input().split())
    s = []
    for i in range(h):
        s.append(input())
    dis = [[-1 for i in range(w)] for i in range(h)]
    que = [[ch-1,cw-1]]
    dis[ch-1][cw-1] = 0
    g = 0
    while len(que)>0:
        nxt = []
        while len(que)>0:
            q = que.pop(0)
            if s[q[0]][q[1]] == '#':
                continue
            if q == [dh-1,dw-1]:
                print(g)
                return
            nxt += warp(q,h,w)
            for [mv1,mv2] in [[0,1],[0,-1],[1,0],[-1,0]]:
                if -1 < q[0]+mv1 < h and -1 < q[1]+mv2 < w:
                    if dis[q[0]+mv1][q[1]+mv2] == -1:
                        if s[q[0]+mv1][q[1]+mv2] == '.':
                            dis[q[0]+mv1][q[1]+mv2] = g
                            que.append([q[0]+mv1, q[1]+mv2])
        g += 1
        for i in range(len(nxt)):
            x,y = nxt[i][0],nxt[i][1]
            if dis[x][y] == -1:
                if s[x][y] == '.':
                    dis[x][y] = g
                    que.append([x,y])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def warp(p,h,w):
    ls = [[p[0]-2,p[1]+i] for i in range(-1,2)]
    ls += [[p[0]+2,p[1]+i] for i in range(-1,2)]
    ls += [[p[0]+i,p[1]+2] for i in range(-1,2)]
    ls += [[p[0]+i,p[1]-2] for i in range(-1,2)]
    ls += [[p[0]+2,p[1]+2],[p[0]+2,p[1]-2],[p[0]-2,p[1]+2],[p[0]-2,p[1]-2]]
    ret = []
    for i in range(len(ls)):
        if -1<ls[i][0]<h:
            if -1<ls[i][1]<w:
                ret.append(ls[i])
    return ret

def main():
    h,w = map(int,input().split())
    ch,cw = map(int,input().split())
    dh,dw = map(int,input().split())
    s = []
    for i in range(h):
        s.append(input())
    dis = [[-1 for i in range(w)] for i in range(h)]
    que = [[ch-1,cw-1]]
    dis[ch-1][cw-1] = 0
    g = 0
    while len(que)>0:
        nxt = []
        while len(que)>0:
            q = que.pop(0)
            if s[q[0]][q[1]] == '#':
                continue
            nxt += warp(q,h,w)
            for [mv1,mv2] in [[0,1],[0,-1],[1,0],[-1,0]]:
                if -1 < q[0]+mv1 < h and -1 < q[1]+mv2 < w:
                    if dis[q[0]+mv1][q[1]+mv2] == -1:
                        if s[q[0]+mv1][q[1]+mv2] == '.':
                            dis[q[0]+mv1][q[1]+mv2] = g
                            que.append([q[0]+mv1, q[1]+mv2])
        g += 1
        for i in range(len(nxt)):
            x,y = nxt[i][0],nxt[i][1]
            if dis[x][y] == -1:
                if s[x][y] == '.':
                    dis[x][y] = g
                    que.append([x,y])
    print(dis[dh-1][dw-1])

if __name__ == "__main__":
    main()