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:
def solve(now_x, now_y):
    for next_y in range(-2, 3):
        for next_x in range(-2, 3):
            x, y = now_x + next_x, now_y + next_y
            if 0 <= x < w and 0 <= y < h:
                if c[y][x] != "#" and c[y][x] != "=" and c[y][x] != "!":
                    c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                    d2.append([x, y])


from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
c = [input() for _ in range(h)]
cw -= 1
ch -= 1
dw -= 1
dh -= 1
c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
d1 = deque([[cw, ch]])
d2 = deque([])


cnt = 0
for k in range(50):
    for j in range(100):
        for _ in range(len(d1)):
            now_x, now_y = d1.popleft()
            for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                x, y = now_x + next_x, now_y + next_y
                if 0 <= x < w and 0 <= y < h:
                    if x == dw and y == dh:
                        print(cnt)
                        exit()
                    if c[y][x] == "#":
                        solve(now_x, now_y)
                    if c[y][x] != "#" and c[y][x] != "=":
                        c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                        d1.append([x, y])
    else:
        cnt += 1
        if [dw, dh] in d2:
            print(cnt)
            exit()
        if not d2:
            print(-1)
            exit()
        d1 = d2.copy()
        d2.clear()

Submission status: Wrong Answer

Solution code:
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
d = [list(input()) for l in range(a[0])]
gcan = 0
minwarp = 100000

import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限
h,w = a[0],a[1]



def dfs(x,y,z):
    global minwarp
    global gcan
    if not(0 <= x < h) or not(0 <= y < w): # 壁に当たったり、探索範囲外になった場合はreturn
        return
    elif d[x][y] == "#":
        mx = x - 2
        if mx < 0:
            mx = 0
        my = y - 2
        if my < 0:
            my = 0
        px = x + 2
        if px >= h:
            px = h
        py = y + 2
        if py >= w:
            py = w
        pz = z
        for i in range(mx, px):
            for j in range(my, py):
                if d[i][j] == ".":
                    x = i
                    y = j
                    z = pz + 1
                    dfs(x,y,z)
        return
    if x == c[0] - 1 and y == c[1] - 1: # ゴールを見つけたら”Yes”を出力して終了
        if minwarp > z:
            minwarp = z
        gcan += 1
        return
        
    d[x][y] = "#" #探索済みを示すためのマーキング
    dfs(x+1,y,z)
    dfs(x-1,y,z)
    dfs(x,y+1,z)
    dfs(x,y-1,z)

sx, sy = b[0], b[1] # スタート位置
sz = 0
dfs(sx, sy, sz)
if gcan == 0:
    print("-1")
else:
    if minwarp == 1:
        print("0")
    print(str(minwarp - 2))

Submission status: Wrong Answer

Solution code:
def C_BFS2(R, C, sy, sx, gy, gx, c):
    """
    R:行数
    C:列数
    sy,sx:スタートの座標(sy行sx列)
    gy,gx:ゴールの座標(gy行gx列)
    c:迷路の形状(.:通路,#:壁)
    """
    INF = float('inf')
    sy -= 1
    sx -= 1
    gy -= 1
    gx -= 1

    def bfs2(maze, row, column, sy, sx, gy, gx):
        tmp = [[2,2],[2,1],[2,0],[2,-1],[2,-2],\
       [1,2],[1,-2],[0,2],[0,-2],\
       [-1,2],[-1,-2],\
       [-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2],[1,1],[1,-1],[-1,-1],[-1,1]]
        # 原点は(0,0)とする(問題の制約によっては原点をずらす必要がある)
        queue = []
        queue.insert(0, (sy, sx))
        dist = [[INF for _ in range(column)] for _ in range(row)]
        dist[sy][sx] = 0  # yが行数、xが列数を意味するときはこの順に書く
        # （追記）距離の最大値を持っておく
        dist_max = 0
        while len(queue):
            y, x = queue.pop()
            if x == gx and y == gy:
                 # ゴール座標と一致するなら
                break
            for i in range(20):
                nx = x + tmp[i][0]
                ny = y + tmp[i][1]
                if 0 <= nx and nx < column and 0 <= ny and ny < row \
                        and maze[ny][nx] != '#' and dist[ny][nx] == INF:
                    #(nx,ny)が迷路内であり、壁でなく、まだ距離が確定していないとき
                    queue.insert(0, (ny, nx))  # 次に探索する座標
                    dist[ny][nx] = dist[y][x] + 1
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + \
                    [0, 1, 0, -1][i]  # (x,y)の右、上、左、下
                if 0 <= nx and nx < column and 0 <= ny and ny < row \
                        and maze[ny][nx] != '#' and dist[ny][nx] == INF:
                    #(nx,ny)が迷路内であり、壁でなく、まだ距離が確定していないとき
                    queue.insert(0, (ny, nx))  # 次に探索する座標
                    if dist[ny][nx] > dist[y][x]:
                        dist[ny][nx] = dist[y][x]
        return dist[gy][gx]

    maze = [['' for _ in range(C)] for _ in range(R)]
    for i, tmp in enumerate(c):
        for j in range(C):
            maze[i][j] = tmp[j]

    ans = bfs2(maze, R, C, sy, sx, gy, gx)
    return ans

def C_BFS(R, C, sy, sx, gy, gx, c):
    """
    R:行数
    C:列数
    sy,sx:スタートの座標(sy行sx列)
    gy,gx:ゴールの座標(gy行gx列)
    c:迷路の形状(.:通路,#:壁)
    """
    INF = float('inf')
    sy -= 1
    sx -= 1
    gy -= 1
    gx -= 1

    def bfs(maze, row, column, sy, sx, gy, gx):
        # 原点は(0,0)とする(問題の制約によっては原点をずらす必要がある)
        queue = []
        queue.insert(0, (sy, sx))
        dist = [[INF for _ in range(column)] for _ in range(row)]
        dist[sy][sx] = 0  # yが行数、xが列数を意味するときはこの順に書く
        # （追記）距離の最大値を持っておく
        dist_max = 0
        while len(queue):
            y, x = queue.pop()
            if x == gx and y == gy:
                break
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + \
                    [0, 1, 0, -1][i]  # (x,y)の右、上、左、下
                if 0 <= nx and nx < column and 0 <= ny and ny < row \
                        and maze[ny][nx] != '#' and dist[ny][nx] == INF:
                    #(nx,ny)が迷路内であり、壁でなく、まだ距離が確定していないとき
                    queue.insert(0, (ny, nx))  # 次に探索する座標
                    dist[ny][nx] = dist[y][x]
                    # （追記）距離の最大値を更新する
                    if dist_max < dist[ny][nx]:
                        dist_max = dist[ny][nx]
        return dist[gy][gx]

    maze = [['' for _ in range(C)] for _ in range(R)]
    for i, tmp in enumerate(c):
        for j in range(C):
            maze[i][j] = tmp[j]

    ans = bfs(maze, R, C, sy, sx, gy, gx)
    return ans

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)]
import sys
# スタート地点は全て試す
dist_ans = 0
dist_tmp = C_BFS(H, W, Ch, Cw, Dh, Dw, S) # 今回、 gy, gx は不要
INF = float('inf')
if dist_tmp == 0:
    print(0)
    sys.exit()
else:
    dist_ans = 0
    dist_tmp = C_BFS2(H, W, Ch, Cw, Dh, Dw, S) # 今回、 gy, gx は不要
    INF = float('inf')
    if dist_tmp == INF:
        print(-1)
    else:
        print(dist_tmp)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

mX = [0, 1, 0, -1]
mY = [1, 0, -1, 0]
zX = [2, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, -1, -1, -1, -1, -2, -2, -2, -2, -2]
zY = [2, 1, 0, -1, 2, 2, 1, -1, -2, 2, -2, 2, -2, 1, -1, 2, 1, 0, -1, 2]


def bfs(u, S, M, H, W):  # u 開始点

    q = deque()
    q.append(u)
    while q:
        u = q.popleft()

        # 徒歩移動
        for i in range(4):
            nx = u[0] + mX[i]
            ny = u[1] + mY[i]
            if nx < 0 or H <= nx:
                continue
            if ny < 0 or W <= ny:
                continue
            if S[nx][ny] == "#":
                continue

            if M[nx][ny] == -1 or M[nx][ny] > M[u[0]][u[1]]:  # state を確認
                M[nx][ny] = M[u[0]][u[1]]  # 徒歩移動
                q.append([nx, ny])

        # 魔法移動
        for i in range(20):
            wx = u[0] + zX[i]
            wy = u[1] + zY[i]
            if wx < 0 or H <= wx:
                continue
            if wy < 0 or W <= wy:
                continue
            if S[wx][wy] == "#":
                continue
            if M[wx][wy] == -1 or M[wx][wy] > M[u[0]][u[1]]:  # state を確認
                M[wx][wy] = M[u[0]][u[1]] + 1
                q.append([wx, wy])


def main():

    H, W = map(int, sys.stdin.readline().rstrip().split())
    Ch, Cw = map(int, sys.stdin.readline().rstrip().split())
    Dh, Dw = map(int, sys.stdin.readline().rstrip().split())

    S = []
    for i in range(H):
        S.append(sys.stdin.readline().rstrip())

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

    if S[Ch - 1][Cw - 1] == "#":
        print(-1)
        return

    M[Ch - 1][Cw - 1] = 0
    bfs([Ch - 1, Cw - 1], S, M, H, W)

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


main()

Submission status: Wrong Answer

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    CH, CW = [int(x) - 1 for x in input().split()]
    DH, DW = [int(x) - 1 for x in input().split()]
    S = [input().strip() for _ in range(H)]

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

    visited = [[float("inf")] * W for _ in range(H)]

    q = collections.deque()
    visited[CH][CW] = 0
    q.append((CH, CW))
    while q:
        cx, cy = q.popleft()
        cc = visited[cx][cy]

        # 隣接
        kabe_cnt = 0
        for nx, ny in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            nnx = cx + nx
            nny = cy + ny
            if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                if S[nnx][nny] == ".":
                    if visited[nnx][nny] > cc:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc
                else:
                    kabe_cnt += 1

        # ワープ
        if kabe_cnt > 1:
            for nx, ny in warp:
                nnx = cx + nx
                nny = cy + ny
                if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                    if S[nnx][nny] == "." and visited[nnx][nny] > cc + 1:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc + 1

    if visited[DH][DW] == float("inf"):
        print(-1)
    else:
        print(visited[DH][DW])


if __name__ == '__main__':
    main()

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)]
revisited = [[False 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] = c
                    q.append([ny,nx])
                    dq.append([ny,nx])
                    revisited[ny][nx] = True
    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] = c+1
                                q.append([ny,nx])
                            elif visited[ny][nx] == c and revisited[ny][nx] == False:
                                revisited[ny][nx] = True
                                dq.append([ny,nx])
if visited[dh][dw] != inf:
    print(visited[dh][dw])
else:
    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())
field = []
for i in range(h):
  field.append(input())
seen = [[0 for i in range(w)] for i in range(h)]
jump = [[0 for i in range(w)] for i in range(h)]
jcnt = 0

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

queh = [ch-1]
quew = [cw-1]
seen[ch-1][cw-1] = 1
while queh:
  nowh = queh.pop(0)
  noww = quew.pop(0)
  
  flag = False
  for i in range(4):
    nexth = nowh+dx[i]
    nextw = noww+dy[i]
    if nexth < 0 or nexth >= h or nextw < 0 or nextw >= w:
      continue
    if field[nexth][nextw] == "#":
      continue
    if seen[nexth][nextw] != 0:
      continue
      
    queh.append(nexth)
    quew.append(nextw)
    seen[nexth][nextw] = 1
    jump[nexth][nextw] = jump[nowh][noww]
    
    flag = True
  
  if not flag:
    for i in range(nowh-2, nowh+3):
      for j in range(noww-2, noww+3):
        if i <= 0 or i >= h or j <= 0 or j >= w:
          continue
        if field[i][j] == "#":
          continue
        if seen[i][j] != 0:
          continue
          
        queh.append(i)
        quew.append(j)
        seen[i][j] = 1
        jump[i][j] = jcnt
    jcnt += 1

if seen[dh-1][dw-1] == 0:
  print(-1)
else:
  print(jump[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
start = list(map(int, input().split()))
goal = list(map(int, input().split()))
maze = [['#']*(W+2)] + [['#'] + list(input()) + ['#'] for _ in range(H)] + [['#']*(W+2)]
around = [[-1,0], [0,-1], [1,0], [0,1]]
more_around = [[i-2,j-2] for i in range(5) for j in range(5)]
t = 0

que = deque([start])
while len(que) > 0:
    nque = []
    while len(que) > 0:
        h, w = que.popleft()
        if [h, w] == goal:
            print(t)
            exit()
        elif maze[h][w] == '.':
            maze[h][w] = t
            DE = True
            for i, j in around:
                if maze[h+i][w+j] == '.':
                    que.append([h+i, w+j])
                    DE = False
            if DE:
                nque.append([h, w])
    
    que = deque(nque)
    nque = []
    t += 1
    while len(que) > 0:
        h, w = que.popleft()
        for i, j in more_around:
            if 0 <= h+i <= H+1 and 0 <= w+j <= W+1:
                if maze[h+i][w+j] == '.':
                    nque.append([h+i, w+j])
    que = deque(nque)

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 = ""
for h in range(H):
    S += input()

G = [{} for i in range(H*W)]
INF = 10**18
for h in range(H):
    for w in range(W):
        now = h*W + w
        for hh in range(-1, 2):
            t = (h+hh)*W + w
            for i in range(-1, 2):
                t_ = t + i
                if 0<= t_ < H*W  and ((h+hh)*W <= t_ <(h+hh+1) * W):
                    #print(now, t_)
                    if t_ != now and S[t_] == ".":
                        G[now][t_] = (1, 0)
                    elif t_ != now and S[t_] == "#":
                        G[now][t_] = (INF, 0)
        
        # Warp
        for hh in range(-2, 3):
            t = (h+hh)*W + w
            #print(now)
            for i in range(-2, 3):
                t_ = t + i
                if 0<= t_ < H*W  and ((h+hh)*W <= t_ <(h+hh+1)*W):
                    if t_ != now and t_ not in G[now].keys() and S[t_] == ".":
                        G[now][t_] = (1, 1)
                        
import queue
def solve(s, t):
    global G
    fixed = {}
    q = queue.PriorityQueue()
    q.put((0, s, 0)) # 0は累積コスト
    while q.empty() == False:
        w, x, warp = q.get()
        #print(fixed, w, x)
        if x == t: 
            return (w, warp)
        if x in fixed: 
            continue;
        fixed[x] = (w, warp)
        #print(G[x])
        for y in G[x]:
              if y not in fixed:
                    if G[x][y][1]:
                        add = 1
                    else:
                        add = 0
                    #print(add)
                    q.put((w + G[x][y][0], y, warp+add))
        #print(q.queue, "\n")
    return None

s = (Ch-1)*W + Cw-1
t = (Dh-1)*W + Dw-1
(a, ans) = solve(s, t)
if a >= INF:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right
from copy import deepcopy

def grid_wall(grid, h, w, wall='#'):
    G = [[wall]*(w+2) for _ in range(h+2)]
    for hi in range(h):
        G[hi+1][1:w+1] = grid[hi]
    return G

def solve():
    H, W = MI()
    ch, cw = MI()
    dh, dw = MI()
    G = LLS(H)
    GW = grid_wall(G, H, W)
    GW[dh][dw] = 'G'
    # print(GW)

    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    d = deque([(0, ch, cw)])

    used = deepcopy(GW)
    used[ch][cw] = '#'
    mp = 0
    WP = deque([d])

    # for _ in range(5):
    while d:
        # print(d)
        tmp2 = []
        while d:
            m, h, w = d.popleft()

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

                    if (dh, dw) in move:
                        # print(nh, nw)
                        if used[nh][nw] == '#':
                            continue
                        elif used[nh][nw] == 'G':
                            print(mp)
                            return
                        d.append((m, nh, nw))
                        used[nh][nw] = '#'
                        continue

                    if used[nh][nw] == '#':
                        continue
                    # elif used[nh][nw] == 'G':
                    #     print(mp)
                    #     return
                    tmp2.append((m+1, nh, nw))

        # print(tmp2)
        # mp = mp + 1
        for mm, nh, nw in tmp2:
            if used[nh][nw] == '#':
                continue
            elif used[nh][nw] == 'G':
                print(mm)
                return
            d.append((mm, nh, nw))
            used[nh][nw] = '#'

    print(-1)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W=map(int,input().split())
c=tuple(map(int,input().split()))
c=(c[0]-1,c[1]-1)
d=tuple(map(int,input().split()))
d=(d[0]-1,d[1]-1)
S=[]
for i in range(H):
  S.append(input())
  
INF=10**8

def bfs(s):
  seen = [[0 for i in range(W)] for j in range(H)]
  total = [[INF for i in range(W)] for j in range(H)]
  todo = deque([])
  now = s
  seen[now[0]][now[1]],total[now[0]][now[1]] = 1,0
  todo.append(now)
  while 1:
    if len(todo)==0:break
    now = todo.popleft()
    wall = [0,0]
    for d in [(1,0),(-1,0),(0,1),(0,-1)]:
      new = (now[0]+d[0], now[1]+d[1])
      if new[0]<0 or new[0]>=H:continue
      if new[1]<0 or new[1]>=W:continue
      if seen[new[0]][new[1]]==1:continue
      if S[new[0]][new[1]]=='#':
        wall[0] += abs(new[0])
        wall[1] += abs(new[1])
        continue
      seen[new[0]][new[1]] = 1
      todo.append(new)
      total[new[0]][new[1]] = min(total[now[0]][now[1]],total[new[0]][new[1]])
    if sum(wall)==0:continue
    for dx in range(-2,3):
      if wall[0]==0:continue
      for dy in range(-2,3):
        if wall[1]==0:continue
        new = (now[0]+dx,now[1]+dy)
        if new[0]<0 or new[0]>=H:continue
        if new[1]<0 or new[1]>=W:continue
        if seen[new[0]][new[1]]==1:continue
        if S[new[0]][new[1]]=='#':continue
        todo.append(new)
        total[new[0]][new[1]] = min(total[now[0]][now[1]]+1,total[new[0]][new[1]])
        
  return total

total = bfs(c)
ans = total[d[0]][d[1]]
if ans == INF:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

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

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

H,W = I()
Ch,Cw = I()
Dh,Dw = I()
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
li = deque([])
maze = [list(s()) for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
dist[Ch][Cw] = 1
que = deque([[Ch, Cw]])
while que:
    F = 0
    h, w = que.pop()
    for dh, dw in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = h + dh
        nw = w + dw
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if maze[nh][nw] == '#':
            F = 1
            continue
        if dist[nh][nw] == -1:
            if nh == Dh and nw == Dw:
                print(0)
                exit()
            dist[nh][nw] = 1
            que.appendleft([nh, nw])
    if F == 1:
        li.append((h,w,0))
que2 = copy(li)
lisy = [-2,-1,0,1,2]
lis = []
for i in range(5):
    for j in range(5):
      lis.append([lisy[i],lisy[j]])
while que2:
    h,w,n = que2.pop()
    if h == Dh and w == Dw:
        print(n)
        exit()
    for dh, dw in lis:
        nh = h + dh
        nw = w + dw
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        if maze[nh][nw] == '#':
            continue
        if abs(nh-h) > 2 or abs(nw-w) > 2:
            continue
        if dist[nh][nw] == -1:
            bfs(nh,nw,n+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 i in range(H)]
S=[list('#' for i in range(W+2)) for j in range(H+2)]
for i in range(1, H+1):
    for j in range(1, W+1):
        S[i][j]=s[i-1][j-1]
counter=0
h,w=Dh,Dw  
while h!=Ch or w!=Cw:
    flag1=False
    flag2=False
    #check to walk closer to C from current position
    if Ch<h and S[h-1][w]=='.':
        h-=1
        flag1=True
    elif Ch>h and S[h+1][w]=='.':
        h+=1
        flag1=True
    elif Cw<w and S[h][w-1]=='.':
        w-=1
        flag1=True
    elif Cw>w and S[h][w+1]=='.':
        w+=1
        flag1=True
    else:
        #use 2nd magic
        for i in range(h-2, h+3):
            for j in range(w-2, w+3):
                if i==Ch and j==Cw:
                    h=Ch
                    w=Cw
                    flag2=True
                    counter+=1
                    break
                elif i!=h and j!=w and abs(i-h)+abs(j-w)>=abs(i-Ch)+abs(j-Cw) and S[i][j]=='.':
                    #move to (i,j) with the magic
                    h=i
                    w=j
                    flag2=True
                    counter+=1
                    break
            if flag2:
                break
    if flag1 == False and flag2 == False:
        counter=-1
        break
print(counter)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
c1,c2 = map(int,input().split())
import sys
sys.setrecursionlimit(200000)
c1 -= 1
c2 -= 1
d1,d2 = map(int,input().split())
d1 -= 1
d2 -= 1
INF = 10**6
s = [list(input()) for _ in range(h)]
num = list([INF for i in range(w)] for _ in range(h))
bit = list( [0 for _ in range(w)] for _ in range(h))
num[c1][c2] = 0
bit[c1][c2] = 1


def dfs(j,k):
    tate = [0,1,0,-1]
    yoko = [1,0,-1,0]
    for i in range(4):
        if 0<= j+tate[i] and j+tate[i]<=h-1 and 0<=k +yoko[i] and k +yoko[i] <= w-1:
            if s[j+tate[i]][k+yoko[i]]== "." and bit[j+tate[i]][k+yoko[i]]==0:
                bit[j+tate[i]][k+yoko[i]] = 1
                num[j+tate[i]][k+yoko[i]]= min(num[j+tate[i]][k+yoko[i]], num[j][k])

                dfs(j+tate[i],k+yoko[i])


    for a in range(-2,3):
        for b in range(-2,3):
            if 0<= j+a and j+a<=h-1 and 0<=k+b and k+b <= w-1:
                if s[j+a][k+b]== "." and bit[j+a][k+b]==0:
                    bit[j+a][k+b]= 1
                    num[j+a][k+b]= min( num[j+a][k+b] , num[j][k]+1)
                    
                    dfs(j+a,k+b)

dfs(c1,c2)
if num[d1][d2]== 10**6:
    print(-1)
else:
    print(num[d1][d2])