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:
# coding: utf-8
# Your code here!
 
import sys
from collections import deque 
INF = float('INF') #INFの宣言
#入力部
H, W = map(int, input().split())
Ch, Cw = map(lambda c: int(c) +1 , input().split())
Dh, Dw = map(lambda d: int(d) +1, input().split())
mymap = []
mymap += [['#' for w in range(W+4)]]
mymap += [['#' for w in range(W+4)]]
for h in range(H):
    mymap += [ ['#', '#'] + list(input()) +['#', '#']]
mymap += [['#' for w in range(W+4)]]
mymap += [['#' for w in range(W+4)]]
#for m in mymap:
#    print(m)
#各地点までの最短距離の配列,INFで初期化
d = [ [INF for w in range(W+4)] for h in range(H+4) ]
#obstacleの処理
for h in range(H):
    for w in range(W):
        if mymap[h][w] == '#':
            d[h][w] = -1
#移動4方向のベクトル
dx, dy  = [1, 0, -1, 0], [0, 1, 0, -1]  
 
def bfs(h, w):
    warp_cnt = 0
    mydeque = deque()
    mydeque.append([h, w]) #スタート地点をdequeに入れる
    d[h][w] = warp_cnt     #スタート地点のwarp回数をresにする
    #warp先の座標を格納するリスト
    warp_deque = deque()
    # dequeが空になるまでループ
    while mydeque:
        while mydeque:
            #dequeの先頭を取り出す
            y, x = mydeque.popleft()
            warp_deque.append((y,x))
            for i in range(4):
                #移動後の点を(nx, ny) とする
                nx, ny = x + dx[i], y + dy[i]
                #移動可能かの判定とすでに訪れたことがあるかの判定(d[nx][ny] !=  INF なら訪れたことがある)
                if 0 <= nx and nx < W and 0 <= ny and ny < H and d[ny][nx] >  d[y][x]:
                    #print(ny, nx, d[ny][nx], mymap[ny][nx])
                    if  mymap[ny][nx] != '#' : 
                    #移動できるならdequeに入れ、その点の距離をwarp_cntで確定する
                        mydeque.appendleft([ny, nx])
                        if d[ny][nx] > warp_cnt:
                            d[ny][nx] = warp_cnt
                            warp_deque.append((ny, nx))
        #Goalが探索済みであれば，探索をやめる
        if d[Dh][Dw] != INF:
            break
        #warpの処理
        warp_cnt += 1
        while warp_deque:
            h, w = warp_deque.popleft()
            for i in range(-2, 3):
                for j in range(-2, 3):
                    nny, nnx = h + i, w + j
                    if d[nny][nnx] > warp_cnt:
                        d[nny][nnx] = warp_cnt
                        mydeque.append([i,j])
    return
 
 
bfs(Ch,Cw)

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
dxw = [-2, -1, 0, 1, 2, -2, -1, 0, 1, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2, -2, -1, 0, 1, 2]
dyw = [-2, -2, -2, -2, -2, -1, -1, -1, -1, -1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]

q = deque()
q.append((ch, cw, 0))
ans = [[10 ** 9] * w for _ in range(h)]
while len(q) > 0:
    x, y, c = q.popleft()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if (
            nx >= 0
            and nx < h
            and ny >= 0
            and ny < w
            and c < ans[nx][ny]
            and s[nx][ny] == "."
        ):
            q.appendleft((nx, ny, c))
            ans[nx][ny] = c
    for i in range(24):
        nx, ny = x + dxw[i], y + dyw[i]
        if (
            nx >= 0
            and nx < h
            and ny >= 0
            and ny < w
            and c + 1 < ans[nx][ny]
            and s[nx][ny] == "."
        ):
            q.append((nx, ny, c + 1))
            ans[nx][ny] = c + 1
v = ans[dh][dw]
print(-1 if v == 10 ** 4 else v)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
dxw = [-2, -1, 0, 1, 2, -2, -1, 0, 1, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2, -2, -1, 0, 1, 2]
dyw = [-2, -2, -2, -2, -2, -1, -1, -1, -1, -1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]

q = deque()
q.append((ch, cw, 0))
ans = [[10 ** 4] * w for _ in range(h)]
while len(q) > 0:
    x, y, c = q.popleft()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if (
            nx >= 0
            and nx < h
            and ny >= 0
            and ny < w
            and c < ans[nx][ny]
            and s[nx][ny] == "."
        ):
            q.appendleft((nx, ny, c))
            ans[nx][ny] = c
    for i in range(24):
        nx, ny = x + dxw[i], y + dyw[i]
        if (
            nx >= 0
            and nx < h
            and ny >= 0
            and ny < w
            and c + 1 < ans[nx][ny]
            and s[nx][ny] == "."
        ):
            q.append((nx, ny, c + 1))
            ans[nx][ny] = c + 1
v = ans[dh][dw]
print(-1 if v == 10 ** 4 else v)

Submission status: Wrong Answer

Solution code:
# import math, queue

# h, w = map(int, input().split(" "))
# sY, sX = map(int, input().split(" "))
# gY, gX = map(int, input().split(" "))
# smap = [list(input()) for _ in range(h)]
# visited = [[False for _ in range(w)] for _ in range(h)]

# for y in range(h):
#     for x in range(w):
#         if smap[y][x] == ".":
#             smap[y][x] = 100000000000

# sY, sX = sY - 1, sX - 1
# gY, gX = gY - 1, gX - 1

# q = queue.deque()
# q.append([sY, sX])
# smap[sY][sX] = 0

# mv0 = [[-1, 0], [1, 0], [0, -1], [0, 1]]
# mv1 = [[-1, -1], [1, -1], [-1, 1], [1, 1], [-2, -2], [-2, -1],
#        [-2, 0], [-2, 1], [-2, 2], [-1, 2], [0, 2], [1, 2], [2, 2], [2, 1],
#        [2, 0], [2, 1], [2, -2], [1, -2], [0, -2], [-1, -2]]

# cnt = 0
# while len(q) != 0:
#     cnt += 1
#     crntY, crntX = q.popleft()
#     if visited[crntY][crntX]:
#         continue
#     for i, [stepY, stepX] in enumerate(mv0 + mv1):
#         nextY = crntY + stepY
#         nextX = crntX + stepX
#         if nextY < 0 or h <= nextY or nextX < 0 or w <= nextX:
#             continue
#         if visited[nextY][nextX] or smap[nextY][nextX] == "#":
#             continue
#         cost = smap[crntY][crntX]
#         if i >= 4:
#             cost += 1
#             q.append([nextY, nextX])
#         else:
#             q.appendleft([nextY, nextX])
#         smap[nextY][nextX] = min(cost, smap[nextY][nextX])
#     visited[crntY][crntX] = True

# if smap[gY][gX] == 100000000000:
#     print(-1)
# else:
#     print(smap[gY][gX])

import math, queue

h, w = map(int, input().split(" "))
sY, sX = map(int, input().split(" "))
gY, gX = map(int, input().split(" "))
smap = [list(input()) for _ in range(h)]
visited = [[False for _ in range(w)] for _ in range(h)]

for y in range(h):
    for x in range(w):
        if smap[y][x] == ".":
            smap[y][x] = 100000000000

sY, sX = sY - 1, sX - 1
gY, gX = gY - 1, gX - 1

q = queue.Queue()
q.put([sY, sX])
smap[sY][sX] = 0

mv0 = [[-1, 0], [1, 0], [0, -1], [0, 1]]
mv1 = [[-1, -1], [1, -1], [-1, 1], [1, 1], [-2, -2], [-2, -1],
       [-2, 0], [-2, 1], [-2, 2], [-1, 2], [0, 2], [1, 2], [2, 2], [2, 1],
       [2, 0], [2, 1], [2, -2], [1, -2], [0, -2], [-1, -2]]

while q.qsize() != 0:
    crntY, crntX = q.get()
    if visited[crntY][crntX]:
        continue
    for i, [stepY, stepX] in enumerate(mv0 + mv1):
        nextY = crntY + stepY
        nextX = crntX + stepX
        if nextY < 0 or h <= nextY or nextX < 0 or w <= nextX:
            continue
        if visited[nextY][nextX] or smap[nextY][nextX] == "#":
            continue
        cost = smap[crntY][crntX]
        if i >= 4:
            cost += 1
        smap[nextY][nextX] = min(cost, smap[nextY][nextX])
        q.put([nextY, nextX])
    visited[crntY][crntX] = True

if smap[gY][gX] == 100000000000:
    print(-1)
else:
    print(smap[gY][gX])

Submission status: Wrong Answer

Solution code:
import math, queue

h, w = map(int, input().split(" "))
sY, sX = map(int, input().split(" "))
gY, gX = map(int, input().split(" "))
smap = [list(input()) for _ in range(h)]
visited = [[False for _ in range(w)] for _ in range(h)]

for y in range(h):
    for x in range(w):
        if smap[y][x] == ".":
            smap[y][x] = 100000000000

sY, sX = sY - 1, sX - 1
gY, gX = gY - 1, gX - 1

q = queue.deque()
q.append([sY, sX])
smap[sY][sX] = 0

mv0 = [[-1, 0], [1, 0], [0, -1], [0, 1]]
mv1 = [[-1, -1], [1, -1], [-1, 1], [1, 1], [-2, -2], [-2, -1],
       [-2, 0], [-2, 1], [-2, 2], [-1, 2], [0, 2], [1, 2], [2, 2], [2, 1],
       [2, 0], [2, 1], [2, -2], [1, -2], [0, -2], [-1, -2]]

cnt = 0
while len(q) != 0:
    cnt += 1
    crntY, crntX = q.popleft()
    if visited[crntY][crntX]:
        continue
    for i, [stepY, stepX] in enumerate(mv0 + mv1):
        nextY = crntY + stepY
        nextX = crntX + stepX
        if nextY < 0 or h <= nextY or nextX < 0 or w <= nextX:
            continue
        if visited[nextY][nextX] or smap[nextY][nextX] == "#":
            continue
        cost = smap[crntY][crntX]
        if i >= 4:
            cost += 1
            q.append([nextY, nextX])
        else:
            q.appendleft([nextY, nextX])
        smap[nextY][nextX] = min(cost, smap[nextY][nextX])
    visited[crntY][crntX] = True

if smap[gY][gX] == 100000000000:
    print(-1)
else:
    print(smap[gY][gX])

Submission status: Wrong Answer

Solution code:
import math
import queue

h, w = map(int, input().split(" "))
sY, sX = map(int, input().split(" "))
gY, gX = map(int, input().split(" "))
smap = [list(input()) for _ in range(h)]
visited = [[False for _ in range(w)] for _ in range(h)]

for y in range(h):
    for x in range(w):
        if smap[y][x] == ".":
            smap[y][x] = 100000000000

sY, sX = sY - 1, sX - 1
gY, gX = gY - 1, gX - 1

q = queue.deque()
q.append([sY, sX])
smap[sY][sX] = 0
visited[sY][sX] = True

mv0 = [[-1, 0], [1, 0], [0, -1], [0, 1]]
mv1 = [[-1, -1], [1, -1], [-1, 1], [1, 1], [-2, -2], [-2, -1],
       [-2, 0], [-2, 1], [-2, 2], [-1, 2], [0, 2], [1, 2], [2, 2], [2, 1],
       [2, 0], [2, 1], [2, -2], [1, -2], [0, -2], [-1, -2]]

cnt = 0
while len(q) != 0:
    cnt += 1
    crntY, crntX = q.pop()
    for i, [stepY, stepX] in enumerate(mv0 + mv1):
        nextY = crntY + stepY
        nextX = crntX + stepX
        if nextY < 0 or h <= nextY or nextX < 0 or w <= nextX:
            continue
        if visited[nextY][nextX] or smap[nextY][nextX] == "#":
            continue
        cost = smap[crntY][crntX]
        if i >= 4:
            cost += 1
        smap[nextY][nextX] = min(cost, smap[nextY][nextX])
        if i >= 4:
            q.append([nextY, nextX])
        else:
            q.appendleft([nextY, nextX])
    visited[crntY][crntX] = True

if smap[gY][gX] == 100000000000:
    print(-1)
else:
    print(smap[gY][gX])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
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 i in range(H):
    S.append(list(input()))

def visit(S, h, w, d, H, W):
    stack = [(h, w)]
    visited = []
    while stack:
        h, w = stack.pop()
        S[h][w] = d 
        visited.append((h, w))
        for x, y in [(h-1, w), (h+1,w), (h, w-1), (h, w+1)]:
            if 0 <= x < len(S) and 0 <= y < len(S[x]):
                if S[x][y] == '#':
                    continue
                if S[x][y] == '.':
                    stack.append((x, y))
                    continue
                elif S[x][y] > d:
                    stack.append((x, y))
    for h, w in visited:
        for dh in range(-2, 2+1):
            if not 0 <= h+dh < H:
                continue
            for dw in range(-2,2+1):
                if not 0 <= w+dw < W:
                    continue

                hop = S[h+dh][w+dw]
                if hop  == "#":
                    continue
                if hop != ".":
                    continue
                visit(S, h+dh, w+dw, d+1, H, W)


def solve(H, W, Ch, Cw, Dh, Dw, S):
    visited = visit(S, Ch, Cw, 0, H, W)
    if S[Dh][Dw] != ".":
        return S[Dh][Dw]
    else:
        return -1

print(solve(H, W, Ch, Cw, Dh, Dw, S))
#for h in range(H): print("".join(map(str, S[h])))
"""
import sys

if sys.argv[0] != "/.Main.py" and False:
    import random

    for i in range(1):
        H = random.randint(2, 20)
        W = random.randint(2, 20)
        S = []
        for h in range(H):
            S.append([random.choice(".#") for _ in range(W)])

        Ch, Cw = random.randrange(0, H), random.randrange(0, W)
        Dh, Dw = random.randrange(0, H), random.randrange(0, W)
        S[Ch][Cw] = 'C'
        S[Dh][Dw] = '.'
        print(H, W, (Ch, Cw), (Dh, Dw), solve(H, W, Ch, Cw, Dh, Dw, S))
        for i in range(H):
            #print("".join(map(str, S[h])))
            print(h, S[h])
"""

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
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 i in range(H):
    S.append(list(input()))

def visit(S, h, w, d, H, W):
    stack = [(h, w)]
    visited = []
    while stack:
        h, w = stack.pop()
        S[h][w] = d 
        visited.append((h, w))
        for x, y in [(h-1, w), (h+1,w), (h, w-1), (h, w+1)]:
            if 0 <= x < len(S) and 0 <= y < len(S[x]):
                if S[x][y] == '#':
                    continue
                if S[x][y] == '.':
                    stack.append((x, y))
                    continue
                elif S[x][y] >= d:
                    stack.append((x, y))
    for x, y in visited:
        for dh in range(-2, 2+1):
            if not 0 <= h+dh < H:
                continue
            for dw in range(-2,2+1):
                if not 0 <= w+dw < W:
                    continue

                hop = S[h+dh][w+dw]
                if hop  == "#":
                    continue
                if hop != ".":
                    continue
                visit(S, h+dh, w+dw, d+1, H, W)


def solve(H, W, Ch, Cw, Dh, Dw, S):
    visited = visit(S, Ch, Cw, 0, H, W)
    if S[Dh][Dw] != ".":
        return S[Dh][Dw]
    else:
        return -1

print(solve(H, W, Ch, Cw, Dh, Dw, S))

"""
import sys

if sys.argv[0] != "/.Main.py":
    import random

    for i in range(100):
        H = random.randint(2, 100)
        W = random.randint(2, 100)
        S = []
        for h in range(H):
            S.append([random.choice(".#") for _ in range(W)])

        Ch, Cw = random.randrange(0, H), random.randrange(0, W)
        Dh, Dw = random.randrange(0, H), random.randrange(0, W)
        S[Ch][Cw] = '.'
        S[Dh][Dw] = '.'
        print(H, W, (Ch, Cw), (Dh, Dw), solve(H, W, Ch, Cw, Dh, Dw, S))
"""

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
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 i in range(H):
    S.append(list(input()))

def visit(S, h, w, d, H, W):
    stack = [(h, w)]
    visited = []
    while stack:
        h, w = stack.pop()
        S[h][w] = d 
        visited.append((h, w))
        for x, y in [(h-1, w), (h+1,w), (h, w-1), (h, w+1)]:
            if 0 <= x < len(S) and 0 <= y < len(S[x]):
                if S[x][y] == '#':
                    continue
                if S[x][y] == '.':
                    stack.append((x, y))
                    continue
                elif S[x][y] > d:
                    stack.append((x, y))
    for x, y in visited:
        for dh in range(-2, 2+1):
            if not 0 <= h+dh < H:
                continue
            for dw in range(-2,2+1):
                if not 0 <= w+dw < W:
                    continue

                hop = S[h+dh][w+dw]
                if hop  == "#":
                    continue
                if hop != ".":
                    continue
                visit(S, h+dh, w+dw, d+1, H, W)


def solve(H, W, Ch, Cw, Dh, Dw, S):
    visited = visit(S, Ch, Cw, 0, H, W)
    if S[Dh][Dw] != ".":
        return S[Dh][Dw]
    else:
        return -1

print(solve(H, W, Ch, Cw, Dh, Dw, S))

"""
import sys

if sys.argv[0] != "/.Main.py":
    import random

    for i in range(100):
        H = random.randint(2, 100)
        W = random.randint(2, 100)
        S = []
        for h in range(H):
            S.append([random.choice(".#") for _ in range(W)])

        Ch, Cw = random.randrange(0, H), random.randrange(0, W)
        Dh, Dw = random.randrange(0, H), random.randrange(0, W)
        S[Ch][Cw] = '.'
        S[Dh][Dw] = '.'
        print(H, W, (Ch, Cw), (Dh, Dw), solve(H, W, Ch, Cw, Dh, Dw, S))
"""

Submission status: Wrong Answer

Solution code:
# Fast IO (be careful about bytestring)

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from collections import deque

movable = 46
blocked = 35
MAXDist = 1 << 15

def isMovable(p,q):
    if p < 0 or q < 0 or p >= H or q >= W:
        return False
    if maze[p][q] == blocked:
        return False
    return True

H,W = map(int,input().split())
sH,sW = map(int,input().split())
eH,eW = map(int,input().split())

maze = []
distance = []
for _ in range(H):
    maze.append(input())
    distance.append([MAXDist] * W)

distance[sH - 1][sW - 1] = 0
deq = deque()
deq.append((sH - 1, sW - 1, 0))

while len(deq):
    h,w,dist = deq.popleft()
    if dist > distance[h][w]:
        continue
    # no spell movement
    if isMovable(h - 1,w) and distance[h-1][w] > dist:
        distance[h-1][w] = dist
        deq.appendleft((h-1,w,dist))
    if isMovable(h + 1,w) and distance[h+1][w] > dist:
        distance[h + 1][w] = dist
        deq.appendleft((h + 1,w,dist))
    if isMovable(h,w - 1) and distance[h][w - 1] > dist:
        distance[h][w - 1] = dist
        deq.appendleft((h,w - 1,dist))
    if isMovable(h,w + 1) and distance[h][w + 1] > dist:
        distance[h][w + 1] = dist
        deq.appendleft((h,w + 1,dist))

    # spell movement
    for i in range(h - 2,h + 3):
        for j in range(w - 2, w + 3):
            if isMovable(i,j) and distance[i][j] > dist + 1:
                distance[i][j] = dist + 1
                deq.append((i,j,dist + 1))

print(distance[eH - 1][eW - 1] if distance[eH - 1][eW - 1] != MAXDist else -1)

Submission status: Wrong Answer

Solution code:
# Fast IO (be careful about bytestring)

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from collections import deque

movable = 46
blocked = 35
MAXDist = 1 << 15

def isMovable(p,q):
    if p < 0 or q < 0 or p >= H or q >= W:
        return False
    if maze[p][q] == blocked:
        return False
    return True

H,W = map(int,input().split())
sH,sW = map(int,input().split())
eH,eW = map(int,input().split())

maze = []
distance = []
for _ in range(H):
    maze.append(input())
    distance.append([MAXDist] * W)

distance[sH - 1][sW - 1] = 0
deq = deque()
deq.append((sH - 1, sW - 1, 0))

while len(deq):
    h,w,dist = deq.popleft()
    if dist > distance[h][w]:
        continue
    # no spell movement
    if isMovable(h - 1,w) and distance[h-1][w] > dist:
        distance[h-1][w] = dist
        deq.appendleft((h-1,w,dist))
    if isMovable(h + 1,w) and distance[h+1][w] > dist:
        distance[h + 1][w] = dist
        deq.appendleft((h + 1,w,dist))
    if isMovable(h,w - 1) and distance[h][w - 1] > dist:
        distance[h][w - 1] = dist
        deq.appendleft((h,w - 1,dist))
    if isMovable(h,w + 1) and distance[h][w + 1] > dist:
        distance[h][w + 1] = dist
        deq.appendleft((h,w + 1,dist))

    # spell movement
    for i in range(h - 2,h + 3):
        for j in range(w - 2, w + 3):
            if isMovable(i,j) and distance[i][j] > dist + 1:
                distance[i][j] = dist + 1
                deq.append((i,j,dist + 1))

print(distance[eH - 1][eW - 1])

Submission status: Wrong Answer

Solution code:
# Fast IO (be careful about bytestring)

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from collections import deque

movable = 46
blocked = 35
MAXDist = 1 << 15

def isMovable(p,q):
    if p < 0 or q < 0 or p >= H or q >= W:
        return False
    if maze[p][q] == blocked:
        return False
    return True

H,W = map(int,input().split())
sH,sW = map(int,input().split())
eH,eW = map(int,input().split())

maze = []
distance = []
for _ in range(H):
    maze.append(input())
    distance.append([MAXDist] * W)

distance[sH - 1][sW - 1] = 0
deq = deque()
deq.append((sH - 1, sW - 1, 0))

while len(deq):
    h,w,dist = deq.popleft()
    if dist >= distance[h][w]:
        continue
    # no spell movement
    if isMovable(h - 1,w) and distance[h-1][w] > dist:
        distance[h-1][w] = dist
        deq.appendleft((h-1,w,dist))
    if isMovable(h + 1,w) and distance[h+1][w] > dist:
        distance[h + 1][w] = dist
        deq.appendleft((h + 1,w,dist))
    if isMovable(h,w - 1) and distance[h][w - 1] > dist:
        distance[h][w - 1] = dist
        deq.appendleft((h,w - 1,dist))
    if isMovable(h,w + 1) and distance[h][w + 1] > dist:
        distance[h][w + 1] = dist
        deq.appendleft((h,w + 1,dist))

    # spell movement
    for i in range(h - 2,h + 3):
        for j in range(w - 2, w + 3):
            if isMovable(i,j) and distance[i][j] > dist + 1:
                distance[i][j] = dist + 1
                deq.append((i,j,dist + 1))

print(distance[eH - 1][eW - 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())
DH,DW = DH-1,DW-1
S=[]
for i in range(H):
    S.append(list(map(lambda x:0 if x=='.' else -1, input().strip())))

def walk(h,w,n):
    r = []
    q = [(h,w)]
    while q:
        h,w = q.pop(0)
        if S[h][w] == 0:
            S[h][w] = n
            r.append((h,w))
        if h == DH and w == DW:
            print(n-1)
            exit()
        if h > 0 and S[h-1][w] == 0:
            q.append((h-1,w))
        if h < H-1 and S[h+1][w] == 0:
            q.append((h+1,w))
        if w > 0 and S[h][w-1] == 0:
            q.append((h,w-1))
        if w < W-1 and S[h][w+1] == 0:
            q.append((h,w+1))
    return r

warp = 1
q = [(CH-1,CW-1)]
while len(q) > 0:
    n = []
    while len(q) > 0:
        h,w = q.pop(0)
        n+=walk(h,w,warp)
    warp += 1
    if len(n) == 0:
        break
    for h,w in n:
        for ah in range(max(0,h-2),min(H,h+3)):
            for aw in range(max(0,w-2),min(W,w+3)):
                if ah == DH and aw == DW:
                    print(warp-1)
                    exit()
                if S[ah][aw] == 0:
                    S[ah][aw] = warp
                    q.append((ah,aw))

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=[input()for _ in [0]*h]
ch-=1;cw-=1;dh-=1;dw-=1;
dist=[[1e9]*w]*h
dist[ch][cw]=0
from collections import deque
q=deque()
q.append((ch,cw))
e=(-2,-1,0,1,2)
while len(q):
	x,y=q.popleft()
	d=dist[x][y]
	for i,j in zip((-1,0,1,0),(0,-1,0,1)):
		ni,nj=x+i,y+j
		if 0>ni or ni>=h or 0>nj or nj>=w: continue
		if s[ni][nj]=='#': continue
		if dist[ni][nj]<=d: continue
		dist[ni][nj]=d
		q.appendleft((ni,nj))
	for ei in e:
		for ej in e:
			ni,nj=x+ei,y+ej
			if 0>ni or ni>=h or 0>nj or nj>=w: continue
			if s[ni][nj]=='#': continue
			if dist[ni][nj]<=d+1: continue
			dist[ni][nj]=d+1
			q.append((ni,nj))
r=dist[dh][dw]
print(r if r!=1e9 else-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=[input()for _ in [0]*h]
ch-=1;cw-=1;dh-=1;dw-=1;
dist=[[1e9]*w]*h
dist[ch][cw]=0
from collections import deque
q=deque()
q.append((ch,cw))
while len(q):
	x,y=q.popleft()
	d=dist[x][y]
	for i,j in zip((-1,0,1,0),(0,-1,0,1)):
		ni,nj=x+i,y+j
		if 0>ni or ni>=h or 0>nj or nj>=w: continue
		if s[ni][nj]=='#': continue
		if dist[ni][nj]<=d: continue
		dist[ni][nj]=d
		q.appendleft((ni,nj))
	for ei in(-2,-1,1,2):
		for ej in(-2,-1,1,2):
			ni,nj=x+ei,y+ej
			if 0>ni or ni>=h or 0>nj or nj>=w: continue
			if s[ni][nj]=='#': continue
			if dist[ni][nj]<=d+1: continue
			dist[ni][nj]=d+1
			q.append((ni,nj))
r=dist[dh][dw]
print(r if r!=1e9 else-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
 
def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    grid = []
    for i in range(H):
        grid.append(list(input()))
 
    INF = 10**15
    d = [[INF for _ in range(W)] for _ in range(H)]    
    d[Ch-1][Cw-1] = 0
 
    direction = [(0, 1), (-1, 0), (0, -1), (1, 0)]
 
    def dfs(ch, cw):   
        stack = deque()
        stack.append((ch, cw))
    
        while stack:
            x, y = stack.popleft()
        
            if(d[x][y] != INF):
                continue
        
            if(x == Dh-1 and y == Dw-1):
                return d[x][y]
    
            for dx, dy in direction:
                nx = x + dx
                ny = y + dy
        
                if(nx < 0 or nx >= H or ny < 0 or ny >= W):
                    continue
                if(grid[nx][ny] == "#"):
                    continue
                d[nx][ny] = d[x][y]
                stack.append((nx, ny))
        
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if(x+i < 0 or x+i >= H or y+j < 0 or y+j >= W):
                        continue
                    if(grid[x+i][y+j] == "#"):
                        continue
                    if(d[x][y] + 1 >= d[x+i][y+j]):
                        continue
                    d[x+i][y+j] = d[x][y] + 1
                    stack.append((x+i, y+j))
        return -1
    
    print(dfs(Ch-1, Cw-1))
        
main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

from collections import deque

INF = 10 ** 12


H, W = map(int, input().split())
s_i, s_j = map(lambda x: int(x) - 1, input().split())
t_i, t_j = map(lambda x: int(x) - 1, input().split())
field = [input() for _ in range(H)]

# 1. bfs でワープなしで到達できるマスを探索
# 2. 1 で見つかったマスから一回ワープして到達できるマスを探索
# 3. 1, 2 を繰り返す


walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

warp_times = [[INF] * W for i in range(H)]
que = deque()

warp_times[s_i][s_j] = 0
que.append((s_i, s_j, 0))

while que:
    i, j, times = que.popleft()
    # ワープ無しで到達できるマスの探索
    for di, dj in walk:
        i_adj, j_adj = i + di, j + dj
        if 0 <= i_adj < H and i <= j_adj < W and field[i_adj][j_adj] == '.':
            if warp_times[i_adj][j_adj] > times:
                warp_times[i_adj][j_adj] = times
                que.appendleft((i_adj, j_adj, times))

    # ワープ有りで到達できるマスの探索
    for di, dj in warp:
        i_adj, j_adj = i + di, j + dj
        if 0 <= i_adj < H and 0 <= j_adj < W and field[i_adj][j_adj] == '.':
            if warp_times[i_adj][j_adj] > times + 1:
                warp_times[i_adj][j_adj] = times + 1
                # ワープ無しで到達できるマスを探索しきった後に探索するため、単に append
                que.append((i_adj, j_adj, times + 1))

ans = warp_times[t_i][t_j] if warp_times[t_i][t_j] < INF else '-1'
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

from collections import deque

INF = 10 ** 12


H, W = map(int, input().split())
s_i, s_j = map(lambda x: int(x) - 1, input().split())
t_i, t_j = map(lambda x: int(x) - 1, input().split())
field = [input() for _ in range(H)]

# 1. bfs でワープなしで到達できるマスを探索
# 2. 1 で見つかったマスから一回ワープして到達できるマスを探索
# 3. 1, 2 を繰り返す


walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

warp_times = [[INF for j in range(W)] for i in range(H)]
que = deque()

warp_times[s_i][s_j] = 0
que.append((s_i, s_j, 0))

while que:
    i, j, times = que.popleft()
    # ワープ無しで到達できるマスの探索
    for di, dj in walk:
        i_adj, j_adj = i + di, j + dj
        if 0 <= i_adj < H and i <= j_adj < W and field[i_adj][j_adj] == '.':
            if warp_times[i_adj][j_adj] > times:
                warp_times[i_adj][j_adj] = times
                que.appendleft((i_adj, j_adj, times))

    # ワープ有りで到達できるマスの探索
    for di, dj in warp:
        i_adj, j_adj = i + di, j + dj
        if 0 <= i_adj < H and 0 <= j_adj < W and field[i_adj][j_adj] == '.':
            if warp_times[i_adj][j_adj] > times + 1:
                warp_times[i_adj][j_adj] = times + 1
                # ワープ無しで到達できるマスを探索しきった後に探索するため、単に append
                que.append((i_adj, j_adj, times + 1))

ans = warp_times[t_i][t_j] if warp_times[t_i][t_j] < INF else '-1'
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

from collections import deque
import sys

INF = 10 ** 12


H, W = map(int, input().split())
s_i, s_j = map(lambda x: int(x) - 1, input().split())
t_i, t_j = map(lambda x: int(x) - 1, input().split())
field = [list(input()) for _ in range(H)]

# 1. bfs でワープなしで到達できるマスを探索
# 2. 1 で見つかったマスから一回ワープして到達できるマスを探索
# 3. 1, 2 を繰り返す


walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

warp_times = [[INF for j in range(W)] for i in range(H)]
que = deque()

warp_times[s_i][s_j] = 0
que.append((s_i, s_j, 0))

while que:
    i, j, times = que.popleft()
    # ワープ無しで到達できるマスの探索
    for di, dj in walk:
        i_adj, j_adj = i + di, j + dj
        if 0 <= i_adj < H and i <= j_adj < W and field[i_adj][j_adj] == '.':
            if warp_times[i_adj][j_adj] > times:
                warp_times[i_adj][j_adj] = times
                que.appendleft((i_adj, j_adj, times))

    # ワープ有りで到達できるマスの探索
    for di, dj in warp:
        i_adj, j_adj = i + di, j + dj
        if 0 <= i_adj < H and 0 <= j_adj < W and field[i_adj][j_adj] == '.':
            if warp_times[i_adj][j_adj] > times + 1:
                warp_times[i_adj][j_adj] = times + 1
                # ワープ無しで到達できるマスを探索しきった後に探索するため、単に append
                que.append((i_adj, j_adj, times + 1))

ans = warp_times[t_i][t_j] if warp_times[t_i][t_j] < INF else '-1'
print(ans)