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: Accepted

Solution code:
from itertools import combinations
import sys
from collections import defaultdict, deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
DDX = (-1, 0, 1, 0, -1, -1, 1, 1)
DDY = (0, 1, 0, -1, -1, 1, -1, 1)
DX = DDX[:4]
DY = DDY[:4]


H, W = map(int, input().split())
Cx, Cy = map(int, input().split())
Dx, Dy = map(int, input().split())

grid = ["#" * (W + 2)]
for _ in range(H):
    inp = "#" + input().strip() + "#"
    grid.append(inp)
grid.append("#" * (W + 2))


area = [[-1] * (W + 2) for _ in range(H + 2)]
cnt = 0
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if grid[i][j] == "#" or area[i][j] != -1:
            continue
        cnt += 1
        node = [(i, j)]
        area[i][j] = cnt
        while node:
            x, y = node.pop()
            for dx, dy in zip(DX, DY):
                nx = x + dx
                ny = y + dy
                if grid[nx][ny] == "#":
                    continue
                if area[nx][ny] == -1:
                    area[nx][ny] = cnt
                    node.append((nx, ny))


used = defaultdict(int)

edge = [[] for _ in range(cnt + 1)]
for i in range(1, H + 1):
    for j in range(1, W + 1):
        memo = set()
        if grid[i][j] == ".":
            memo.add(area[i][j])
        for dx, dy in zip(DDX, DDY):
            if area[i + dx][j + dy] == -1:
                continue
            memo.add(area[i + dx][j + dy])
        for x, y in combinations(memo, 2):
            if x > y:
                x, y = y, x
            if used[(x, y)]:
                continue
            edge[x].append(y)
            edge[y].append(x)
            used[(x, y)] = 1


dist = [-1] * (cnt + 1)
ci = area[Cx][Cy]
di = area[Dx][Dy]
dist[ci] = 0
node = deque([ci])
while node:
    s = node.popleft()
    for t in edge[s]:
        if dist[t] != -1:
            continue
        dist[t] = dist[s] + 1
        node.append(t)

print(dist[di])

Submission status: Accepted

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
ch,cw = map(int, input().split())
ch,cw = ch-1, cw-1
dh,dw = map(int, input().split())
dh,dw = dh-1,dw-1
s = [list(map(lambda x: x==".", input())) for i in range(h)]

inf = 2**32-1
count = [[inf]*w for i in range(h)]

from collections import deque
que = deque()
que.append((ch,cw,0))

dxdy = [(0,1),(1,0),(0,-1),(-1,0)]

while que:
    x,y,c = que.popleft()
    if count[x][y] <= c:
        continue
    count[x][y] = c
    kabe = False
    for dx,dy in dxdy:
        nx, ny = x+dx, y+dy
        if not (0<=nx<h and 0<=ny<w):
            continue
        if s[nx][ny]:
            que.appendleft((nx,ny,c))
        else:
            kabe = True
    if not kabe:
        continue
    nc = c+1
    for kx in range(-2,3):
        for ky in range(-2,3):
            nx = x+kx
            ny = y+ky
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > nc:
                que.append((nx,ny,nc))

ans = count[dh][dw]
if ans == inf:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
import collections
import itertools

h, w = map(int, input().split())
sy, sx = map(lambda x:int(x) - 1, input().split())
gy, gx = map(lambda x:int(x) - 1, input().split())
maze = [list(input()) for _ in range(h)]

seen = [[-1] * w for _ in range(h)]
seen[sy][sx] = 0
que = collections.deque()
que.append((sy, sx))
tmp2 = [(sy, sx)]
cnt = 0
while True:
    tmp1 = []
    for sy, sx in tmp2:
        if maze[sy][sx] == ".":
            que.append((sy,sx))
            tmp1.append((sy, sx))
            while que:
                py, px = que.popleft()
                for dy, dx in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                    ny = py + dy
                    nx = px + dx
                    if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] == "." and seen[ny][nx] == -1:
                        seen[ny][nx] = cnt
                        que.append((ny, nx))
                        tmp1.append((ny, nx))
                        maze[sy][sx] = "#"
                        
    if seen[gy][gx] != -1:
        break

    flag = True
    d = [-2, -1, 0, 1, 2]
    tmp2 = []
    for py, px in tmp1:
        for i in range(5):
            for j in range(5):
                ny = py + d[i]
                nx = px + d[j]
                if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] == "." and seen[ny][nx] == -1:
                    seen[ny][nx] = cnt + 1
                    que.append((ny, nx))
                    flag = False
                    tmp2.append((ny, nx))
    cnt += 1
    if flag:
        break
    if seen[gy][gx] != -1:
        break

print(seen[gy][gx])

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
ch,cw = map(int, input().split())
ch,cw = ch-1, cw-1
dh,dw = map(int, input().split())
dh,dw = dh-1,dw-1
s = [list(map(lambda x: x==".", input())) for i in range(h)]

inf = 2**32-1
count = [[inf]*w for i in range(h)]

from collections import deque
que = deque()
que.append((ch,cw,0))

dxdy = [(-1,0),(0,1),(1,0),(0,-1)]
dxdy1 = [(-1,-1),(-1,-2),(-2,-1),(-2,-2)]
dxdy2 = [(-1,1),(-1,2),(-2,1),(-2,2)]
dxdy3 = [(1,1),(1,2),(2,1),(2,2)]
dxdy4 = [(1,-1),(1,-2),(2,-1),(2,-2)]
while que:
    x,y,c = que.popleft()
    if count[x][y] <= c:
        continue
    count[x][y] = c
    state = [False]*4
    for i, (dx,dy) in enumerate(dxdy):
        nx, ny = x+dx, y+dy
        if not (0<=nx<h and 0<=ny<w):
            continue
        if s[nx][ny]:
            que.appendleft((nx,ny,c))
        else:
            state[i] = True
            nx,ny = nx+dx, ny+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))

    if state[-1] and state[0]:
        for dx,dy in dxdy1:
            nx, ny = x+dx, y+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))

    if state[0] and state[1]:
        for dx,dy in dxdy2:
            nx, ny = x+dx, y+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))
    if state[1] and state[2]:
        for dx,dy in dxdy3:
            nx, ny = x+dx, y+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))
    if state[2] and state[3]:
        for dx,dy in dxdy4:
            nx, ny = x+dx, y+dy
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > c+1:
                que.append((nx,ny,c+1))

ans = count[dh][dw]
if ans == inf:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
#abc176-d
import sys,math,collections,itertools
input = sys.stdin.readline
 
H,W=list(map(int,input().split()))
Ch,Cw=list(map(int,input().split()))
Dh,Dw=list(map(int,input().split()))
s=[ input().rstrip() for _ in range(H)]
 
#DPで遷移が2種類　初期値をinf として、現在値より小さければ遷移可能とする
dp = [ [float('inf') ]*W  for _ in range(H)]
 
q = collections.deque([])
q.append((Ch-1,Cw-1))
dp[Ch-1][Cw-1]=0
while q:
    visit = []
    while q:
        nh,nw = q.popleft()
        visit.append((nh,nw))
        #徒歩での遷移
        if nh>0 and s[nh-1][nw] =='.' and dp[nh-1][nw]>dp[nh][nw]:
            q.append((nh-1,nw))
            dp[nh-1][nw] = dp[nh][nw]
        if nh<H-1 and s[nh+1][nw] =='.' and dp[nh+1][nw]>dp[nh][nw]:
            q.append((nh+1,nw))
            dp[nh+1][nw] = dp[nh][nw]
        if nw>0 and s[nh][nw-1] =='.' and dp[nh][nw-1]>dp[nh][nw]:
            q.append((nh,nw-1))
            dp[nh][nw-1] = dp[nh][nw]
        if nw<W-1 and s[nh][nw+1] =='.' and dp[nh][nw+1]>dp[nh][nw]:
            q.append((nh,nw+1))
            dp[nh][nw+1] = dp[nh][nw]
    while visit:
    #ワープで遷移
        nh,nw = visit.pop()
        for ih in range(-2,3,1):
            for iw in range(-2,3,1):
                if (0<= nh+ih<=H-1) and (0<=nw+iw<=W-1):
                    if s[nh+ih][nw+iw] =='.' and dp[nh+ih][nw+iw]>dp[nh][nw]:
                        q.append((nh+ih,nw+iw))
                        dp[nh+ih][nw+iw] = dp[nh][nw]+1
     
 
ans = dp[Dh-1][Dw-1]
print(-1 if ans==float('inf') else ans)

Submission status: Accepted

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools
from math import *
from bisect import *
from heapq import *
from collections import *
import queue

def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

H, W = In.ints()

grid = [["." for j in range(W)] for i in range(H)]

C = In.ints()
C = (C[0]-1, C[1]-1)
D = In.ints()
D = (D[0]-1, D[1]-1)

for i in range(H):
    s = In.str()

    for j in range(W):
        grid[i][j] = s[j]    

#print(grid)

moves = [[0,1], [0,-1], [1,0], [-1,0]]
setnext = set()
setnow = set([(C[0], C[1])])
quenow = deque([(C[0], C[1])])

ans = 0
found = False
hadOne = True

while hadOne:
    hadOne=False
    while len(quenow)>0:
        hadOne=True
        now = quenow.popleft()

        for i in range(-2,3):
            for j in range(-2, 3):
                nex = (now[0]+i, now[1]+j)

                if 0<=nex[0]<H and 0<=nex[1]<W and grid[nex[0]][nex[1]]==".":
                    if nex not in setnow and nex not in setnext:
                        setnext.add(nex)                    

        for m in moves:
            nex = (now[0]+m[0], now[1]+m[1])

            if nex == D:
                found = True
                break

            if 0<=nex[0]<H and 0<=nex[1]<W and grid[nex[0]][nex[1]] == "." and nex not in setnow:
                quenow.append(nex)
                setnow.add(nex)
        
        if found:
            break
    
    if found:
        break
    
    ans += 1

    for el in setnext:
        if el==D:
            found=True
            break
        if el not in setnow:            
            setnow.add(el)
            quenow.append(el)
    
    setnext.clear()
    
    if found:
        break


if found:
    Out.int(ans)
else:
    Out.int(-1)
######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
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 = list(data.reshape(-1))
    HEIGHT = H + 4
    WIDTH = W + 4
    N = HEIGHT * WIDTH
    visited = [0] * N
    distance = [0] * N
    jump = [0] * N

    start = (Ch + 1) * WIDTH + (Cw + 1)
    goal = (Dh + 1) * WIDTH + (Dw + 1)
    q = []
    nextJump = set()
    q.append(start)

    currentDistance = 0
    while True:
        while q:
            p = q.pop()
            if p == goal:
                return currentDistance
            if visited[p]:
                continue
            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
                    nextJump.add(p + dx + dy)
            visited[p] = 1
            for d in [-1, +1, -WIDTH, +WIDTH]:
                if data[p + d] and not visited[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)
        for p in nextJump:
            if not data[p]:
                continue
            if visited[p]:
                continue
            q.append(p)

        currentDistance += 1
        nextJump = set()
        if not q:
            return -1

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


def main():
    # parse input
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    D = [0] * ((H + 4) * (W + 4))
    for i in range(H):
        S = input().strip()
        for j in range(W):
            D[(i + 2) * (W + 4) + (j + 2)] = 1 if S[j] == ord(b".") else 0
    # print(D)
    # for i in range(H + 4):
    #     print(D[i * (H + 4): i * (H + 4) + (W + 4)])
    # data = np.array(list(read().strip()) + [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: Accepted

Solution code:
from collections import deque
from itertools import product

H, W =map(int,input().split())
C=tuple(map(lambda x: int(x)-1,input().split()))
D=tuple(map(lambda x: int(x)-1,input().split()))
S=[input().strip("¥n") for i in range(H)]

mag=(-2, -1, 0, 1, 2)

dist=[[-1]*W for i in range(H)]

qu=deque([(C[0], C[1])])
dist[C[0]][C[1]]=0

while(len(qu)>0):
  qut=deque()
  while(len(qu)>0):
    v=qu.popleft()
    qut.append(v)
    for h,w in ((-1,0),(1,0),(0,-1),(0,1)):
      nvh=v[0]+h
      nvw=v[1]+w
      if 0<=nvh<H and 0<=nvw<W and dist[nvh][nvw]==-1 and S[nvh][nvw]==".":
        dist[nvh][nvw]=dist[v[0]][v[1]]
        qu.append((nvh,nvw))
  while(len(qut)>0):
    v=qut.popleft()
    for h,w in product(mag,repeat=2):
      if h==0 and w==0:
        continue
      nvh=v[0]+h
      nvw=v[1]+w
      if 0<=nvh<H and 0<=nvw<W and S[nvh][nvw]==".":
        if dist[nvh][nvw]==-1:
          dist[nvh][nvw]=dist[v[0]][v[1]]+1
          qu.append((nvh,nvw))
print(dist[D[0]][D[1]])

Submission status: Accepted

Solution code:
import sys


def _s(): return sys.stdin.readline().strip()


def _ia(): return map(int, sys.stdin.readline().strip().split())


def walk(s, w1, h1, x, y, cur, v1, v2):
    if s[y][x] is not None:
        return
    s[y][x] = cur
    v1.add((x, y))
    for hi in range(max(0, y - 2), min(h1, y + 2) + 1):
        for wi in range(max(0, x - 2), min(w1, x + 2) + 1):
            if s[hi][wi] is None:
                v2.add((wi, hi))

    if x > 0:
        walk(s, w1, h1, x-1, y, cur, v1, v2)
    if x < w1:
        walk(s, w1, h1, x+1, y, cur, v1, v2)
    if y > 0:
        walk(s, w1, h1, x, y-1, cur, v1, v2)
    if y < h1:
        walk(s, w1, h1, x, y+1, cur, v1, v2)


def main():
    h, w = _ia()
    sh, sw = map(lambda x: x-1, _ia())
    gh, gw = map(lambda x: x-1, _ia())
    s = [[0]*w for _ in range(h)]
    for hi in range(h):
        for wi, c in enumerate(_s()):
            if c == '.':
                s[hi][wi] = None
            else:
                s[hi][wi] = -1

    p = [(sw, sh)]
    c = 0
    h1, w1 = h-1, w-1
    while len(p) > 0:
        v1 = set()
        v2 = set()
        for pi in p:
            walk(s, w1, h1, *pi, c, v1, v2)
        p = v2 - v1
        c += 1
    ans = s[gh][gw]
    return ans if ans is not None else -1


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
h, w = [int(i) for i in input().split()]
ch, cw = [int(i) for i in input().split()]
ch -= 1
cw -= 1
dh, dw = [int(i) for i in input().split()]
dh -= 1
dw -= 1

loc = []
move = []
checked = []
magicchecked = []
for i in range(h):
    line = input()
    loc.append([j for j in line])
    move.append([-1 for j in line])
    checked.append([0 for j in line])
    magicchecked.append([0 for j in line])

move[ch][cw] = 0
cur = 0
walk = [(ch, cw)]
walkhistory = []
magic = []
while len(walk) > 0:
    node = walk.pop()
    walkhistory.append(node)
    checked[node[0]][node[1]] = 1
    if node[0] - 1 >= 0 and loc[node[0] - 1][node[1]] != "#" and checked[node[0] - 1][node[1]] == 0:
        walk.append((node[0] - 1, node[1]))
    if node[1] - 1 >= 0 and loc[node[0]][node[1] - 1] != "#" and checked[node[0]][node[1] - 1] == 0:
        walk.append((node[0], node[1] - 1))
    if node[0] + 1 < h and loc[node[0] + 1][node[1]] != "#" and checked[node[0] + 1][node[1]] == 0:
        walk.append((node[0] + 1, node[1]))
    if node[1] + 1 < w and loc[node[0]][node[1] + 1] != "#" and checked[node[0]][node[1] + 1] == 0:
        walk.append((node[0], node[1] + 1))
    move[node[0]][node[1]] = cur
    i = node[0]
    j = node[1]

for node in walkhistory:
    i = node[0]
    j = node[1]
    for k in range(-2, 3):
        for l in range(-2, 3):
            if i + k >= 0 and i + k < h and j + l >= 0 and j + l < w \
            and loc[i + k][j + l] == "." and checked[i + k][j + l] == 0 and magicchecked[i + k][j + l] == 0:
                magicchecked[i + k][j + l] = 1
                magic.append((i + k, j + l))

cur += 1

while magic:
    walk = magic[:]
    magic = []
    walkhistory = []

    while len(walk) > 0:
        node = walk.pop()
        walkhistory.append(node)
        checked[node[0]][node[1]] = 1
        if node[0] - 1 >= 0 and loc[node[0] - 1][node[1]] != "#" and checked[node[0] - 1][node[1]] == 0:
            walk.append((node[0] - 1, node[1]))
        if node[1] - 1 >= 0 and loc[node[0]][node[1] - 1] != "#" and checked[node[0]][node[1] - 1] == 0:
            walk.append((node[0], node[1] - 1))
        if node[0] + 1 < h and loc[node[0] + 1][node[1]] != "#" and checked[node[0] + 1][node[1]] == 0:
            walk.append((node[0] + 1, node[1]))
        if node[1] + 1 < w and loc[node[0]][node[1] + 1] != "#" and checked[node[0]][node[1] + 1] == 0:
            walk.append((node[0], node[1] + 1))
        move[node[0]][node[1]] = cur
        i = node[0]
        j = node[1]

    for node in walkhistory:
        i = node[0]
        j = node[1]
        for k in range(-2, 3):
            for l in range(-2, 3):
                if i + k >= 0 and i + k < h and j + l >= 0 and j + l < w \
                and loc[i + k][j + l] == "." and checked[i + k][j + l] == 0 and magicchecked[i + k][j + l] == 0:
                    magicchecked[i + k][j + l] = 1
                    magic.append((i + k, j + l))


    cur += 1

print(move[dh][dw])

Submission status: Accepted

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop
 
# sys.setrecursionlimit(5000)
 
n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]
 
def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)
 
H, W = nn()
Ch, Cw = nn()
Dh, Dw = nn()
S = sm(H)
 
T = [u"#"*(W+4)] * 2
for s in S:
    T.append("##" + s[0] + "##")
T += [u"#"*(W+4)] * 2
 
H += 4
W += 4
Ch += 2 - 1
Cw += 2 - 1
Dh += 2 - 1
Dw += 2 - 1
 
deq1 = deque()
deq1.append((Ch, Cw))
deq2 = deque()
 
cnt = 0
 
memo = array2(H, W, 10**6)
memo[Ch][Cw] = 0
 
memo2 = deque()

for i in range(10**6):
    #pprint(T)
    #pprint(memo)
    #print("-"*30 + "\n")
 
    if len(deq1) == 0:
        print(-1)
        exit(0)
 
    while len(deq1) > 0:
        h, w = deq1.pop()
        memo2.append((h, w))

        if h == Dh and w == Dw:
            print(i)
            exit(0)
 
        def sch(x, y, i):
            #print(x, y, T[x][y])
            if T[x][y] == "." and i < memo[x][y]:
                memo[x][y] = i
                deq1.append((x, y))
 
        sch(h+1, w, i)
        sch(h-1, w, i)
        sch(h, w+1, i)
        sch(h, w-1, i)
 
    #for j in range(H):
    #    for k in range(W):
    while len(memo2) > 0:
        j, k = memo2.pop()
        if memo[j][k] == i:
            for l in range(-2, 3):
                for m in range(-2, 3):
                    if T[j+l][k+m] == "." and i + 1 < memo[j+l][k+m]:
                        memo[j+l][k+m] = i + 1
                        deq2.append((j+l, k+m))
 
    deq1 = deq2
    deq2 = deque()
    memo2 = deque()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
h,w=map(int,input().split())
nx,ny=map(int,input().split())
gx,gy=map(int,input().split())
maze=[input()for i in range(h)]
from heapq import heapify, heappop, heappush
seen=set()
gx-=1;gy-=1
SIZE=h*w
hq=[(nx-1)*w+ny-1]
while hq:
    d=heappop(hq)
    c,d=divmod(d,SIZE)
    x,y=divmod(d,w)
    if w*x +y in seen:continue
    seen.add(w*x +y)
    if x==gx and y==gy:print(c);exit()
    if x and w*(x-1)+y not in seen and maze[x-1 ][y]!=35:
        heappush(hq,(c*SIZE+w*(x-1)+y))
    if y and w*x+y-1 not in seen and maze[x][y-1]!=35:
        heappush(hq,(c*SIZE+w*x+y-1))
    if x+1<h  and w*(x+1)+y not in seen and maze[x+1][y]!=35:
        heappush(hq,(c*SIZE+w*(x+1)+y))
    if y+1<w  and w*x+y+1 not in seen and maze[x][y+1]!=35:
        heappush(hq,(c*SIZE+w*x+y+1))
    for i in range(max(0,x-2),min(h,x+3)):
        for j in range(max(0,y-2),min(w,y+3)):
            if i==x and j==y:continue
            if maze[i][j]==46 and w*i + j not in seen:
                heappush(hq,(c+1)*SIZE+w*i+j)

print(-1)

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    H, W = map(int, input().split())
    sy, sx = (int(x) - 1 for x in input().split())
    gy, gx = (int(x) - 1 for x in input().split())
    G = [input().rstrip() for _ in range(H)]

    dq = deque()
    dq.append((sy, sx, 0))

    INF = H * W + 10

    ctr = [[INF] * W for _ in range(H)]
    ctr[sy][sx] = 0

    while dq:
        y, x, cnt = dq.popleft()
        if cnt > ctr[y][x]:
            continue

        if y > 0 and G[y - 1][x] == '.' and ctr[y - 1][x] > cnt:
            dq.appendleft((y - 1, x, cnt))
            ctr[y - 1][x] = cnt
            if y - 1 == gy and x == gx:
                print(cnt)
                return

        if x > 0 and G[y][x - 1] == '.' and ctr[y][x - 1] > cnt:
            dq.appendleft((y, x - 1, cnt))
            ctr[y][x - 1] = cnt
            if y == gy and x - 1 == gx:
                print(cnt)
                return

        if y < H - 1 and G[y + 1][x] == '.' and ctr[y + 1][x] > cnt:
            dq.appendleft((y + 1, x, cnt))
            ctr[y + 1][x] = cnt
            if y + 1 == gy and x == gx:
                print(cnt)
                return

        if x < W - 1 and G[y][x + 1] == '.' and ctr[y][x + 1] > cnt:
            dq.appendleft((y, x + 1, cnt))
            ctr[y][x + 1] = cnt
            if y == gy and x + 1 == gx:
                print(cnt)
                return

        ncnt = cnt + 1
        for dr in range(-2, 3):
            ny = y + dr
            if ny < 0 or ny >= H:
                continue
            for dc in range(-2, 3):
                nx = x + dc
                if nx < 0 or nx >= W:
                    continue
                if G[ny][nx] == '.' and ctr[ny][nx] > ncnt:
                    dq.append((ny, nx, ncnt))
                    ctr[ny][nx] = ncnt

        if ctr[gy][gx] <= cnt:
            print(cnt)
            return

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

meiro = [ ['#'] * (w+4)]
meiro += [ ['#'] * (w+4)]
meiro += [['#'] * 2 + list(input()) + ['#'] * 2 for _ in range(h)]
meiro += [ ['#'] * (w+4)]
meiro += [ ['#'] * (w+4)]

moved = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def label(row, column):
    meiro[row][column] = num
    for i,j in moved:
        if meiro[row+i][column+j] == '.':
            check.append([row+i, column+j])
            label(row+i, column+j)

row = ch + 1
column = cw + 1

num = 0
check = [[row, column]]
label(row, column)

while True:
    num += 1
    check_copy = copy.deepcopy(check)
    check = []
    for i,j in check_copy:
        for s in range(-2, 3):
            for t in range(-2, 3):
                if meiro[i+s][j+t] == '.':
                    check.append([i+s, j+t])
                    label (i+s,j+t)

    if len(check) == 0:
        break

if meiro[dh+1][dw+1] == '.':
    print(-1)
else:
    print(meiro[dh+1][dw+1])