Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

1

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

Note that he cannot walk diagonally.

Sample Input 2

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

Sample Output 2

-1

He cannot move from there.

Sample Input 3

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

Sample Output 3

0

No use of magic is needed.

Sample Input 4

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

Sample Output 4

2



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


Sample output:
1

Submission status: Wrong Answer

Solution code:
from collections import deque
inf=float("inf")


def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque([])

    x,y=C
    x -=1
    y -=1
    queue.append([x,y])
    color[x][y]="gray"
    D[x][y]=0

    for i in range(h):
        for j in range(w):
            if S[i][j]=="#":
                color[i][j]="black"

    while len(queue)>0:
        x,y=queue.popleft()
        for X in range(max(0,x-2),min(h,x+3)):
            for Y in range(max(0,y-2),min(w,y+3)):
                if color[X][Y]=="white":
                    D[X][Y]=0
                    queue.append([X,Y])
                    color[X][Y]="gray"
        color[x][y]="black"

    return D


def Check():
    point=0
    color=[["white" for _ in range(w)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if D[i][j]==inf:
                color[i][j]="black"

    queue=deque([])
    for i in range(h):
        for j in range(w):
            if D[i][j]==0 and color[i][j]=="white":
                queue.append([i,j])
                color[i][j]="gray"
                while len(queue)>0:
                    x,y=queue.popleft()
                    for a,b in [[1,0],[0,1],[0,-1],[-1,0]]:
                        X,Y=x+a,y+b
                        if 0<=X<h and 0<=Y<w:
                            if color[X][Y]=="white":
                                color[X][Y]="gray"
                                queue.append([X,Y])
                    color[x][y]="black"
                point +=1

    return point


h,w=map(int,input().split())
C=list(map(int,input().split()))
G=list(map(int,input().split()))
S=[list(input()) for _ in range(h)]

D=BFS()
ans=True if D[G[0]-1][G[1]-1]==0 else False
if ans is False:print(-1);exit()
print(Check()-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
import heapq


def read():
    H, W = map(int, input().strip().split())
    CH, CW = map(int, input().strip().split())
    DH, DW = map(int, input().strip().split())
    S = [[0 for j in range(W)] for i in range(H)]
    for i in range(H):
        s = list(input().strip())
        for j in range(W):
            if s[j] == "#":
                S[i][j] = -2
            else:
                S[i][j] = -1
    return H, W, CH, CW, DH, DW, S


def solve(H, W, CH, CW, DH, DW, S, INF=10**7):
    DIR = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    # 島を作る
    id = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == -1:
                id += 1
                S[i][j] = id
                q = deque()
                q.append((i, j))
                while q:
                    y, x = q.popleft()
                    for dy, dx in DIR:
                        ny, nx = y+dy, x+dx
                        if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == -1:
                            S[ny][nx] = id
                            q.append((ny, nx))

    start_id = S[CH-1][CW-1]
    goal_id = S[DH-1][DW-1]
    if start_id == goal_id:
        return 0

    # id: 島の数
    N = id
    G = [dict() for i in range(N)]

    # 島を連結する
    for i in range(H):
        for j in range(W):
            source_id = S[i][j]
            if source_id > 0:
                for k in range(i-2, i+3):
                    for l in range(j-2, j+3):
                        if 0 <= k < H and 0 <= l < W:
                            target_id = S[k][l]
                            if target_id > 0 and source_id != target_id:
                                G[source_id-1][target_id-1] = 1
                                G[target_id-1][source_id-1] = 1
    
    visited = [-1 for i in range(N)]
    q = deque()
    visited[start_id-1] = 0
    q.append(start_id-1)
    while q:
        u = q.pop()
        if u == goal_id-1:
            break
        for v in G[u].keys():
            if visited[v] == -1:
                visited[v] = visited[u] + 1
                q.append(v)
    return visited[goal_id-1]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

H, W = map(int,input().split())
Ch1, Cw1 = map(int,input().split())
Dh1, Dw1 = map(int,input().split())

Ch = Ch1 -1
Cw = Cw1 -1

Dh = Dh1 - 1
Dw = Dw1 - 1


def finding(a,b): #(a,b)から5マス以内に数字マスがあるか索敵
    if type(T[a][b]) == int:
        return T[a][b]
    else:
        V = []
        for i in range(-5,6):
            for j in range(-(5 - abs(i)), 6 - abs(i)):
                if type(T[min(max(0,a+i), H-1)][min(max(0,b+j),W-1)]) == int:
                    V += [T[min(max(0,a+i), H-1)][min(max(0,b+j),W-1)]]
        if V != []:
            return min(n + 1 for n in V)
        else:
            return T[a][b]
            


i = 0
S = []
while i < H:
    s= map(list,input().split())
    li = list(s)
    S += li
    i += 1

T = deepcopy(S)
T[Ch][Cw] = 0
U = []
while T!= U:
    while T != U:
        U = deepcopy(T)
        for i in range(H):
            for j in range(W):
                if T[i][j] != '#':
                    if type(T[max(i-1,0)][j]) == int:
                        T[i][j] = T[max(i-1,0)][j]
                    if type(T[i][min(j+1,W-1)]) == int:
                        T[i][j] = T[i][min(j+1,W-1)]
                    if type(T[min(i+1,H-1)][j]) == int:
                        T[i][j] = T[min(i+1,H-1)][j]
                    if type(T[i][max(j-1,0)]) == int:
                        T[i][j] = T[i][max(j-1,0)]
    for a in range(H):
        for b in range(W):
            if T[a][b] != '#':
                T[a][b] = finding(a,b)


if T[Dh][Dw] == '.':
    print(-1)
else:
    print(T[Dh][Dw])

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
map = []
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visit = [[-1]*w for i in range(h)]
visit[sy - 1][sx - 1] = 0
warp = []
cnt = 0

for i in range(-2, 3):
    for j in range(-2, 3):
        if i == 0 and j == 0:
            continue
        else:
            warp.append([i, j])

for i in range(h):
    s = input()
    map.append(s)

route = deque([[sy - 1, sx - 1]])
wroute = deque([])

while route:
    while route:
        y, x = route.popleft()
        for i, j in move:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] == visit[y][x]:
                        continue
                    visit[k][l] = visit[y][x]
                    route.append([k, l])
                    wroute.append([k, l])

    while wroute:
        y, x = wroute.popleft()
        for i, j in warp:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] != -1:
                        continue
                    visit[k][l] = visit[y][x] + 1
                    route.append([k, l])
    cnt += 1

print(visit[gy - 1][gx - 1])

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(h, w, maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx, 0]])
    visited[sy][sx] = 0
    worps = []
    while queue:
        y, x, worp = queue.popleft()
        print(y, x, worp)
        if [y, x] == [gy, gx]:
            worps.append(worp)
        walkable = False
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + j, x + k
            if new_y < 0 or new_y >= h or new_x < 0 or new_x >= w:
                continue
            if maze[new_y][new_x] == ".":
                if visited[new_y][new_x] == -1 or visited[new_y][new_x] > worp:
                    visited[new_y][new_x] = worp
                    queue.append([new_y, new_x, worp])
                    walkable = True

        if walkable is False:
            for s, t in (
                [1, 1],
                [1, -1],
                [-1, 1],
                [-1, -1],
                [2, 0],
                [2, 1],
                [2, -1],
                [2, 2],
                [2, -2],
                [1, 2],
                [1, -2],
                [0, 2],
                [0, -2],
                [-1, 2],
                [-1, -2],
                [-2, 0],
                [-2, 1],
                [-2, -1],
                [-2, 2],
                [-2, -2],
            ):
                new_y, new_x = y + s, x + t
                if new_y < 0 or new_y >= h or new_x < 0 or new_x >= w:
                    continue
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = worp + 1
                    queue.append([new_y, new_x, worp + 1])
    return min(worps) if len(worps) > 0 else -1


if __name__ == "__main__":
    h, w = map(int, input().split())
    ch, cw = map(lambda x: int(x) - 1, input().split())
    dh, dw = map(lambda x: int(x) - 1, input().split())
    s = [list(input()) for i in range(h)]
    visited = [[-1] * w for j in range(h)]
    print(bfs(h, w, s, visited, ch, cw, dh, dw))

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 = [[10000000 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()
        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:

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
import sys

input = sys.stdin.readline

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 _ in range(3000):
    for _ in range(3000):
        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:
h, w = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
dh, dw = list(map(int, input().split()))
dp = [[1e10+1 for __ in range(w)] for _ in range(h)]
isFirst = True
S = [[] for _ in range(h)]
for i in range(h):
    S[i] = list(input())
    for j in range(w):
        if S[i][j] == '#':
            dp[i][j] = -1
            continue
        if isFirst:
            dp[i][j] = 0
            isFirst = False
        
        t = max(0, i-2)
        b = min(h-1, i+2)
        l = max(0, j-2)
        r = min(w-1, j+2)
        magic = dp[i][j]+1
        for wi in range(t, b+1):
            for wj in range(l, r+1):
                dp[wi][wj] = min(dp[wi][wj], magic)

        if i-1 >= 0:
            dp[i-1][j] = min(dp[i-1][j], dp[i][j])
        if i+1 < h:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if j-1 >= 0:
            dp[i][j-1] = min(dp[i][j-1], dp[i][j])
        if j+1 < w:
            dp[i][j+1] = min(dp[i][j+1], dp[i][j])

for i in range(h):
    for j in range(w):
        if S[i][j] == '#':
            dp[i][j] = -1
            continue
        if isFirst:
            dp[i][j] = 0
            isFirst = False
        
        t = max(0, i-2)
        b = min(h-1, i+2)
        l = max(0, j-2)
        r = min(w-1, j+2)
        magic = dp[i][j]+1
        for wi in range(t, b+1):
            for wj in range(l, r+1):
                dp[wi][wj] = min(dp[wi][wj], magic)

        if i-1 >= 0:
            dp[i-1][j] = min(dp[i-1][j], dp[i][j])
        if i+1 < h:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if j-1 >= 0:
            dp[i][j-1] = min(dp[i][j-1], dp[i][j])
        if j+1 < w:
            dp[i][j+1] = min(dp[i][j+1], dp[i][j])
# print(dp)
if dp[ch-1][cw-1] == 1e10+1 or dp[dh-1][dw-1] == 1e10+1:
    print(-1)
else:
    print(abs(dp[ch-1][cw-1] - dp[dh-1][dw-1]))

Submission status: Wrong Answer

Solution code:

# lrud = [[0, -1], [0, 1], [-1, 0], [1, 0], \
#     [1, -1], [1, 1], [-1, -1], [-1, 1]]
lrud = [[0, -1], [0, 1], [-1, 0], [1, 0]]
lrud2 = [[-1, -1], [1, 1], [-1, 1], [1, -1]]
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Ch, Cw = Ch-1, Cw-1
Dh, Dw = map(int, input().split())
Dh, Dw = Dh-1, Dw-1
S = [list(input()) for i in range(H)]
is_visited = [[float('inf') for j in range(W)]for i in range(H)]
is_visited[Ch][Cw] = 0
for i in range(2):
    for x in range(H):
        for y in range(W):
            cost = int(S[x][y] == '#')
            for dx, dy in lrud:
                nx, ny = x+dx, y+dy
                if 0 <= nx < H and 0 <= ny < W and S[nx][ny] !='#':
                    is_visited[x][y] = min(is_visited[x][y], is_visited[nx][ny]+cost)
            for dx, dy in lrud2:
                nx, ny = x+dx, y+dy
                if 0 <= nx < H and 0 <= ny < W and (cost != int(S[nx][ny]=='#')):
                    is_visited[x][y] = min(is_visited[x][y], is_visited[nx][ny]+cost)
    for x in range(H-1, -1, -1):
        for y in range(W-1, -1, -1):
            cost = int(S[x][y] == '#')
            for dx, dy in lrud:
                nx, ny = x+dx, y+dy
                if 0 <= nx < H and 0 <= ny < W and S[nx][ny] !='#':
                    is_visited[x][y] = min(is_visited[x][y], is_visited[nx][ny]+cost)
            for dx, dy in lrud2:
                nx, ny = x+dx, y+dy
                if 0 <= nx < H and 0 <= ny < W and (cost != int(S[nx][ny]=='#')):
                    is_visited[x][y] = min(is_visited[x][y], is_visited[nx][ny]+cost)
# for i in range(H):
#     print(is_visited[i])
if is_visited[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(is_visited[Dh][Dw])

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
grid = [input() for _ in range(h)]

move = ((1, 0), (-1, 0), (0, 1), (0, -1))
done = [[-1 for _ in range(w)] for _ in range(h)]
todo = deque([(sx - 1, sy - 1)])
done[sx - 1][sy - 1] = 0
check = deque([(sx - 1, sy - 1)])

while check or todo:
    if todo:
        while todo:
            n, m = todo.popleft()
            d = done[n][m]
            for dn, dm in move:
                if n + dn < 0 or m + dm < 0 or n + dn > h - 1 or m + dm > w - 1:
                    pass
                elif done[n + dn][m + dm] >= 0:
                    pass
                elif grid[n + dn][m + dm] == "#":
                    pass
                elif grid[n + dn][m + dm] == ".":
                    todo.append((n + dn, m + dm))
                    check.append((n + dn, m + dm))
                    done[n + dn][m + dm] = d
    if check:
        n, m = check.popleft()
        d = done[n][m]
        for dn in range(-2, 3):
            for dm in range(-2, 3):
                if n + dn < 0 or m + dm < 0 or n + dn > h - 1 or m + dm > w - 1:
                    pass
                elif done[n + dn][m + dm] >= 0:
                    pass
                elif grid[n + dn][m + dm] == "#":
                    pass
                elif grid[n + dn][m + dm] == ".":
                    done[n + dn][m + dm] = d + 1
                    todo.append((n + dn, m + dm))
print(done[gx-1][gy-1])

Submission status: Wrong Answer

Solution code:
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 i in range(h)]

reach = [[False]*w for i in range(h)]
reach[ch][cw] = True

import heapq
q = [[0,ch,cw]]
heapq.heapify(q)

ans = -1
while q:
    cnt,cx,cy = heapq.heappop(q)

    if cx==dh and cy==dw:
        ans = cnt
        break

    f=False
    for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]:
        if not(0<=cx+dx<h and 0<=cy+dy<w):continue
        if s[cx+dx][cy+dy]=='.':
            if not reach[cx+dx][cy+dy]:
                heapq.heappush(q,[cnt,cx+dx,cy+dy])
                reach[cx+dx][cy+dy] = True
            f = True
        else:
            for ddx in range(-1,2):
                for ddy in range(-1,2):
                    if ddx+dx==0 and ddy+dy==0:continue
                    if not(0<=cx+dx+ddx<h and 0<=cy+dy+ddy<w):continue
                    if s[cx+dx+ddx][cy+dy+ddy]=='.':
                        if not reach[cx+dx+ddx][cy+dy+ddy]:
                            heapq.heappush(q,[cnt+1,cx+dx+ddx,cy+dy+ddy])
                            reach[cx+dx+ddx][cy+dy+ddy] = True
                        f = True
    if not f:
        for dx,dy in [[-2,-2],[2,2],[-2,2],[2,-2]]:
            if not(0<=cx+dx<h and 0<=cy+dy<w):continue
            if s[cx+dx][cy+dy]=='.':
                if not reach[cx+dx][cy+dy]:
                    heapq.heappush(q,[cnt+1,cx+dx,cy+dy])
                    reach[cx+dx][cy+dy] = True

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
h, w = map(int, input().split())
c_h, c_w = map(int, input().split())
d_h, d_w = map(int, input().split())
#スタートとゴールの座標を設定
start_h = c_h - 1
start_w = c_w - 1
goal_h = d_h - 1
goal_w = d_w - 1
#迷路の読み込み
maze = [input() for _ in range(h)]

visited = [[False] * w for _ in range(h)]
warp = [0]


def dfs(a, b):
    visited[a][b] = True
    for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0), (-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)]:
        nh = a + dx
        nw = b + dy
        if nh == goal_h and nw == goal_w:
            visited[nh][nw] = True
            return 
        if not 0 <= nh < h or not 0 <= nw < w:
            continue
        if maze[nh][nw] == "#":
            continue
        if visited[nh][nw]:
            continue
        if dx == 0 and dy == 1 or dx == 1 and dy == 0 or dx == 0 and dy == -1 or dx == -1 and dy == 0:
            dfs(nh, nw)
        else:
            warp[0] += 1
            dfs(nh, nw)
       


dfs(start_h, start_w)

if visited[goal_h][goal_w]:
    print(warp[0])
else:
    print("-1")

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)


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

G = [["#"]*(w+2), ["#"]*(w+2)]
for i in range(h):
    G.append(["#", "#"] + list(input()) + ["#", "#"])

G.append(["#"]*(w+2))
G.append(["#"]*(w+2))

S = [[float("inf")]*(w+4) for _ in range(h+4)]

G[dh+1][dw+1] = "g"

ans = 0
def dfs(x,y):
    global ans

    if not(2 <= x < h+2) or not(2 <= y < w+2) or G[x][y] == "#":
        return

    G[x][y] = "#"
    S[x][y] = min(S[x][y], ans)
    dfs(x+1,y)
    dfs(x-1,y)
    dfs(x,y+1)
    dfs(x,y-1)

    for i in range(-2, 3):
        for j in range(-2, 3):
            if i!= 0 and j!= 0 and 2 <= x+i < h+2 and 2 <= y < w+2:
              if G[x+i][y+j] == ".": 
                  ans += 1
                  dfs(x+i, y+j)


dfs(ch+1, cw+1)

if S[dh+1][dw+1] == float("inf"):
    print(-1)
else:
    print(S[dh+1][dw+1])

Submission status: Wrong Answer

Solution code:
# 2020/08/22
# AtCoder Beginner Contest 176 - D

# Input
h, w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
sl = list()
sl.append(['#'] * (w+2))
for i in range(h):
    s = list('#' + input())
    s.append('#')
    sl.append(s)
sl.append(['#'] * (w+2))

wcnt = 0
findflg = False
posq = list()
tl = [[0] * (w+2) for i in range(h+2)]
tl[ch][cw] = 1
posq.append([ch, cw])
passq = list()

loopmax = h  * w

while():
    while(len(posq) > 0):
        th, tw = posq.pop()
        if th == dh and tw == dw:
            findflg = True
            break
            
        passq.append([th, tw])
    
        if sl[th-1][tw] == '.' and tl[th-1][tw] == 0:
            posq.append([th-1, tw])
            tl[th-1][tw] = 1
        elif sl[th][tw-1] == '.' and tl[th][tw-1] == 0:
            posq.append([th, tw-1])
            tl[th][tw-1] = 1
        elif sl[th+1][tw] == '.' and tl[th+1][tw] == 0:
            posq.append([th+1, tw])
            tl[th+1][tw] = 1
        elif sl[th][tw+1] == '.' and tl[th][tw+1] == 0:
            posq.append([th, tw+1])
            tl[th][tw+1] = 1

    if findflg == True:
        break

    while(len(passq) > 0):
        ph, pw = passq.pop()
        
        for i in range(ph-2, ph+3):
            for j in range(pw-2, pw+3):
                if i > 0 and i <= h and j > 0 and j <= w:
                    if sl[i][j] == '.' and tl[i][j] == 0:
                        posq.append([i, j])
                        tl[i][j] = 1
    wcnt = wcnt + 1
    if len(posq) == 0:
        break

# Output
if findflg == True:
    ans = wcnt
else:
    ans = -1
    
print(ans)

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

def walk(h, w):
    q = deque([[h, w]])
    coord = []
    while q:
        y, x = q.popleft()
        for i, j in [(0,1), (0,-1), (1,0),(-1,0)]:
            if (y+i<0 or y+i>H-1) or (x+j<0 or x+j>W-1):
                continue
            if s[y+i][x+j] == '#':
                continue
            if m[y+i][x+j] != -1:
                continue
            q.append([y+i, x+j])
            m[y+i][x+j] = m[h][w]
            coord.append([y+i, x+j])
    return coord


def warp(h, w):
    coord = []
    v = m[h][w]
    h_s = max(0, h-2)
    h_e = min(H-1, h+2)
    w_s = max(0, w-2)
    w_e = min(W-1, w+2)
    for h1 in range(h_s, h_e+1):
        for w1 in range(w_s, w_e+1):
            if h==h1 and w==w1:
                continue
            if m[h1][w1] == -1 and s[h1][w1] != '#':
                m[h1][w1] = v + 1
                coord.append([h1, w1])
    return coord

    
m = [[-1] * W for _ in range(H)]
m[ch][cw] = 0
queue = [[ch, cw]]
while True:
    c = []
    co = []
    for y, x in queue:
        c += walk(y, x)
    c += queue
    for h, w in c:
        co = warp(h, w)
    if len(co) == 0:
        break
    queue = co.copy()
    if [dh, dw] in queue:
        break
print(m[dh][dw])