Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

1

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

Note that he cannot walk diagonally.

Sample Input 2

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

Sample Output 2

-1

He cannot move from there.

Sample Input 3

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

Sample Output 3

0

No use of magic is needed.

Sample Input 4

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

Sample Output 4

2



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


Sample output:
1

Submission status: Wrong Answer

Solution code:
def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(10000000)
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())

    s = [['#'] + list(input()) + ['#'] for _ in range(h)]
    wall = ['#'] * (w + 2)
    s.insert(0, wall)
    s.append(wall)

    visited = [[False for _ in range(w + 2)] for _ in range(h + 2)]
    group = [[0 for _ in range(w + 2)] for _ in range(h + 2)]
    gd = defaultdict(list)

    def dfs(i, j, g):
        if visited[i][j]:
            return
        visited[i][j] = True
        group[i][j] = g
        gd[g].append((i, j))
        for p, q in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
            if s[i + p][j + q] == '#':
                continue
            dfs(i + p, j + q, g)

    g = 1
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if s[i][j] == '#':
                continue
            dfs(i, j, g)
            g += 1

    gstart = group[ch][cw]
    ggoal = group[dh][dw]

    visited = [[False for _ in range(w + 2)] for _ in range(h + 2)]

    def search(i, j, gfrom, step):
        visited[i][j] = True
        gij = group[i][j]
        if gij != gfrom:
            step += 1
        if gij == ggoal:
            return step
        for p in range(-2, 3):
            for q in range(-2, 3):
                if not 1 <= i + p <= h + 1:
                    continue
                if not 1 <= j + q <= w + 1:
                    continue
                if s[i + p][j + q] == '#':
                    continue
                if visited[i + p][j + q]:
                    continue
                return search(i + p, j + q, gij, step)

    g = gstart
    gs = gd[g]
    ans = float('Inf')
    if gstart == ggoal:
        print(0)
        return
    for (i, j) in gs:
        res = search(i, j, 1, 0)
        if res is not None:
            ans = min(ans, res)

    print(-1 if ans == float('Inf') else ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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



def clear_maze(h, w, ch, cw, dh, dw, S):
    visited = [[-1] * w for _ in range(h)]
    visited[ch - 1][cw - 1] = 0
    queue = deque([[ch - 1 , cw - 1]])
    while queue:
        y, x = queue.popleft()
        if [y, x] == [dh - 1, dw - 1]:
            return visited[y][x]
        num = 0
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            n_y = y + i
            n_x = x + j
            if n_y >= 0 and n_y < h and n_x >= 0 and n_x < w and S[n_y][n_x] == '.':
                if visited[n_y][n_x] == -1:
                    visited[n_y][n_x] = visited[y][x]
                    queue.append([n_y, n_x])
                else:
                    if visited[y][x] < visited[n_y][n_x]:
                        queue.append([n_y, n_x])
                    visited[n_y][n_x] = min(visited[n_y][n_x], visited[y][x])
        for i in range(-2, 2 + 1):
            for j in range(-2, 2 + 1):
                if not [i, j] in ([1, 0], [-1, 0], [0, 0], [0, 1], [0, -1]):
                    n_y = y + i
                    n_x = x + j
                    if n_y >= 0 and n_y < h and n_x >= 0 and n_x < w and S[n_y][n_x] == '.':
                        if visited[n_y][n_x] == -1:
                            visited[n_y][n_x] = visited[y][x] + 1
                            queue.append([n_y, n_x])
                        else:
                            if visited[y][x] + 1 < visited[n_y][n_x]:
                                queue.append([n_y, n_x])
                            visited[n_y][n_x] = min(visited[n_y][n_x], visited[y][x] + 1)
    return -1

print(clear_maze(h, w, ch, cw, dh, dw, S))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
c1, c2 = map(int,input().split())
d1, d2 = map(int,input().split())
data = []
for i in range(h):data.append(input())
ans = []
for i in range(h):ans.append([1e9]*w)

warp = [-2, -1, 0, 1, 2]
ans[c1-1][c2-1] = 0
for i in range(h):
    for j in range(w):


        for t1 in warp:
            for t2 in warp:
                if(t1==t2 and t1==0):continue
                if(i+t1 < 0 or j+t2 < 0 or i+t1 >= h or j+t2 >= w):continue
                if (data[t1+i][t2+j] == "#"):continue
                if(abs(t1)+abs(t2) <= 1 ):
                    ans[t1+i][t2+j] = min(ans[t1+i][t2+j], ans[i][j])
                else:
                    ans[t1+i][t2+j] = min(ans[t1+i][t2+j], ans[i][j]+1)


if(ans[d1-1][d2-1] == 1e9):print(-1)
else:print(ans[d1-1][d2-1])

Submission status: Wrong Answer

Solution code:
import queue
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
table = []
for i in range(h):
    table.append(input())
# print(table)

def check(h_tmp, w_tmp, steps):
    if h_tmp < 0 or w_tmp < 0 or h_tmp >= h or w_tmp >= w:
        return False
    elif visit[h_tmp][w_tmp] <= steps:
        return False
    elif table[h_tmp][w_tmp] == '#':
        return False
    else:
        return True


q = queue.Queue()
q.put((ch, cw, 0, 0))
ans = 1000000000
visit = [[1000000000] * w] * h
# print(visit)
while not q.empty():
    now = q.get()
    visit[now[0]][now[1]] = min(visit[now[0]][now[1]], now[3])
    # print(q.qsize())
    # print(visit)
    if now[0] == dh and now[1] == dw:
        # print(now[0], now[1])
        ans = visit[now[0]][now[1]]
        continue
    # print(now[0], now[1])

    if check(now[0]+1, now[1], now[3]):
        q.put((now[0]+1, now[1], now[2] + 1, now[3]))
    if check(now[0], now[1]+1, now[3]):
        q.put((now[0], now[1]+1, now[2] + 1, now[3]))
    if check(now[0]-1, now[1], now[3]):
        q.put((now[0]-1, now[1], now[2] + 1, now[3]))
    if check(now[0], now[1]-1, now[3]):
        q.put((now[0], now[1]-1, now[2] + 1, now[3]))
    if check(now[0]+1, now[1]+1, now[3]+1):
        q.put((now[0]+1, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]+1, now[3]+1):
        q.put((now[0]-1, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]+1, now[1]-1, now[3]+1):
        q.put((now[0]+1, now[1]-1, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]-1, now[3]+1):
        q.put((now[0]-1, now[1]-1, now[2] + 1, now[3]+1))

    if check(now[0]+2, now[1], now[3]+1):
        q.put((now[0]+2, now[1], now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]+1, now[3]+1):
        q.put((now[0]+2, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]+2, now[3]+1):
        q.put((now[0]+2, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]-1, now[3]+1):
        q.put((now[0]+2, now[1]-1, now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]-2, now[3]+1):
        q.put((now[0]+2, now[1]-2, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1], now[3]+1):
        q.put((now[0]-2, now[1], now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]+1, now[3]+1):
        q.put((now[0]-2, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]+2, now[3]+1):
        q.put((now[0]-2, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]-1, now[3]+1):
        q.put((now[0]-2, now[1]-1, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]-2, now[3]+1):
        q.put((now[0]-2, now[1]-2, now[2] + 1, now[3]+1))

    if check(now[0], now[1]+2, now[3]+1):
        q.put((now[0], now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]+2, now[3]+1):
        q.put((now[0]-1, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]+1, now[1]+2, now[3]+1):
        q.put((now[0]+1, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0], now[1]-2, now[3]+1):
        q.put((now[0], now[1]-2, now[2] + 1, now[3]+1))
    if check(now[0]+1, now[1]-2, now[3]+1):
        q.put((now[0]+1, now[1]-2, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]-2, now[3]+1):
        q.put((now[0]-1, now[1]-2, now[2] + 1, now[3]+1))
if not ans == 1000000000:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import collections, sys
import numpy as np
input = sys.stdin.readline

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = []
for i in range(h):
    s.append(list(input()))
s = np.array(s)
num = np.array([[float("inf") for i in range(w)] for i in range(h)])
flag = np.array([[False for i in range(w)] for i in range(h)])
num[ch - 1][cw - 1] = 0
flag[ch - 1][cw - 1] = True
queue = collections.deque([[ch, cw]])
d1 = np.array([[-1, 0], [1, 0], [0, -1], [0, 1]])
d2 = np.array([[-1, -1], [-1, 1], [1, -1], [1, 1], [-2, 0], [2, 0], [0, -2], [0, 2]])
d3 = np.array([[-2, -1], [-1, -2], [2, -1], [1, -2], [-2, 1], [-1, 2], [2, 1], [1, 2]])
d4 = np.array([[-2, -2], [-2, 2], [2, -2], [2, 2]])
while queue:
    test = queue.popleft()
    y = test[0]
    x = test[1]
    temp = num[y - 1][x - 1]
    for i in d1:
        x2 = x + i[1]
        y2 = y + i[0]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == ".":
            num[y2 - 1][x2 - 1] = temp
            if flag[y2 - 1][x2 - 1] == False:
                queue.append([y2, x2])
                flag[y2 - 1][x2 - 1] = True
    for i in d2:
        x2 = x + i[1]
        y2 = y + i[0]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == ".":
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            if flag[y2 - 1][x2 - 1] == False:
                queue.append([y2, x2])
                flag[y2 - 1][x2 - 1] = True
    for i in d3:
        x2 = x + i[1]
        y2 = y + i[0]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == ".":
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            if flag[y2 - 1][x2 - 1] == False:
                queue.append([y2, x2])
                flag[y2 - 1][x2 - 1] = True
    for i in d4:
        x2 = x + i[1]
        y2 = y + i[0]
        if 1 <= x2 <= w and 1 <= y2 <= h and s[y2 - 1][x2 - 1] == ".":
            num[y2 - 1][x2 - 1] = min(temp + 1, num[y2 - 1][x2 - 1])
            if flag[y2 - 1][x2 - 1] == False:
                queue.append([y2, x2])
                flag[y2 - 1][x2 - 1] = True
if num[dh - 1][dw - 1] == float("inf"):
    print(-1)
else:
    print(int(num[dh - 1][dw - 1]))

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


h, w = map(int, input().split())
si, sj = LI()
gi, gj = LI()
si, sj = si-1, sj-1
gi, gj = gi-1, gj-1
c = [list(input()) for i in range(h)]
is_seen = [[False for j in range(w)] for i in range(h)]
stack = deque([[sj, si]])
while stack:
    now_i, now_j = stack.pop()
    is_seen[now_i][now_j] = True
    for i, j in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        next_i = now_i + i
        next_j = now_j + j
        if next_i < 0 or next_j < 0 or next_i > h - 1 or next_j > w - 1 or c[next_i][next_j] == '#':
            continue
        if is_seen[next_i][next_j] == False:
            stack.append([next_i, next_j])

if is_seen[gi][gj]:
    print(0)
    exit()
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
# import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
enu = enumerate
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
HW = [list(input()) for _ in range(H)]


def check(ny, nx):
    if 0 <= ny < H and 0 <= nx < W and HW[ny][nx] == ".":
        return True
    else:
        return False


HW[ch - 1][cw - 1] = "#"
dist = [[float("inf")] * W for _ in range(H)]
# print("dist")
# pl(dist)
dist[ch - 1][cw - 1] = 0


deq = deque()
deq.append([(ch - 1, cw - 1)])  # insert indices
ddy = [-1, 0, 1, 0]
ddx = [0, -1, 0, 1]
warpy = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
warpx = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]
step = 0
found = False
cnt = 0
while deq[0]:
    nqueue = []
    cqueue = deq.popleft()
    # pl(HW)
    # pl(dist)
    for val in cqueue:
        y, x = val
        # if val == (gy - 1, gx - 1):
        #     found = True
        #     break
        for dy, dx in zip(ddy, ddx):
            chky = set()
            chkx = set()
            ny, nx = y + dy, x + dx
            if check(ny, nx):
                if dy != 0:
                    chky.add(dy)
                    chky.add(dy * 2)
                if dx != 0:
                    chkx.add(dx)
                    chkx.add(dx * 2)
                HW[ny][nx] = "#"
                if dist[y][x] < dist[ny][nx]:
                    dist[ny][nx] = dist[y][x]
                # dist[ny][nx] = min(dist[ny][nx], dist[y][x])
                nqueue.append((ny, nx))
        for dy, dx in zip(warpy, warpx):
            if (dy in chky) or (dx in chkx):
                continue
            # cnt += 1
            ny, nx = y + dy, x + dx
            if check(ny, nx) and dist[ny][nx] == float("inf"):
                if dist[y][x] + 1 < dist[ny][nx]:
                    dist[ny][nx] = dist[y][x] + 1
                # dist[ny][nx] = min(dist[ny][nx], dist[y][x] + 1)
                nqueue.append((ny, nx))
    # if found:
    #     break
    deq.append(nqueue)
    # step += 1
# print(cnt)
val = dist[dh - 1][dw - 1]
if val == float("inf"):
    print(-1)
else:
    print(val)
# print(dist[dh - 1][dw - 1])

Submission status: Wrong Answer

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

from collections import defaultdict
from queue import Queue

path = dict()
cache = set()

Cur = (Cw-1, Ch-1)
Q = Queue()
Q.put(Cur)
cache.add(Cur)

path[Cur] = 0
G = (Dw - 1, Dh - 1)

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

wdx = []
wdy = []

# warp = 0
while not Q.empty():
    node = Q.get()
    # print("search: ", node)
    
    if node == G:
        # print("Goal")
        # cache.add(G)
        # print(path)
        pass

    else:
        cx, cy = node
        # cache.add(node)

        # move
        for di in range(4):
            nx = cx + dx[di]
            ny = cy + dy[di]

            if W > nx >= 0 and H > ny >= 0:
                nt = (nx, ny)
                # print(nt)
                if S[ny][nx] == '.':
                    # print(path)
                    if nt not in cache:
                        # 移動可能
                        Q.put(nt)
                        cache.add(nt)
                        path[nt] = path[node]

                    elif nt in path.keys() and path[node] < path[nt]:
                        # 小さいパスがあるなら更新
                        path[nt] = path[node]
                        # Q済みなのでQは更新しない
        
        # warp
        for wdx in range(-2, 3, 1):
            for wdy in range(-2, 3, 1):

                nx = cx + wdx
                ny = cy + wdy
                nt = (nx, ny)
                # print("warp node::", nt)

                if W > nx >= 0 and H > ny >= 0:
                    if S[ny][nx] == '.':
                        # print(path)
                        # print("search warp::to ", nt, ",::from ", node)
                        if nt not in cache:
                            Q.put(nt)
                            cache.add(nt)
                            path[nt] = path[node] + 1
                        # elif nt in path.keys() and path[node] < path[nt]:
                        #     # 小さいパスがあるなら更新
                        #     print("path[", node, "] < path[", nt, "]")
                        #     print(path)
                        #     path[nt] = path[node]
                        #     # Q済みなのでQは更新しない                   

print(path[G] if G in path.keys() else -1)

Submission status: Wrong Answer

Solution code:
import numpy as np
import collections

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

Chw = list(map(int, input().split()))
Dhw = list(map(int, input().split()))

Ss = []
for _ in range(H):
    tmp = input()
    Ss.append(list(tmp))

mazeArray = np.zeros((H+6, W+6), dtype = 'int64')

for i in range(H+6):
    for j in range(W+6):
        if(i < 3 or i > H+2):
            mazeArray[i][j] = -1
        
        elif(j < 3 or j > W+2):
            mazeArray[i][j] = -1
        
        else:
            if(Ss[i - 3][j-3] == "#"):
                mazeArray[i][j] = -1
            else:
                mazeArray[i][j] = 100000

#前準備完了

H_que = collections.deque()
W_que = collections.deque()

H_que.append(Chw[0])
W_que.append(Chw[1])

mazeArray[Chw[0]+2][Chw[1]+2] = 0

#print(mazeArray)

for _ in range(5 * 10**4):
    H_iti = H_que.popleft() + 2
    W_iti = W_que.popleft() + 2

    #上移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti - 1][W_iti]):
        mazeArray[H_iti - 1][W_iti] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 3)
        W_que.append(W_iti - 2)

    elif(mazeArray[H_iti - 1][W_iti] == -1):
        for i in range(H_iti-2, H_iti):
            for j in range(W_iti -2, W_iti + 3):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)
                
    #下移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti + 1][W_iti]):
        mazeArray[H_iti + 1][W_iti] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 1)
        W_que.append(W_iti - 2)
        
    elif(mazeArray[H_iti+1][W_iti] == -1):
        for i in range(H_iti+1, H_iti+3):
            for j in range(W_iti -2, W_iti + 3):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)

    #左移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti][W_iti - 1]):
        mazeArray[H_iti][W_iti - 1] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 2)
        W_que.append(W_iti - 3)

    elif(mazeArray[H_iti][W_iti-1] == -1):
        for i in range(H_iti-2, H_iti+3):
            for j in range(W_iti -2, W_iti):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)

    #右移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti][W_iti + 1]):
        mazeArray[H_iti][W_iti + 1] = mazeArray[H_iti][W_iti]

        H_que.append(H_iti - 2)
        W_que.append(W_iti - 1)

    elif(mazeArray[H_iti][W_iti-1] == -1):
        for i in range(H_iti-2, H_iti+3):
            for j in range(W_iti +1, W_iti + 3):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)

    #移動Bパターン


    if(len(H_que) == 0):
        break

#print(mazeArray)

if(mazeArray[Dhw[0]+2][Dhw[1]+2] == 100000):
    print(-1)

else:
    print(mazeArray[Dhw[0]+2][Dhw[1]+2])

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    h, w = tuple(map(int, input().split()))
    c = tuple(map(int, input().split()))
    d = tuple(map(int, input().split()))
    s = [list(input()) for i in range(h)]

    flag = 0
    start = (c[0] - 1, c[1] - 1)
    goal = (d[0] - 1, d[1] - 1)
    available_mat = [[goal]]
    available_list = [goal]

    while not len(available_mat[-1]) == 0:
        index = 0
        while index < len(available_mat[-1]):
            i, j = available_mat[-1][index]
            if i > 0 and s[i - 1][j] == '.':
                if not (i - 1, j) in available_list:
                    available_mat[-1].append((i - 1, j))
                    available_list.append((i - 1, j))
            if j > 0 and s[i][j - 1] == '.':
                if not (i, j - 1) in available_list:
                    available_mat[-1].append((i, j - 1))
                    available_list.append((i, j + 1))
            if i < h - 1 and s[i + 1][j] == '.':
                if not (i + 1, j) in available_list:
                    available_mat[-1].append((i + 1, j))
                    available_list.append((i + 1, j))
            if j < w - 1 and s[i][j + 1] == '.':
                if not (i, j + 1) in available_list:
                    available_mat[-1].append((i, j + 1))
                    available_list.append((i, j + 1))
            index += 1
        if start in available_list:
            flag = 1
            break
        available_mat.append([])
        for coordinate in available_mat[-2]:
            for i in range(max(0, coordinate[0] - 2), min(h, coordinate[0] + 3)):
                for j in range(max(0, coordinate[1] - 2), min(w, coordinate[1] + 3)):
                    if not (i, j) in available_list and s[i][j] == '.':
                        available_list.append((i, j))
                        available_mat[-1].append((i, j))
        if start in available_list:
            flag = 1
            break

    print(len(available_mat) - 1 if flag == 1 else -1)

Submission status: Wrong Answer

Solution code:
import sys, math

# input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [list(input()) for _ in range(H)]


uf = UnionFind(H*W)
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            uf.parents[W*i+j] = math.inf
            continue
        if i != H-1 and S[i + 1][j] == '.':
            uf.union(W*i + j, W*(i+1) + j)
        if j != W-1 and S[i][j+1] == '.':
            uf.union(W*i + j, W*i + j + 1)

groupidx = {k: v for v, k in enumerate(uf.roots())}
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            S[i][j] = -1
        else:
            S[i][j] = groupidx[uf.find(W*i+j)]


groups = list(range(len(uf.roots())))
can_reach = [[False]*len(groups) for _ in range(len(groups))]
for i in range(H):
    for j in range(W):
        if S[i][j] == -1:
            continue
        g = []
        for s in S[i:i+1]:
            g += s[j:j + 1]
            # g += s[max(0, j - 2):j + 3]

        g = set(g)
        if -1 in g:
            g.remove(-1)
        for k in g:
            can_reach[S[i][j]][k] = True
            can_reach[k][S[i][j]] = True

can_reach_ = {}
for i in range(len(groups)):
    can_reach_[i] = [j for j, k in enumerate(can_reach[i]) if k]
ans = 0
s = S[Ch-1][Cw-1]
g = S[Dh-1][Dw-1]
if s==g:
    print(0)
    sys.exit()

reached = [s]
searched = [False]*len(groups)
ans = 0
while len(reached)>0:
    new_reached = []
    ans += 1
    for p in reached:
        searched[p] = True
    for p in reached:
        for k in can_reach_[p]:
            if k == g:
                print(ans)
                sys.exit()
            if not searched[k]:
                new_reached.append(k)
    reached = list(set(new_reached))
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())
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

    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
                            memo_que.append([sh + ph, sw + pw, count + 1])
    memo_que.clear()

print(-1)

Submission status: Wrong Answer

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

que = set()
que.add((Ch-1, Cw-1))
d = {}
d[(Ch-1, Cw-1)] = 0

def check(newh, neww, dis, c):
    if newh < 0 or newh >= H or neww < 0 or neww >= W:
        return
    if S[newh][neww] == "#":
        return
    if dis == 1:
        if (newh,neww) in d:
            if c < d[(newh,neww)]:
                d[(newh, neww)] = c
                que.add((newh, neww))
        else:
            d[(newh, neww)] = c
            que.add((newh, neww))
    else:
        if (newh,neww) in d:
            d[(newh, neww)] = min(d[(newh,neww)], c+1)
        else:
            d[(newh, neww)] = c+1
            que.add((newh, neww))
    

while que:
    h, w = que.pop()
    nowc = d[(h,w)]
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == 0 and j == 0:
                continue
            check(h+i, w+j, abs(i)+abs(j), nowc)

if (Dh-1, Dw-1) in d:
    print(d[(Dh-1, Dw-1)])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
cy, cx = map(lambda x: int(x) - 1, input().split())
dy, dx = map(lambda x: int(x) - 1, input().split())
table = [list(input()) for _ in range(h)]
if cy == dy and cx == dx:
    print(0)
    exit()
if table[cy][cx] == "#" or table[dy][dx] == "#":
    print(-1)
    exit()
stack = [[cy, cx]]
table[cy][cx] = 0
step = [0, 1, 0, -1, 0]
step2 = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, 2],
         [0, -2], [0, 2], [1, -2], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1],
         [2, 2]]
while len(stack) > 0:
    cur = stack.pop()
    if cur[0] == dy and cur[1] == dx:
        break
    for [i, j] in step2:
        ny, nx = cur[0] + i, cur[1] + j
        if 0 <= ny < h and 0 <= nx < w and table[ny][nx] != "#":
            if table[ny][nx] == ".":
                table[ny][nx] = table[cur[0]][cur[1]] + 1
                stack.append([ny, nx])
            elif table[ny][nx] > table[cur[0]][cur[1]] + 1:
                table[ny][nx] = table[cur[0]][cur[1]] + 1
                stack.append([ny, nx])

    cur2 = cur
    for i in range(4):
        ny, nx = cur2[0] + step[i], cur2[1] + step[i + 1]
        if 0 <= ny < h and 0 <= nx < w and table[ny][nx] != "#":
            if table[ny][nx] == ".":
                table[ny][nx] = table[cur2[0]][cur2[1]]
                stack.append([ny, nx])
            elif table[ny][nx] > table[cur2[0]][cur2[1]]:
                table[ny][nx] = table[cur2[0]][cur2[1]]
                stack.append([ny, nx])
print(-1 if table[dy][dx] == "." else table[dy][dx])