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: Runtime Error

Solution code:
H,W=[int(i) for i in input().split(" ")]
Ch, Cw=[int(i)+1 for i in input().split(" ")]
Dh,Dw=[int(i)+1 for i in input().split(" ")]
S=[[False for i in range(W+4)],[False for i in range(W+4)]]
for i in range(H):
    S.append([False,False]+[j=='.' for j in input()]+[False,False])
S+=[[False for i in range(W+4)],[False for i in range(W+4)]]

def check(h,w,island_num):
    assert S[h][w]
    block[h][w]=island_num
    if S[h-1][w] and block[h-1][w]==-1:
        check(h-1,w,island_num)
    if S[h+1][w] and block[h+1][w]==-1:
        check(h+1,w,island_num)
    if S[h][w-1] and block[h][w-1]==-1:
        check(h,w-1,island_num)
    if S[h][w+1] and block[h][w+1]==-1:
        check(h,w+1,island_num)

block=[]
for i in range(H+4):
    block.append([-1 for j in range(W+4)])

island_num=0

for h in range(H+4):
    for w in range(W+4):
        if S[h][w] and block[h][w]==-1:
            check(h,w,island_num)
            island_num+=1


neighbor={}
for island in range(island_num):
    neighbor[island]=set()


for h in range(2,H+2):
    for w in range(2,W+2):
        if block[h][w]!=-1:
            for y in range(h-2,h+3):
                for x in range(w-2, w+3):
                    if block[y][x]!=-1 and block[h][w]!=block[y][x]:
                        neighbor[block[h][w]].add(block[y][x])


start=block[Ch][Cw]
goal=block[Dh][Dw]
assert start!=-1
assert goal!=-1



dist=[10**10 for i in range(island_num)]
dist[start]=0

nexts=[start]
while len(nexts)!=0:
    for n in nexts:
        _nexts=[]
        for neigh in neighbor[n]:
            assert neigh!=-1
            if dist[neigh]>dist[n]+1:
                _nexts.append(neigh)
                dist[neigh]=dist[n]+1
        nexts=set(_nexts)

if dist[goal]==10**10:
    print(-1)
    assert dist[goal]==-1
else:
    print(dist[goal])

Submission status: Runtime Error

Solution code:
H,W=[int(i) for i in input().split(" ")]
Ch, Cw=[int(i)+1 for i in input().split(" ")]
Dh,Dw=[int(i)+1 for i in input().split(" ")]
S=[[False for i in range(W+4)],[False for i in range(W+4)]]
for i in range(H):
    S.append([False,False]+[j=='.' for j in input()]+[False,False])
S+=[[False for i in range(W+4)],[False for i in range(W+4)]]

def check(h,w,island_num):
    assert S[h][w]
    block[h][w]=island_num
    if S[h-1][w] and block[h-1][w]==-1:
        check(h-1,w,island_num)
    if S[h+1][w] and block[h+1][w]==-1:
        check(h+1,w,island_num)
    if S[h][w-1] and block[h][w-1]==-1:
        check(h,w-1,island_num)
    if S[h][w+1] and block[h][w+1]==-1:
        check(h,w+1,island_num)

block=[]
for i in range(H+4):
    block.append([-1 for j in range(W+4)])

island_num=0

for h in range(H+4):
    for w in range(W+4):
        if S[h][w] and block[h][w]==-1:
            check(h,w,island_num)
            island_num+=1


neighbor={}
for island in range(island_num):
    neighbor[island]=set()


for h in range(2,H+2):
    for w in range(2,W+2):
        if block[h][w]!=-1:
            for y in range(h-2,h+3):
                for x in range(w-2, w+3):
                    if block[y][x]!=-1 and block[h][w]!=block[y][x]:
                        neighbor[block[h][w]].add(block[y][x])


start=block[Ch][Cw]
goal=block[Dh][Dw]
assert start!=-1
assert goal!=-1



dist=[10**10 for i in range(island_num)]
dist[start]=0

nexts=[start]
while len(nexts)!=0:
    for n in nexts:
        _nexts=[]
        for neigh in neighbor[n]:
            assert neigh!=-1
            if dist[neigh]>dist[n]+1:
                _nexts.append(neigh)
                dist[neigh]=dist[n]+1
        nexts=set(_nexts)

if dist[goal]==10**10:
    print(-1)
    assert dist[goal]=-1
else:
    print(dist[goal])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(H, W, Ch, Cw, Dh, Dw, data):
    data = data.reshape(-1)
    visited = np.zeros(data.shape)
    distance = np.zeros(data.shape, dtype=np.int16)
    jump = np.zeros(data.shape, dtype=np.int16)
    from collections import deque

    HEIGHT = H + 4
    WIDTH = W + 4
    start = (Ch + 1) * WIDTH + (Cw + 1)
    goal = (Dh + 1) * WIDTH + (Dw + 1)
    q = deque()
    q.append(start)

    currentDistance = 0
    while True:
        while q:
            p = q.pop()
            if visited[p]:
                continue
            if p == goal:
                return currentDistance
            distance[p] = currentDistance
            for dx in [-2, -1, 0, +1, +2]:
                for dy in [-WIDTH * 2, -WIDTH, 0, WIDTH, WIDTH * 2]:
                    jump[p + dx + dy] = currentDistance + 1
            visited[p] = 1
            for d in [-1, +1, -WIDTH, +WIDTH]:
                if data[p + d]:
                    q.append(p + d)

        # no continuous cell
        for i in range(HEIGHT * WIDTH):
            if not data[i]:
                continue
            if visited[i]:
                continue
            # not visited vacant cell
            if jump[i] > 0:
                q.append(i)
        currentDistance += 1
        if not q:
            return -1

    # print(distance)
    # print(visited.reshape((H+4, -1)))


def main():
    global data
    # parse input
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    data = np.array(list(read()) + [0])
    data = np.equal(data, 46).reshape((H, W + 1))
    D = np.zeros((H + 4, W + 4), dtype=np.int8)
    D[2:2+H, 2:2+W+1] = data
    # print(data)
    # print(D)
    print(solve(H, W, Ch, Cw, Dh, Dw, D))


# tests
T1 = """
4 4
1 1
4 4
..#.
..#.
.#..
.#..
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1
"""

T2 = """
4 4
1 4
4 1
.##.
####
####
.##.
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
-1
"""

T3 = """
4 4
2 2
3 3
....
....
....
....
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
0
"""

T4 = """
4 5
1 2
2 5
#.###
####.
#..##
#..##
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
2
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd,deque as dq
import sys
inf=100000000
input=sys.stdin.readline
n,m=map(int,input().split())
cx,cy=map(int,input().split())
cx-=1
cy-=1
dx,dy=map(int,input().split())
dx-=1
dy-=1
ll=[]
for i in range(n):
    ll.append(input().split()[0])
q=dq([cx*m+cy])
dis=[inf]*(n*m+1)
xx=[0,-1,0,1]
yy=[1,0,-1,0]
des=dx*m+dy
d=dd(list)
vis=[[0]*m for i in range(n)]
for x in range(n):
    for y in range(m):
        for i in range(4):
            X=x+xx[i]
            Y=y+yy[i]
            if(X<n and X>=0 and Y<m and Y>=0 and ll[X][Y]=='.' and vis[X][Y]==0):
                d[x*m+y].append((X*m+Y,0))
                vis[X][Y]=1
        X=x-2
        Y=Y-2
        for i in range(5):
            for j in range(5):
                if(X+i>=0 and X+i<n and Y+j>=0 and Y+j<m and ll[X+i][Y+j]=='.' and vis[X][Y]==0):
                    d[x*m+y].append(((X+i)*m+Y+j,1))
dis[q[0]]=0
lol=0
while q:
    curr=q.pop()
    if(curr==des):
        print(dis[curr])
        lol=1
        break
    for j in d[curr]:
        temp,val=j
        if(dis[temp]>dis[curr]+val):
            dis[temp]=dis[curr]+val
            if(val==0):
                q.append(temp)
            else:
                q.appendleft(temp)
if(lol==0):
    print(-1)

Submission status: Runtime Error

Solution code:
import collections
import threading

h, w = map(int, input().split())
src_y, src_x = map(int, input().split())
dst_y, dst_x = map(int, input().split())
src_y -= 1
dst_y -= 1
src_x -= 1
dst_x -= 1
grid = [input() for _ in range(h)]

UNDEF = -1
colors = [[UNDEF] * w for _ in range(h)]


def paint(grid, i, j, colors, color):
    q = collections.deque()
    colors[i][j] = color
    q.append((i, j))
    while q:
        i, j = q.popleft()

        for ii, jj in (
            (i - 1, j),
            (i, j - 1),
            (i, j + 1),
            (i + 1, j)
        ):
            if 0 <= ii < h and 0 <= jj < w and colors[ii][jj] == UNDEF and grid[ii][jj] == '.':
                colors[ii][jj] = color
                q.append((ii, jj))

color = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] == '.' and colors[i][j] == UNDEF:
            paint(grid, i, j, colors, color)
            color += 1


g = [set() for _ in range(color)]
for i in range(h):
    for j in range(w):
        if colors[i][j] != UNDEF:
            for ii in range(i - 2, i + 3):
                for jj in range(j - 2, j + 3):
                    if 0 <= ii < h and 0 <= jj < w and colors[ii][jj] != colors[i][j] and colors[ii][jj] != UNDEF:
                        c1 = colors[ii][jj]
                        c2 = colors[i][j]
                        assert c1 != UNDEF and c2 != UNDEF
                        g[c1].add(c2)
                        g[c2].add(c1)

q = collections.deque()
src_color = colors[src_y][src_x]
dst_color = colors[dst_y][dst_x]
q.append((src_color, 0))
vis = [0] * len(colors)
vis[src_color] = 1
ans = -1
while q:
    color, dist = q.popleft()
    if color == dst_color:
        ans = dist
        break
    for other in g[color]:
        if not vis[other]:
            q.append((other, dist + 1))
            vis[other] = 1

print(ans)

Submission status: Runtime Error

Solution code:
# r,c,m = list(map(int,input().split()))
# arr = []
# for i in range(m):
#     arr.append(list(map(int,input().split())))

n,m = list(map(int,input().split()))
xs,ys = list(map(int,input().split()))
xd,yd = list(map(int,input().split()))
xs-=1
ys-=1
xd-=1
yd-=1
dr = [(0,1),(0,2),(0,-1),(0,-2),
      (1, 1), (1, 2), (1, -1), (1, -2),
      (2, 1), (2, 2), (2, -1), (2, -2),
      (-1, 1), (-1, 2), (-1, -1), (-1, -2),
      (-2, 1), (-2, 2), (-2, -1), (-2, -2),
      (1,0), (2,0), (-1,0), (-2,0)]
dx = [1,-1,0,0]
dy = [0,0,-1,1]
mat = []
for i in range(n):
    s = input()
    s = list(s)
    mat.append(s)

q = [[xs,ys,0]]
vis = [[0 for i in range(m)]for j in range(m)]

ans = 10**10
while q!=[]:
    x,y,d = q[0]
    q.pop(0)
    vis[x][y] = 1
    for i in range(4):
        nx,ny = x+dx[i],y+dy[i]
        if nx>=0 and nx<n and ny>=0 and ny<m:
            if vis[nx][ny]==0 and mat[nx][ny]!='#':
                q.append([nx,ny,d])
                vis[nx][ny] = 1
    
    for i in dr:
        dxp,dyp = i[0],i[1]
        nx = x+dxp
        ny = y+dyp
        if nx >= 0 and nx < n and ny >= 0 and ny < m:
            if vis[nx][ny] == 0 and mat[nx][ny] != '#':
                q.append([nx, ny, d+1])
    if x==xd and y==yd:
        ans = min(ans,d)

if ans==10**10 or mat[xs][ys]=='#' or mat[xd][yd]=='#':
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
import copy
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]


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

tree = Uf(h*w)
for i in range(h):
    for j in range(w):
        if A[i][j] == "#":
            continue
        if i > 0 and A[i-1][j] == ".":
            tree.unite(w*i+j, w*(i-1)+j)
        if i < h-1 and A[i+1][j] == ".":
            tree.unite(w*i+j, w*(i+1)+j)
        if j > 0 and A[i][j-1] == ".":
            tree.unite(w*i+j, w*i+(j-1))
        if j < w-1 and A[i][j+1] == ".":
            tree.unite(w*i+j, w*i+(j+1))

# print(tree.p)

par_list = set()
for i in range(h):
    for j in range(w):
        if A[i][j] == ".":
            par_list.add(tree.p[w*i+j])

# print(par_list)

node = dict()
for i, e in enumerate(par_list):
    node[e] = i

# print(node)

edge_list = set()
for i in range(h):
    for j in range(w):
        if A[i][j] == ".":
            for a in range(max(0, i-2), min(h, i+2)):
                for b in range(max(0, j - 2), min(h, j + 2)):
                    if A[a][b] == "." and tree.p[w*i+j] != tree.p[w*a+b]:
                        edge_list.add((node[tree.p[w*i+j]], node[tree.p[w*a+b]]))
                        edge_list.add((node[tree.p[w*a + b]], node[tree.p[w*i + j]]))

start = node[tree.p[w*(ch-1) + cw-1]]
goal = node[tree.p[w*(dh-1) + dw-1]]

g = [[] for i in range(len(node))]
for e in edge_list:
    g[e[0]].append(e[1])

# print(g)

que = deque([(start, 0)])
seen = set()
seen.add(start)
while que:
    cur, time = que.popleft()
    if cur == goal:
        print(cur)
        exit()
    for nxt in g[cur]:
        if nxt not in seen:
            seen.add(nxt)
            que.append((nxt, time+1))

print(-1)

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
maze = [input() for _ in range(h)]

# 魔法使わない
dx1 = [1, 0, -1, 0]
dy1 = [0, 1, 0, -1]

# 魔法使う
dx2 = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]
dy2 = [2, 2, 2, 2, 2, 1, 1, 1, 0, 0, -1, -1, -1, -2, -2, -2, -2, -2]

mp = [[10**9 for _ in range(w)] for _ in range(h)]

walk_visited = [[False for _ in range(w)] for _ in range(h)]

def bfs(x, y):
    for dx, dy in zip(dx1, dy1):
        nx, ny = x+dx, y+dy
        if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] == ".":
            mp[ny][nx] = min(mp[ny][nx], mp[y][x])

    for dx, dy in zip(dx2, dy2):
        nx, ny = x+dx, y+dy
        if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] == ".":
            mp[ny][nx] = min(mp[ny][nx], mp[y][x]+1)

    for dx, dy in zip(dx1, dy1):
        nx, ny = x+dx, y+dy
        if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] == ".":
            if mp[ny][nx] >= mp[y][x] and not walk_visited[y][x]:
                walk_visited[ny][nx] = True
                bfs(nx, ny)
    
    for dx, dy in zip(dx2, dy2):
        nx, ny = x+dx, y+dy
        if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] == ".":
            if mp[ny][nx] > mp[y][x]:
                bfs(nx, ny)
    

mp[ch-1][cw-1] = 0
bfs(cw-1, ch-1)
if mp[dh-1][dw-1] == 10**9:
    mp[dh-1][dw-1] = -1
print(mp[dh-1][dw-1])

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    H,W = LI()
    ch, cw = _LI()
    dh, dw = _LI()
    m = [[0] * W for _ in range(W)]
    for i in range(H):
        s = SI()
        for j in range(W):
            if s[j] == "#":
                m[i][j] = -1

    z = [(ch,cw,1)]
    while z:
        x,y,c = z.pop()
        if m[x][y]: continue
        q = collections.deque()
        q.append((x,y))
        m[x][y] = c
        r = [(x,y)]
        while q:
            x,y = q.popleft()
            if x == dh and y == dw:
                print(c-1)
                return
            for dx,dy in ((0,1),(1,0),(-1,0),(0,-1)):
                nx = x + dx
                ny = y + dy
                if not(0<= nx < H and 0<= ny < W): continue
                if m[nx][ny]: continue
                m[nx][ny] = c
                q.append((nx,ny))
                r.append((nx,ny))
        for x,y in r:
            for dx in range(-2,3):
                nx = x + dx
                if not(0<= nx < H): continue
                for dy in range(-2,3):
                    ny = y + dy
                    if not(0<= ny < W): continue
                    if m[nx][ny]: continue
                    z.append((nx,ny,c+1))
    print(-1)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import collections
import threading
sys.setrecursionlimit(1000 * 1000 + 100)

h, w = map(int, input().split())
src_y, src_x = map(int, input().split())
dst_y, dst_x = map(int, input().split())
src_y -= 1
dst_y -= 1
src_x -= 1
dst_x -= 1
grid = [input() for _ in range(h)]

UNDEF = -1
colors = [[UNDEF] * w for _ in range(h)]


def paint(grid, i, j, colors, color):
    colors[i][j] = color
    for ii, jj in (
        (i - 1, j),
        (i, j - 1),
        (i, j + 1),
        (i + 1, j)
    ):
        if 0 <= ii < h and 0 <= jj < w and colors[ii][jj] == UNDEF and grid[ii][jj] == '.':
            paint(grid, ii, jj, colors, color)

threading.stack_size(2 ** 27)

color = 0
def recurse():
    global color
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '.' and colors[i][j] == UNDEF:
                paint(grid, i, j, colors, color)
                color += 1

t = threading.Thread(target=recurse)
t.start()
t.join()

g = [[0] * color for _ in range(color)]
for i in range(h):
    for j in range(w):
        if colors[i][j] != UNDEF:
            for ii in range(i - 2, i + 3):
                for jj in range(j - 2, j + 3):
                    if 0 <= ii < h and 0 <= jj < w and colors[ii][jj] != colors[i][j] and colors[ii][jj] != UNDEF:
                        c1 = colors[ii][jj]
                        c2 = colors[i][j]
                        assert c1 != UNDEF and c2 != UNDEF
                        g[c1][c2] = 1
                        g[c2][c1] = 1

q = collections.deque()
src_color = colors[src_y][src_x]
dst_color = colors[dst_y][dst_x]
q.append((src_color, 0))
vis = [0] * len(colors)
vis[src_color] = 1
ans = -1
while q:
    color, dist = q.popleft()
    if color == dst_color:
        ans = dist
        break
    for other in range(len(g)):
        if g[color][other] and not vis[other]:
            q.append((other, dist + 1))
            vis[other] = 1

print(ans)

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
cy,cx  = map(int,input().split())
cy -= 1
cx -= 1
dy,dx  = map(int,input().split())
dy -= 1
dx -= 1
S = [list(input()) for i in range(H)]
ans = -1

def moveB(y,x,count):
    global ans
    #print(y,x,dy,dx,ans)
    if(y == dy and x  == dx):
        ans = count
        return
    S[y][x] = "*"
    if(y != 0 and S[y-1][x] == "."):
        moveB(y-1,x,count)
    if(y != H-1 and S[y+1][x] == "."):
        moveB(y+1,x,count)
    if(x != 0 and S[y][x-1] == "."):
        moveB(y,x-1,count)
    if(x != W-1 and S[y][x +1] == "."):
        moveB(y, x +1,count)
        
    if(y != 0 and S[y-1][x] == "#"):
        moveA(y,x,count,-2,0)
        moveA(y,x,count,-2,-1)
        moveA(y,x,count,-2,1)
    if(y != H-1 and S[y+1][x] == "#"):
        moveA(y,x,count,2,0)
        moveA(y,x,count,2,-1)
        moveA(y,x,count,2,1)
    if(x != 0 and S[y][x-1] == "#"):
        moveA(y,x,count,0,-2)
        moveA(y,x,count,-1,-2)
        moveA(y,x,count,1,-2)
    if(x != W-1 and S[y][x +1] == "#"):
        moveA(y,x,count,0,2)
        moveA(y,x,count,-1,2)
        moveA(y,x,count,1,2)
        
def moveA(y,x,count,h,w):
    if(y+h in range(H) and x+w in range(W) and S[y+h][x+w] == "."):
        moveB(y+h,x+w,count+1)
    

moveB(cy,cx,0)


print(ans)

Submission status: Runtime Error

Solution code:
import collections, itertools
H, W, ch, cw, dh, dw, *S = open(0).read().split()
H, W, ch, cw, dh, dw = [int(_) + 1 for _ in [H, W, ch, cw, dh, dw]]
H += 3
W += 3
S = ['#' * W] + ['#' * W] + ['##' + s + '##'
                             for s in S] + ['#' * W] + ['#' * W]
Dist = [[None] * W for _ in range(H)]
Q = collections.deque([(0, ch, cw)])
while Q:
    d, ox, oy = Q.popleft()
    if Dist[ox][oy] is not None:
        continue
    stack = [[ox, oy]]
    warp = set()
    while stack:
        x, y = stack.pop()
        if (x, y) == (dh, dw):
            print(d)
            exit()
        Dist[x][y] = d
        for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            nx, ny = x + dx, y + dy
            if Dist[nx][ny] is None:
                if S[nx][ny] == '.':
                    stack += [[nx, ny]]
                else:
                    warp.add((x, y))
    for x, y in warp:
        for dx, dy in itertools.product(range(-2, 3), repeat=2):
            nx, ny = x + dx, y + dy
            if Dist[nx][ny] is None and S[ox][oy] == '.':
                Q += [(d + 1, nx, ny)]
print(-1)

Submission status: Runtime Error

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_()
    s = ["."*w]*w
    q = deque()
    c = defaultdict(lambda :inf)
    q.append((ch-1, cw-1))
    c[(ch-1,cw-1)] = 0
    while q:
        nh, nw = q.popleft()
        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))
        for i in range(-2, 3):
            i += nh
            for j in range(-2, 3):
                j += nw
                if 0 <= i < h and 0 <= j < w and c[(i, j)] > now + 1 and s[i][j] == ".":
                    c[(i, j)] = now + 1
                    q.append((i, j))
    print(-1 if c[(dh, dw)] == inf else c[(dh, dw)])
    return


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

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit()=10**6=10
h,w=[int(_) for _ in input().split()]

ch,cw=[int(_) for _ in input().split()]
dh,dw=[int(_) for _ in input().split()]

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

t=[[-1 for i in range(w)]for j in range(h)]

def wfs(i,j,d):
    for k,l in [[0,1],[0,-1],[1,0],[-1,0]]:
        if 0<=i+k<h and 0<=j+l<w and s[i+k][j+l]=="." and t[i+k][j+l]<0:
            t[i+k][j+l]=d
            wfs(i+k,j+l,d)
    for k in range(-2,3):
        for l in range(-2,3):
            if 0<=i+k<h and 0<=j+l<w and s[i+k][j+l]=="." and t[i+k][j+l]<0:
                t[i+k][j+l]=d+1
                wfs(i+k,j+l,d+1)

t[ch-1][cw-1]=0
wfs(ch-1,cw-1,0)
print(t[dh-1][dw-1])

# print(t)

Submission status: Runtime Error

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
#from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7


h,w=mdata()
ch,cw=mdata()
dh,dw=mdata()
ch-=1
dh-=1
cw-=1
dw-=1
if ch==dh and cw==dw:
    out(0)
    exit()
S=[data().split() for i in range(h)]
stack=[(dh,dw)]
steps=[(0,1),(1,0),(-1,0),(0,-1)]
moves={(dh,dw)}
while stack:
    a,b=stack.pop()
    for i,j in steps:
        if 0<=a+i<h and 0<=b+j<w and S[a+i][b+j]=='.' and (a+i,b+j) not in moves:
            moves.add((a+i,b+j))
            stack.append((a+i,b+j))
if (ch,cw) in moves:
    out(0)
    exit()
moves1={(ch,cw)}
stack=[(ch,cw)]
cnt=0
while stack:
    stack1=[]
    cnt+=1
    while stack:
        a, b = stack.pop()
        for i in range(-2,3):
            for j in range(-2,3):
                if 0 <= a + i < h and 0 <= b + j < w and S[a + i][b + j] == '.' and ((a + i, b + j) not in moves1):
                    moves1.add((a + i, b + j))
                    stack1.append((a + i, b + j))
                    if (a + i, b + j) in moves:
                        out(cnt)
                        exit()
    stack=stack1
out(-1)

Submission status: Runtime Error

Solution code:
# r,c,m = list(map(int,input().split()))
# arr = []
# for i in range(m):
#     arr.append(list(map(int,input().split())))

n,m = list(map(int,input().split()))
xs,ys = list(map(int,input().split()))
xd,yd = list(map(int,input().split()))
xs-=1
ys-=1
xd-=1
yd-=1
dr = [(0,1),(0,2),(0,-1),(0,-2),
      (1, 1), (1, 2), (1, -1), (1, -2),
      (2, 1), (2, 2), (2, -1), (2, -2),
      (-1, 1), (-1, 2), (-1, -1), (-1, -2),
      (-2, 1), (-2, 2), (-2, -1), (-2, -2),
      (1,0), (2,0), (-1,0), (-2,0)]
dx = [1,-1,0,0]
dy = [0,0,-1,1]
mat = []
for i in range(n):
    s = input()
    s = list(s)
    mat.append(s)

q = [[xs,ys,0]]
vis = [[0 for i in range(m)]for j in range(m)]

ans = 10**10
while q!=[]:
    x,y,d = q[0]
    q.pop(0)
    vis[x][y] = 1
    for i in range(4):
        nx,ny = x+dx[i],y+dy[i]
        if nx>=0 and nx<n and ny>=0 and ny<m:
            if vis[nx][ny]==0 and mat[nx][ny]!='#':
                q.append([nx,ny,d])
                vis[nx][ny] = 1
    
    for i in dr:
        dxp,dyp = i[0],i[1]
        nx = x+dxp
        ny = y+dyp
        if nx >= 0 and nx < n and ny >= 0 and ny < m:
            if vis[nx][ny] == 0 and mat[nx][ny] != '#':
                q.append([nx, ny, d+1])
    if x==xd and y==yd:
        ans = min(ans,d)
if ans==10**10:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:


h,w=[int(_) for _ in input().split()]

ch,cw=[int(_) for _ in input().split()]
dh,dw=[int(_) for _ in input().split()]

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

t=[[-1 for i in range(w)]for j in range(h)]

def wfs(i,j,d):
    for k,l in [[0,1],[0,-1],[1,0],[-1,0]]:
        if 0<=i+k<h and 0<=j+l<w and s[i+k][j+l]=="." and t[i+k][j+l]<0:
            t[i+k][j+l]=d
            wfs(i+k,j+l,d)
    for k in range(-2,3):
        for l in range(-2,3):
            if 0<=i+k<h and 0<=j+l<w and s[i+k][j+l]=="." and t[i+k][j+l]<0:
                t[i+k][j+l]=d+1
                wfs(i+k,j+l,d+1)

t[ch-1][cw-1]=0
wfs(ch-1,cw-1,0)
print(t[dh-1][dw-1])

# print(t)

Submission status: Runtime Error

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([1000000000]*w)
#print(ans)

def solve(nowx, nowy, length):
    #print(nowx, nowy, length)
    if(ans[nowx][nowy] <= length):return 0
    ans[nowx][nowy] = length
    for i in range(5):
        for j in range(5):
            nextx = nowx+i-2
            nexty = nowy+j-2
            if(nextx < 0 or nextx >= h):continue
            if(nexty < 0 or nexty >= w):continue

            if(data[nextx][nexty] == "."):
                if(abs(i-2)+abs(j-2) <= 1):
                    solve(nextx, nexty, length)

                else:
                    solve(nextx, nexty, length+1)
    return 0

#print(c1, c2)
solve(c1-1, c2-1, 0)

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