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 math import trunc
import sys
import copy
from collections import deque
import collections
import itertools
stdin = sys.stdin
import math

mod = 10**9+7

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


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

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

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

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


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


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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from math import ceil
import numpy as np


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())


def nl(): return list(map(int, stdin.readline().split()))

# can_go_d = []
# dg = deque([(Dh, Dw)])

# while dg:
#     c_i, c_j = dg.pop()
#     for i in range(-2, 3):
#         for j in range(-2, 3):
#             if 0 <= c_i + i - 1 < h and 0 <= c_j + j - 1 < w:
#                 if not visited[c_i + i - 1][c_j + j - 1]:
#                     if S[c_i + i - 1][c_j + j - 1] == '.':
#                         can_go.append((c_i + i, c_j + j))
#                         pos.append((c_i + i, c_j + j))
#                         visited[c_i + i - 1][c_j + j - 1] = 1


def main():
    h, w = nm()
    Ch, Cw = nm()
    Dh, Dw = nm()
    S = np.array([list(ns()) for _ in range(h)])
    can_go = [(Ch, Cw)]
    pos = deque([(Ch, Cw)])
    visited = [[0] * w for _ in range(h)]
    visited[Ch - 1][Cw - 1] = 1

    while pos:
        c_i, c_j = pos.pop()
        for i, j in [(1, 0), (0, -1), (-1, 0), (0, 1)]:
            if 0 <= c_i + i - 1 < h and 0 <= c_j + j - 1 < w and not visited[c_i + i - 1][c_j + j - 1]:
                if S[c_i + i - 1][c_j + j - 1] == '.':
                    can_go.append((c_i + i, c_j + j))
                    pos.append((c_i + i, c_j + j))
                    visited[c_i + i - 1][c_j + j - 1] = 1

    if (Dh, Dw) in can_go:
        print(0)
        return

    dis = float('Inf')

    for i, j in can_go:
        if dis > (Dh - i) ** 2 + (Dw - j) ** 2:
            dis = (Dh - i) ** 2 + (Dw - j) ** 2
            most_close = (i, j)

    pt = Dh
    pb = Dh
    pl = Dw
    pr = Dw
    ans = 0
    for i in range(ceil(max(Dh - 1, h - Dh, Dw - 1, w - Dw) / 2)):
        pt = min(pt + 2, h)
        pb = max(pb - 2, 1)
        pr = min(pr + 2, w)
        pl = max(pl - 2, 1)
        ans += 1
        SS = S[pb - 1:pt, pl - 1:pr]
        for j, k in list(zip(*np.where(SS == '.'))):
            if most_close[0] == j + 1 and most_close[1] == k + 1:
                print(ans)
                return
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import queue
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
s = ["" for _ in range(h)]
p = [[-1 for _ in range(w)] for _ in range(h)]
for i in range(h):
  si = str(input())
  s[i] = si  
i = 0
flag = False
q = queue.Queue()
q.put((ch,cw))
p[ch][cw] = 0
l = [(ch,cw)]
la = l.append
while True:
  while not q.empty():
    j,k = q.get()
    if j == dh and k == dw:
      print(i)
      exit()
    p[j][k] = i
    for hi,wi in [(-1,0),(1,0),(0,-1),(0,1)]:
      if 0 <= j+hi and j+hi < h and 0 <= k+wi and k+wi < w:
        if s[j+hi][k+wi] == ".":
          if p[j+hi][k+wi] == -1:
            q.put((j+hi,k+wi))
            la((j+hi,k+wi))
  nl = []
  nla = nl.append
  for j,k in l:
    for hi,wi in [(-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)]:
      if  0 <= j+hi and j+hi < h and 0 <= k+wi and k+wi < w:
        if s[j+hi][k+wi] == ".":
          if p[j+hi][k+wi] == -1:
            q.put((j+hi,k+wi))
            nla((j+hi,k+wi))
            p[j+hi][k+wi] = i+1
  if q.empty():
    print(-1)
    exit()
  l = nl
  i += 1

Submission status: Wrong Answer

Solution code:
import collections
import sys
H, W = map(int, input().split())
C = tuple(int(x) - 1 for x in input().split())
D = tuple(int(x) - 1 for x in input().split())
S = [sys.stdin.readline() + "###" for _ in range(H)]
S.append("#" * (W + 3))
S.append("#" * (W + 3))
S.append("#" * (W + 3))

ans = 0
todo = collections.deque()
todo.append(C)
done = set()
while todo:
    pdone = []
    while todo:
        p = todo.popleft()
        done.add(p)
        pdone.append(p)
        h, w = p
        for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nh, nw = (h + dh, w + dw)
            if S[nh][nw] == "#":
                continue
            np = (nh, nw)
            if np == D:
                print(ans)
                sys.exit()
            if np in done:
                continue
            todo.append(np)

    ans += 1
    for h, w in pdone:
        for nh in range(h - 2, h + 2 + 1):
            for nw in range(w - 2, w + 2 + 1):
                if S[nh][nw] == "#":
                    continue
                np = (nh, nw)
                if np == D:
                    print(ans)
                    sys.exit()
                if np in done:
                    continue
                todo.append(np)
print(-1)

Submission status: Wrong Answer

Solution code:
import heapq
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = []
for i in range(H):
    S.append(input())

def Walk(X, Y):
    return [[X-1, Y], [X+1, Y], [X, Y-1], [X, Y+1]]

def Magic(X, Y):
    Ret = []
    for x in range(-2, 3):
        for y in range(-2, 3):
            Ret.append([X+x, Y+y])
    return Ret

D = [[float("inf")]*W for _ in range(H)]
D[Ch-1][Cw-1] = 0

Used = [[False]*W for _ in range(H)]

que = [(0, [Ch-1, Cw-1])]
while que:
    c, pos = heapq.heappop(que)
    if Used[pos[0]][pos[1]]:
        continue
    D[pos[0]][pos[1]] = c
    Used[pos[0]][pos[1]] = True
    if Dh - 1 == pos[0] and Dw -1 == pos[1]:
        break
    for pos_to in Magic(pos[0], pos[1]):
        if 0 <= pos_to[0] <= H - 1:
            if 0 <= pos_to[1] <= W - 1:
                if S[pos_to[0]][pos_to[1]] == ".":
                    Step = abs(pos_to[0]-pos[0]) + abs(pos_to[0]-pos[0])
                    if Step == 0:
                        continue
                    elif Step == 1:
                         heapq.heappush(que, (c, pos_to))
                    else:
                        heapq.heappush(que, (c+1, pos_to))
if D[Dh-1][Dw-1] == float("inf"):
    print(-1)
else:
    print(D[Dh-1][Dw-1])

Submission status: Wrong Answer

Solution code:
import collections

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

g = {}

def dump():
    print('map')
    for row in s:
        print(''.join(row))
    print('graph')
    print(g)
    print()

def check_range(x, y):
    return (0 <= x < h) and (0 <= y < w)

deq = collections.deque()
ident = 0
def reveal_cluster():
    global ident
    while len(deq):
        x, y, no = deq.popleft()
        if not check_range(x, y):
            continue
        if s[x][y] != '.':
            continue
        
        if no is None:
            ident += 1
            g[ident] = set()

        s[x][y] = str(ident)

        # 移動A
        for dx, dy in [(0, -1), (0, +1), (-1, 0), (+1, 0)]:
            nx, ny = x + dx, y + dy
            if check_range(nx, ny) and s[nx][ny] == '.':
                deq.append((nx, ny, ident))

deq.append((ch - 1, cw - 1, None))
reveal_cluster()

deq.append((dh - 1, dw - 1, None))
reveal_cluster()

for i in range(h):
    for j in range(w):
        deq.append((i, j, None))
        reveal_cluster()
#dump()

def check_cluster_connectivity():
    while len(deq):
        x, y, prev = deq.popleft()

        if not (0 <= x < h) or not (0 <= y < w):
            continue
        if s[x][y] == '#':
            continue

        curr = s[x][y]
        curr = int(curr)
        if prev is not None and curr != prev:
            # warpできる
            k = int(s[x][y])
            g[prev].add(k)

        _prev = int(s[x][y])

        s[x][y] = '#'

        # 移動B
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if check_range(nx, ny) and s[nx][ny] != '#' and s[nx][ny] != s[x][y]:
                    v = (nx, ny, _prev)
                    deq.append(v)

for i in range(h):
    for j in range(w):
        v = (i, j, None)
        deq.append(v)
        check_cluster_connectivity()

dist = {k:None for k in g}
def bfs(pos, d):
    if dist[pos] is not None:
        return
    dist[pos] = d
    for e in g[pos]:
        bfs(e, d + 1)

if len(g) == 1:
    # スタート = ゴール
    print(0)
elif len(g[1]) == 0:
    # 経路なし
    print(-1)
else:
    # 経路あり ⇒ bfs
    bfs(1, 0)
    print(dist[2])

Submission status: Wrong Answer

Solution code:
def main2():
    H, W = map(int, input().split())
    Ch, Cw = map(int ,input().split())
    Dh, Dw = map(int, input().split())

    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    maze = list()
    arrived = [[0 for i in range(W)] for j in range(H)]
    arrived[Ch][Cw] = 1

    for i in range(H):
        maze.append(list(input()))

    ans = 0
    for i in range(10**6):
        if Ch == Dh and Cw == Dw:
            print(ans)
            exit()

        update_flag = 0
        if Cw + 1 < W and maze[Ch][Cw + 1] == "." and arrived[Ch][Cw + 1] == 0:
            Cw += 1
            arrived[Ch][Cw] = 1
            update_flag = 1
        elif Ch + 1 < H and maze[Ch + 1][Cw] == "." and arrived[Ch + 1][Cw] == 0:
            Ch += 1
            arrived[Ch][Cw] = 1
            update_flag = 1
        elif Cw - 1 > 0 and maze[Ch][Cw - 1] == "." and arrived[Ch][Cw - 1] == 0:
            Cw -= 1
            arrived[Ch][Cw] = 1
            update_flag = 1
        elif Ch - 1 > 0 and maze[Ch - 1][Cw] == "." and arrived[Ch - 1][Cw] == 0:
            Ch -= 1
            arrived[Ch][Cw] = 1
            update_flag = 1

        if update_flag == 0:
            find = 0
            for i in range(2, -3, -1):
                for j in range(2, -3, -1):
                    x = Cw + j
                    y = Ch + i

                    if 0 <= y < H and 0 <= x < W:
                        if y == Dh and x == Dw:
                            Ch = Dh
                            Cw = Dw
                            find = 1
                            ans += 1
                            break

                        elif maze[y][x] == "." and arrived[y][x] == 0:
                            Ch = y
                            Cw = x
                            find = 1
                            ans += 1
                            break

                if find == 1:
                    break

            if find == 0:
                print(-1)
                exit()
    
    if Ch != Dh and Cw != Dw:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main2()

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 

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

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

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 == 0:
        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]]
        # 原点は(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(16):
                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

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)]
visited = [[-1] * W for j in range(H)]

d = deque([[Ch - 1, Cw - 1]])
wq = deque([[Ch - 1, Cw - 1]])

visited[Ch - 1][Cw - 1] = 0
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
warp_move = [[-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]
             ]
warp = 0

while len(d) > 0 or len(wq) > 0:
    while len(d) > 0:
        y, x = d.popleft()
        for i, j in move:
            nexty, nextx = y + i, x + j
            if nexty == Dh - 1 and nextx == Dw - 1:
                print(warp)
                exit()
            if nextx >= 0 and nextx < W and nexty >= 0 and nexty < H:
                if S[nexty][nextx] == "." and visited[nexty][nextx] == -1:
                    visited[nexty][nextx] = warp
                    d.append([nexty, nextx])
                    wq.append([nexty, nextx])

    warp += 1
    while len(wq) > 0:
        y, x = wq.popleft()
        for i, j in warp_move:
            warp_y, warp_x = y + i, x + j
            if warp_y == Dh - 1 and warp_x == Dw - 1:
                print(warp)
                exit()
            if warp_x >= 0 and warp_x < W and warp_y >= 0 and warp_y < H:
                if S[warp_y][warp_x] == "." and visited[warp_y][warp_x] == -1:
                    visited[warp_y][warp_x] = warp
                    d.append([warp_y, warp_x])
print(-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque

h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
ch, cw = ch-1, cw-1
dh, dw = dh-1, dw-1

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

num = np.inf*np.ones((h,w))


num[ch,cw] = 0
q = deque([[ch,cw]])
walk = [[-1,0],[0,-1],[0,1],[1,0]]
warp = [[-2,i] for i in range(-2,3)] + [[i,-2] for i in range(-1,2)]  + [[i,2] for i in range(-1,2)] + [[2,i] for i in range(-2,3)]
near_wall = deque([])

while len(q)>0 or len(near_wall)>0:
    while len(q)>0:
        now = q.popleft()
        for x in walk:
            next_point = [now[0]+x[0], now[1]+x[1]]
            # print(now,next_point)
            if not (0 <= next_point[0] < h and 0 <= next_point[1] < w ): # 外に出てた場合
                continue
            next_num = num[next_point[0],next_point[1]]
            now_num = num[now[0],now[1]]
            if s[next_point[0]][next_point[1]] =='#':
                near_wall.append(now)
            elif (np.isinf(next_num) or next_num > now_num): # まだやってない場合
                num[next_point[0],next_point[1]] = now_num
                if next_point[0]==dh and next_point[1]==dw:
                    q,near_wall = [],[]
                    break
                q.append(next_point)
    while len(near_wall)>0:
        now = near_wall.popleft()
        for x in warp:
            next_point = [now[0]+x[0], now[1]+x[1]]
            if not (0 <= next_point[0] < h and 0 <= next_point[1] < w ): # 外に出てた場合
                continue
            next_num = num[next_point[0],next_point[1]]
            now_num = num[now[0],now[1]]
            if s[next_point[0]][next_point[1]] =='.'  and \
                (np.isinf(next_num) or\
                next_num > now_num + 1): # まだやってない場合
                num[next_point[0],next_point[1]] = now_num + 1
                q.append(next_point)
if np.isinf(num[dh,dw]):
    print(-1)
else:
    print(int(num[dh,dw]))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from time import time


def main():
    start = time()

    def f(hi, wi):
        return hi * w + wi

    h, w = map(int, input().split())
    sh, sw = map(int, input().split())
    gh, gw = map(int, input().split())
    s = [input() for _ in range(h)]
    INF = 10 ** 9

    sh -= 1
    sw -= 1
    gh -= 1
    gw -= 1

    sh, sw, gh, gw = gh, gw, sh, sw

    hp = [[0, f(sh, sw)]]
    dist = [[INF] * w for _ in range(h)]
    dist[sh][sw] = 0

    while hp:
        if time() - start >= 1.9:
            break
        d, i = heappop(hp)
        hi, wi = divmod(i, w)

        if d != dist[hi][wi]:
            continue

        for dh in range(-2, 3):
            for dw in range(-2, 3):
                nh = hi + dh
                nw = wi + dw
                if 0 <= nh <= h - 1 and 0 <= nw <= w - 1 and s[nh][nw] == ".":
                    if abs(dh) + abs(dw) == 1:
                        cost = 0
                    else:
                        cost = 1

                    dist_now = d + cost
                    if dist_now < dist[nh][nw]:
                        dist[nh][nw] = dist_now
                        heappush(hp, [dist_now, f(nh, nw)])

    ans = dist[gh][gw]
    if ans == INF:
        ans = -1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


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

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

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs():
  d = [[float('inf')]*w for i in range(h)]
  
  dx = [1, 0, -1, 0]
  dy = [0, 1, 0, -1]
  ex = [2, 1, 0, -1, -2, 2, -2, 2, -2, 2, -2, 2, 1, 0, -1, -2, 1, 1, -1, -1]
  ey = [2, 2, 2, 2, 2, 1, 1, 0, 0, -1, -1, -2, -2, -2, -2, -2, 1, -1, 1, -1]
  
  que = deque([])
  que.append((ch, cw))
  d[ch][cw] = 0
  
  while que:
    p = que.popleft()
    if p[0]==dh and p[1]==dw:
      break
    for i in range(4):
      nx = p[0] + dx[i]
      ny = p[1] + dy[i]
      if 0<=nx<h and 0<=ny<w and maze[nx][ny]!='#' and d[nx][ny]==float('inf'):
        que.append((nx, ny))
        d[nx][ny] = d[p[0]][p[1]]
      elif 0<=nx<h and 0<=ny<w and maze[nx][ny]=='#':
        for j in range(19):
          nx = p[0] + ex[j]
          ny = p[1] + ey[j]
          if 0<=nx<h and 0<=ny<w and maze[nx][ny]!='#' and d[nx][ny]==float('inf'):
            que.append((nx, ny)) 
            d[nx][ny] = min(d[nx][ny], d[p[0]][p[1]]+1)
            
              
  return d[dh][dw]
        
  
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
maze = [list(input()) for i in range(h)]

if bfs()==float('inf'):
  print(-1)
else:
  print(bfs())

Submission status: Wrong Answer

Solution code:
from collections import deque
from sys import stdin
h,w =map(int, stdin.readline().split())
ch,cw = map(int, stdin.readline().split())
dh,dw =map(int, stdin.readline().split())

g = []
for i in range(h):
  s = list(input())
  g.append(s)
inf = float("inf")
dist = [[inf]*w for i in range(h)]
seen = [[False]*w for i in range(h)]
queue = deque()
start = [ch-1,cw-1,0]
queue.append(start)
def dfs(y,x,wapu):
  if seen[y][x]:
    return
  dist[y][x] = min(wapu,dist[y][x])
  for new_y, new_x in ([y+1, x], [y-1, x], [y, x+1], [y, x-1]):
        if 0 <= new_y <= h-1 and 0 <= new_x <= w-1:
            if g[new_y][new_x] == '#':
                continue           
            elif wapu < dist[new_y][new_x]:
                dist[new_y][new_x] = wapu
                queue.append([new_y, new_x,wapu])
                dfs(new_y,new_x,wapu)
  
while queue:
    y, x,wapu = queue.popleft()
    if dist[y][x]<wapu:
      continue
    elif wapu < dist[y][x]:
      dfs(y,x,wapu)
    for new_y, new_x in ([y+1, x+1], [y+1, x-1], [y-1, x+1], [y-1, x-1], [y+2, x-1], [y-2, x-1], [y-2, x], [y+2, x], [y+2, x+1], [y-2, x+1], [y-1, x+2], [y, x+2], [y+1, x+2], [y+2, x+2], [y-2, x-2], [y-2, x+2], [y+2, x-2], [y-1, x-2], [y, x-2], [y+1, x-2]):
      if 0 <= new_y <= h-1 and 0 <= new_x <= w-1:
            if g[new_y][new_x] == '#' or seen[new_y][new_x]:
                continue               
            else:
              new_wapu = wapu+1
            if new_wapu < dist[new_y][new_x]:
              dist[new_y][new_x] = new_wapu
              queue.append([new_y, new_x,new_wapu])

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