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:
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)]
 
res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
count = 0
 
que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0
 
while (que or que_warp):
    while (que):
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    que_warp.append((nx,ny))
        que.pop(0)
 
    count += 1
 
    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
        que_warp.pop(0)
 
print (res_S[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 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()
#print('cluster')

def check_cluster_connectivity():
    while len(deq):
        x, y, prev = deq.popleft()
        #print(x, y, prev, s[x][y])
        if s[x][y] == '#':
            continue

        curr = s[x][y]
        curr = int(curr)
        #print('curr', curr, prev)
        if prev is not None and curr != prev:
            k = int(s[x][y])
            g[prev].add(k)

        _prev = 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] != _prev:
                    v = (nx, ny, int(_prev))
                    deq.append(v)

for x in range(h):
    for y in range(w):
        if s[x][y] == '#':
            continue

        # 近傍に壁があるものだけ調べる
        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] == '#':
                v = (x, y, None)
                deq.append(v)
                check_cluster_connectivity()
                break
        else:
            # 近傍に壁がないなら調べる意味なし
            s[x][y] = '#'
#dump()

dist = {k:None for k in g}
def bfs(pos, d):
    if dist[2] is not None:
        return
    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)
else:
    bfs(1, 0)
    
    a = dist[2]
    if a is None:
        # 経路なし
        print(-1)
    else:
        # 経路あり
        print(a)

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 = [list(input()) for _ in range(H)]
dist = [[float("inf")] * W for _ in range(H)]

x = []
for i in range(5):
    for j in range(5):
        if i == 3 and j == 3:
            continue
        x.append((i-2, j-2))
x = set(x)
y = {(0, 1), (1, 0), (-1, 0), (0, -1)}
# x = x - y

from collections import deque
q = deque()
q.append((ch, cw))
dist[ch][cw] = 0
while q:
    h, w = q.popleft()
    for hh, ww in y:
        if h+hh >= 0 and h+hh < H and w+ww >= 0 and w+ww < W and S[h+hh][w+ww] == "." and dist[h+hh][w+ww] > dist[h][w]:
            dist[h+hh][w+ww] = dist[h][w]
            q.appendleft((h+hh, w+ww))
    for hh, ww in x:
        if h+hh >= 0 and h+hh < H and w+ww >= 0 and w+ww < W and S[h+hh][w+ww] == "." and dist[h+hh][w+ww] > dist[h][w]+1:
            dist[h+hh][w+ww] = dist[h][w] + 1
            q.append((h+hh, w+ww))
if dist[dh][dw] == float("inf"):
    print(-1)
else:
    print(dist[dh][dw])

Submission status: Wrong Answer

Solution code:

from collections import deque


H, W = [int(x) for x in input().split()]
Ch, Cw = [int(x) - 1 for x in input().split()]
Dh, Dw = [int(x) - 1 for x in input().split()]

warp_list = [(-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)]

maze = []
warp_count = []
for _ in range(H):
    line = list([x for x in input()])
    maze.append(line)
    warp_count.append([-1] * W)

queue = deque()
warp_queue = deque()

queue.appendleft((Ch, Cw, 0))
warp_count[Ch][Cw] = 0

answer = -1
while queue:
    def maze_check(h, w, use_magic):
        if h < 0 or H <= h:
            return False
        if w < 0 or W <= w:
            return False
        if maze[h][w] == '#':
            return False
        if warp_count[h][w] == -1:
            return True
        if warp_count[h][w] <= use_magic:
            return False

        return True

    now_h, now_w, use_magic = queue.pop()

    if now_h == Dh and now_w == Dw:
        if answer == -1:
            answer = use_magic

        elif answer > use_magic:
            answer = use_magic

        continue

    # 上下左右に移動
    do_warp = True
    if maze_check(now_h+1, now_w, use_magic):
        queue.appendleft((now_h + 1, now_w, use_magic))
        warp_count[now_h + 1][now_w] = use_magic
        do_warp = False
    if maze_check(now_h-1, now_w, use_magic):
        queue.appendleft((now_h - 1, now_w, use_magic))
        warp_count[now_h - 1][now_w] = use_magic
        do_warp = False
    if maze_check(now_h, now_w+1, use_magic):
        queue.appendleft((now_h, now_w + 1, use_magic))
        warp_count[now_h][now_w + 1] = use_magic
        do_warp = False
    if maze_check(now_h, now_w-1, use_magic):
        queue.appendleft((now_h, now_w - 1, use_magic))
        warp_count[now_h][now_w - 1] = use_magic
        do_warp = False

    if do_warp:
        warp_queue.appendleft((now_h, now_w, use_magic))

    if not queue:
        while warp_queue:
            now_h, now_w, use_magic = warp_queue.pop()

            for y, x in warp_list:
                warp_h = now_h + y
                warp_w = now_w + x

                if maze_check(warp_h, warp_w, use_magic+1):
                    queue.append((warp_h, warp_w, use_magic+1))
                    warp_count[warp_h][warp_w] = use_magic + 1

print(answer)

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 = [list(input()) for _ in range(H)]
dist = [[float("inf")] * W for _ in range(H)]

x = []
for i in range(5):
    for j in range(5):
        if i == 3 and j == 3:
            continue
        x.append((i-2, j-2))
x = set(x)
y = {(0, 1), (1, 0), (-1, 0), (0, -1)}
x = x - y

from collections import deque
q = deque()
q.append((ch, cw))
dist[ch][cw] = 0
while q:
    h, w = q.popleft()
    for hh, ww in y:
        if h+hh >= 0 and h+hh < H and w+ww >= 0 and w+ww < W and S[h+hh][w+ww] == "." and dist[h+hh][w+ww] > dist[h][w]:
            dist[h+hh][w+ww] = dist[h][w]
            q.appendleft((h+hh, w+ww))
    for hh, ww in x:
        if h+hh >= 0 and h+hh < H and w+ww >= 0 and w+ww < W and S[h+hh][w+ww] == "." and dist[h+hh][w+ww] > dist[h][w]+1:
            dist[h+hh][w+ww] = dist[h][w] + 1
            q.append((h+hh, w+ww))
if dist[dh][dw] == float("inf"):
    print(-1)
else:
    print(dist[dh][dw])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10**9)

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

G = []
for i in range(h):
    G.append(list(input()))

queue = deque([(ch-1, cw-1)])
S = [[float("inf")]*w for _ in range(h)]
S[ch-1][cw-1] = 0

while queue:
    y, x = queue.popleft()
    dx_dy = [[1,0],[0,1],[-1,0],[0,-1]]
    for j, i in dx_dy:
        if 0 <= x+i < w and 0 <= y+j < h:
            if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                S[y+j][x+i] = S[y][x]
                queue.appendleft((y+j, x+i))

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


if S[dh-1][dw-1] == float("inf"):
    print(-1)
else:
    print(S[dh-1][dw-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 = [list(input()) for _ in range(H)]
used = [[float("inf")] * (W) for _ in range(H)]


x = []
for i in range(5):
    for j in range(5):
        if i == 3 and j == 3:
            continue
        x.append((i-2, j-2))
x = set(x)
y = {(0, 1), (1, 0), (-1, 0), (0, -1)}
x = x - y

from collections import deque
q = deque()
q.append((ch, cw))
used[ch][cw] = 0
while q:
    h, w = q.popleft()
    if (h, w) == (dh, dw):
        print(used[h][w])
        import sys
        sys.exit()
    for hh, ww in y:
        if h+hh >= 0 and h+hh < H and w+ww >= 0 and w+ww < W and S[h+hh][w+ww] == "." and used[h+hh][w+ww] > used[h][w]:
            used[h+hh][w+ww] = used[h][w]
            q.appendleft((h+hh, w+ww))
    for hh, ww in x:
        if h+hh >= 0 and h+hh < H and w+ww >= 0 and w+ww < W and S[h+hh][w+ww] == "." and used[h+hh][w+ww] > used[h][w]+1:
            used[h+hh][w+ww] = used[h][w] + 1
            q.append((h+hh, w+ww))
if used[dh][dw] == float("inf"):
    print(-1)
else:
    print(used[dh][dw])

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs():
    H, W = map(int, input().split())
    C = list(map(int, input().split()))
    D = list(map(int, input().split()))
    S = [list(input()) for _ in range(H)]

    tests = (0, 1), (1, 0), (-1, 0), (0, -1)
    warps = (
        (1, 1),
        (-1, 1),
        (-1, -1),
        (1, -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),
        (2, 2),
        (1, 2),
    )

    start = (0, C[0] - 1, C[1] - 1)
    goal = (D[0] - 1, D[1] - 1)

    queue = deque()
    # (ワープ回数, x, y)
    queue.append(start)

    while queue:
        w_n, x, y = queue.popleft()

        # 通常移動
        for dx, dy in tests:
            nx = x + dx
            ny = y + dy

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

            if S[nx][ny] != "#":
                if S[nx][ny] != "." and w_n >= S[nx][ny]:
                    continue
                else:
                    S[nx][ny] = w_n
                    queue.appendleft((w_n, nx, ny))

        # warp
        w_n += 1
        for dx, dy in warps:
            nx = x + dx
            ny = y + dy

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

            if S[nx][ny] != "#":
                if S[nx][ny] != "." and w_n >= S[nx][ny]:
                    continue
                else:
                    S[nx][ny] = w_n
                    queue.append((w_n, nx, ny))


    if S[goal[0]][goal[1]] == ".":
        print(-1)
    else:
        print(S[goal[0]][goal[1]])


bfs()

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())
Ch-=1
Cw-=1
Dh-=1
Dw-=1

S=[]
for i in range(H):
  s=list(input())
  S.append([-1 if i =="." else i for i in s])

dq = deque()
dq.append((Ch,Cw))
S[Ch][Cw]=0

while dq:
  a=dq.pop()
  for i in range(5):
    for j in range(5):
      if a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W and abs(i)+abs(j)==1 and (S[a[0]-2+i][a[1]-2+j]==-1 or (S[a[0]-2+i][a[1]-2+j]!="#" and S[a[0]-2+i][a[1]-2+j]>=S[a[0]][a[1]]+1)):
        dq.appendleft((a[0]-2+i,a[1]-2+j))
      elif a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W and (S[a[0]-2+i][a[1]-2+j]==-1 or (S[a[0]-2+i][a[1]-2+j]!="#" and S[a[0]-2+i][a[1]-2+j]>=S[a[0]][a[1]]+1)):
        S[a[0]-2+i][a[1]-2+j]=S[a[0]][a[1]]+1
        dq.append((a[0]-2+i,a[1]-2+j))

print(S[Dh][Dw])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    h, w = LI()
    ch, cw = LI_()
    dh, dw = LI_()
    # from time import time
    # st = time()
    s = [None] * h
    for i in range(h):
        s[i] = S()
    q = deque()
    c = defaultdict(lambda :inf)
    q.append((ch, cw))
    c[(ch, cw)] = 0
    nq = deque()
    mv = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    mij = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if i != 0 and j != 0]
    while 1:
        while q:
            nh, nw = q.popleft()
            now = c[(nh, nw)]
            nq.append((nh, nw))
            for mh, mw in mv:
                mh += nh
                mw += nw
                if 0 <= mh < h and 0 <= mw < w and c[(mh, mw)] > now and s[mh][mw] == ".":
                    c[(mh, mw)] = now
                    q.appendleft((mh, mw))
        while nq:
            nh, nw = nq.popleft()
            now = c[(nh, nw)]
            for mi, mj in mij:
                mi += nh
                mj += nw
                if 0 <= mi < h and 0 <= mj < w and c[(mi, mj)] > now + 1 and s[mi][mj] == ".":
                    c[(mi, mj)] = now + 1
                    q.append((mi, mj))
        if len(q) == 0:
            break
    print(-1 if c[(dh, dw)] == inf else c[(dh, dw)])
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
import math


h,w=map(int,input().split())
c=list(map(int,input().split()))
d=list(map(int,input().split()))
s=[list(input()) for _ in range(h)]


def bfs():
    for y in range(h):
        for x in range(w):
            if s[y][x]=='.':
                s[y][x]=math.inf


    s[c[0]-1][c[1]-1]=0
    que=deque([[c[0]-1,c[1]-1]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            if 0<=y+i<h and 0<=x+j<w:
                nexty,nextx=y+i,x+j
                dist=s[nexty][nextx]
                if dist!='#':
                    if dist>s[y][x]:
                        s[nexty][nextx]=s[y][x]
                        que.append([nexty,nextx])
    que=deque([[c[0]-1,c[1]-1]])
    while que:
        y,x=que.popleft()
        for k,l in [(1,0),(0,1),(-1,0),(0,-1),(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<=y+k<h and 0<=x+l<w:
                warpy,warpx=y+k,x+l
                dist=s[warpy][warpx]
                if dist!='#':
                    if k*k+l*l==1 and dist>s[y][x]:
                        s[warpy][warpx]=s[y][x]
                        que.append([warpy,warpx])
                    elif k*k+l*l>1 and dist>s[y][x]+1:
                        s[warpy][warpx]=s[y][x]+1
                        que.append([warpy,warpx])
    if s[d[0]-1][d[1]-1]==math.inf:
        print(-1)
    else:
        print(s[d[0]-1][d[1]-1])

bfs()

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

mvs = [(-1,0),(1,0),(0,1),(0,-1)]
fs = []

for i in range(H):
    r = list(input())
    fs.append(r)


dps = [[-1]*W for i in range(H)]
dps[ch-1][cw-1] = 0
from collections import deque
q = deque([])
q.appendleft((ch-1,cw-1,0))
while len(q)>0:
    h,w,cnt = q.popleft()
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    for dh in range(-2,3):
        for dw in range(-2,3):
            hn = h + dh
            wn = w + dw
            if 0<=hn<H and 0<=wn<W:
                if dps[hn][wn] != -1:continue
                if fs[hn][wn] == ".":
                    if (dh,dw) in mvs:
                        q.appendleft((hn, wn, cnt))
                    else:
                        q.append((hn, wn, cnt+1))

ans = dps[dh_-1][dw_-1]
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

mvs = [(-1,0),(1,0),(0,1),(0,-1)]
fs = []

for i in range(H):
    r = list(input())
    fs.append(r)

INF = 1<<50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
from collections import deque
q = deque([])
q.appendleft((ch-1,cw-1,0))
while len(q)>0:
    h,w,cnt = q.popleft()
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    for dh in range(-2,3):
        for dw in range(-2,3):
            hn = h + dh
            wn = w + dw
            if 0<=hn<H and 0<=wn<W:
                if dps[hn][wn] != INF:continue
                if fs[hn][wn] == ".":
                    if (dh,dw) in mvs:
                        q.appendleft((hn, wn, cnt))
                    else:
                        q.append((hn, wn, cnt+1))

for r in dps:
    print(*r)
ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)

Submission status: Wrong Answer

Solution code:
H, W, ch, cw, dh, dw, *S = open(0).read().split()
H, W, ch, cw, dh, dw = [int(_) for _ in [H, W, ch, cw, dh, dw]]
ch -= 1
cw -= 1
dh -= 1
dw -= 1

stack = [[ch, cw]]
dist = [[None] * W for _ in range(H)]
d = 0
while True:
    stack2 = []
    warp = set()
    while stack:
        x, y = stack.pop()
        if (x, y) == (dh, dw):
            print(d)
            exit()
        if dist[x][y] is not None:
            continue
        dist[x][y] = d
        for dx, dy in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] is None:
                if S[nx][ny] == '.':
                    stack += [[nx, ny]]
                else:
                    warp.add((x, y))
    for x, y in warp:
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] is None and S[
                        x][y] == '.':
                    stack2 += [[nx, ny]]
    if stack2 == []:
        break
    else:
        d += 1
        stack = stack2
print(-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 = [list(input()) for _ in range(H)]
used = [[float("inf")] * (W) for _ in range(H)]


x = []
for i in range(5):
    for j in range(5):
        if i == 3 and j == 3:
            continue
        x.append((i-2, j-2))
x = set(x)
y = {(0, 1), (1, 0), (-1, 0), (0, -1)}
x = x - y

from collections import deque
q = deque()
q.append((ch, cw))
used[ch][cw] = 0
while q:
    h, w = q.popleft()
    for hh, ww in y:
        if h+hh >= 0 and h+hh < H and w+ww >= 0 and w+ww < W and S[h+hh][w+ww] == "." and used[h+hh][w+ww] > used[h][w]:
            used[h+hh][w+ww] = used[h][w]
            q.appendleft((h+hh, w+ww))
    for hh, ww in x:
        if h+hh >= 0 and h+hh < H and w+ww >= 0 and w+ww < W and S[h+hh][w+ww] == "." and used[h+hh][w+ww] > used[h][w]+1:
            used[h+hh][w+ww] = used[h][w] + 1
            q.append((h+hh, w+ww))
if used[dh][dw] == float("inf"):
    print(-1)
else:
    print(used[dh][dw])

Submission status: Wrong Answer

Solution code:
H, W, ch, cw, dh, dw, *S = open(0).read().split()
H, W, ch, cw, dh, dw = [int(_) for _ in [H, W, ch, cw, dh, dw]]
ch -= 1
cw -= 1
dh -= 1
dw -= 1

stack = [[ch, cw]]
dist = [[None] * W for _ in range(H)]
d = 0
while True:
    stack2 = []
    warp = set()
    while stack:
        x, y = stack.pop()
        if (x, y) == (dh, dw):
            print(d)
            exit()
        if dist[x][y] is not None:
            continue
        dist[x][y] = d
        for dx, dy in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] is None:
                if S[nx][ny] == '.':
                    stack += [[nx, ny]]
                else:
                    warp.add((x, y))
    for x, y in warp:
        for dx in range(-1, 2):
            for dy in range(-1, 2):
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] is None and S[
                        x][y] == '.':
                    stack2 += [[nx, ny]]
    if stack2 == []:
        break
    else:
        d += 1
        stack = stack2
print(-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())

G = []
for i in range(h):
    G.append(list(input()))

queue = deque([(ch-1, cw-1)])
S = [[float("inf")]*w for _ in range(h)]
S[ch-1][cw-1] = 0

while queue:
    y, x = queue.popleft()
    dx_dy = [[1,0],[0,1],[-1,0],[0,-1]]
    for k in range(4):
        j, i = dx_dy[k][0], dx_dy[k][1]
        if 0 <= x+i < w and 0 <= y+j < h:
            if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                S[y+j][x+i] = S[y][x]
                queue.appendleft((y+j, x+i))

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


if S[dh-1][dw-1] == float("inf"):
    print(-1)
else:
    print(S[dh-1][dw-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())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]
ans[ch-1][cw-1]=0
count=0

def bfs(ans):
  qu = deque([])
  qu.append((cw-1,ch-1))
  while qu:
    x,y=qu.popleft()

    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        if (x==i and y==j):
          continue
        if 0<=i<w and 0<=j<h:
          if maze[j][i]=="." and (ans[j][i]>ans[y][x] or ans[j][i]==-1):
            if (x==i and y==j+1) or (x==i+1 and y==j) or (x==i-1 and y==j) or (x==i and y==j-1):
              qu.appendleft((i,j))
              ans[j][i] = ans[y][x]
            elif ans[j][i]==-1:
              ans[j][i]=(ans[y][x]+1)
              qu.appendleft((i,j))

bfs(ans)
print(ans[dh-1][dw-1])
#for i in ans:
#  print(*i)

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 = [list(input()) for _ in range(H)]
used = [[-float("inf")] * (W) for _ in range(H)]


x = []
for i in range(5):
    for j in range(5):
        if i == 3 and j == 3:
            continue
        x.append((i-2, j-2))
x = set(x)
y = {(0, 1), (1, 0), (-1, 0), (0, -1)}
x = x - y

from collections import deque
q = deque()
q.append((ch, cw))
used[ch][cw] = 0
while q:
    h, w = q.popleft()
    for hh, ww in y:
        if h+hh >= 0 and h+hh < H and w+ww >= 0 and w+ww < W and S[h+hh][w+ww] == ".":
            if used[h+hh][w+ww] < 0 or used[h+hh][w+ww] > used[h][w]:
                used[h+hh][w+ww] = used[h][w]
                q.appendleft((h+hh, w+ww))
    for hh, ww in x:
        if h+hh >= 0 and h+hh < H and w+ww >= 0 and w+ww < W and S[h+hh][w+ww] == ".":
            if used[h+hh][w+ww] < 0 or used[h+hh][w+ww] > used[h][w]+1: 
                used[h+hh][w+ww] = used[h][w] + 1
                q.append((h+hh, w+ww))
if used[dh][dw] < 0:
    print(-1)
else:
    print(used[dh][dw])

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
PX = [-2, -2, -2, -2, -2, -1, -1, 0, 0, 1, 1, 2, 2, 2, 2, 2]
PY = [-2, -1, 0, 1, 2, -2, 2, -2, 2, -2, 2, -2, -1, 0, 1, 2]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for i in range(4):
        nx = x + NX[i]
        ny = y + NY[i]
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "#":
            if grid[ny][nx] == -1 or grid[ny][nx] > count:
                grid[ny][nx] = count
                que.appendleft((count, ny, nx))
    for i in range(16):
        px = x + PX[i]
        py = y + PY[i]
        if 0 <= px < w and 0 <= py < h and S[py][px] != "#":
            if grid[py][px] == -1 or grid[py][px] > count + 1:
                grid[py][px] = count + 1
            que.append((count + 1, py, px))

print(grid[dh][dw])

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())
maze = [list(input()) for _ in range(H)]

def BFS(maze,s,g):
  q1,q2 = deque([s]),deque()
  checked = []
  m = 0
  while len(q1)>0 or len(q2)>0:
    if len(q1)>0: h,w,n = q1.popleft()
    elif len(q2)>0: h,w,n = q2.popleft()
    if (h,w)==g: return n
    dp = [(i-2,j-2) for i in range(5) for j in range(5) if (i-2,j-2)!=(0,0)]
    for i in dp:
      if (h+i[0],w+i[1]) in checked: continue
      else:
        if (0<=h+i[0]<len(maze)) and (0<=w+i[1]<len(maze[0])) and maze[h+i[0]][w+i[1]]==".":
          checked.append((h+i[0],w+i[1]))
          if sum(i)>1: q2.append((h+i[0],w+i[1],n+1))
          else: q1.append((h+i[0],w+i[1],n))
  return -1

print(BFS(maze,(CH-1,CW-1,0),(DH-1,DW-1)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    h, w = LI()
    ch, cw = LI()
    dh, dw = LI_()
    # from time import time
    # st = time()
    s = SR(h)
    q = deque()
    c = defaultdict(lambda :inf)
    q.append((ch-1, cw-1))
    c[(ch - 1, cw - 1)] = 0
    nq = deque()
    flag = True
    while 1:
        while q:
            nh, nw = q.popleft()
            if flag:
                nq.append((nh, nw))
                flag = False
            now = c[(nh, nw)]
            for mh, mw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                mh += nh
                mw += nw
                if 0 <= mh < h and 0 <= mw < w and c[(mh, mw)] > now and s[mh][mw] == ".":
                    c[(mh, mw)] = now
                    q.appendleft((mh, mw))
                    nq.append((mh, mw))
        while nq:
            nh, nw = nq.popleft()
            now = c[(nh, nw)]
            for i in range(-2, 3):
                i += nh
                if 0 <= i < h:
                    si = s[i]
                    for j in range(-2, 3):
                        j += nw
                        if 0 <= i < h and 0 <= j < w and c[(i, j)] > now + 1 and si[j] == ".":
                            c[(i, j)] = now + 1
                            q.append((i, j))
                            flag = True
        if len(q) == 0:
            break
    print(-1 if c[(dh, dw)] == inf else c[(dh, dw)])
    return


#main
if __name__ == '__main__':
    solve()