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:
def examA():
    N, X, T = LI()
    ans = (1 + (N-1)//X)*T
    print(ans)
    return

def examB():
    N = SI()
    s = 0
    for n in N:
        s += int(n)
    if s%9==0:
        ans = "Yes"
    else:
        ans = "No"
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    now = A[0]
    cnt = 0
    for i in range(N):
        if now>A[i]:
            cnt += now-A[i]
        if now<A[i]:
            now = A[i]
    ans = cnt
    print(ans)
    return

def examD():
    def bfs_grid(h, w, s, g, maze):
        distance = [[inf] * w for _ in range(h)]

        def bfsg():
            queue = deque()
            queue.append(s)
            cost = 0
            distance[s[0]][s[1]] = cost
            used = [s]
            while(True):
                while len(queue):
                    y, x = queue.popleft()
                    for i in range(4):
                        nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '#'):
                            if distance[ny][nx] != inf:
                                continue
                            queue.append((ny, nx))
                            distance[ny][nx] = cost
                            used.append((ny,nx))

                #print(used)

                if distance[g[0]][g[1]]==inf:
                    cost += 1
                    used_ne = []
                    for y,x in used:
                        for i in range(5):
                            nx = x + [-2, -1, 0, 1, 2][i]
                            if not 0<=nx<W:
                                continue
                            for j in range(5):
                                ny = y + [-2, -1, 0, 1, 2][j]
                                if not 0<=ny<H:
                                    continue
                                if distance[ny][nx] != inf:
                                    continue
                                if maze[ny][nx]=="#":
                                    continue
                                queue.append((ny,nx))
                                distance[ny][nx] = cost
                                used_ne.append((ny,nx))
                    used = used_ne

                    if not queue:
                        #print(distance)
                        return -1
                    continue

                return cost


            return distance

        return bfsg()
    H, W = LI()
    C = LI()
    D = LI()
    C[0] -= 1; C[1] -= 1
    D[0] -= 1; D[1] -= 1
    S = [SI()for _ in range(H)]
    ans = bfs_grid(H, W, C, D, S)
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
a, b = map(int, input().split())
c, d = map(int, input().split())
a -= 1
b -= 1
c -= 1
d -= 1
s = [list(input()) for i in range(h)]
now = 0
dd = [(-1, 0), (1, 0), (0, 1), (0, -1)]

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            de = deque([(i, j)])
            s[i][j] = now
            while de:
                x, y = de.popleft()
                for p, q in dd:
                    if 0 <= x + p < h and 0 <= y + q < w and s[x + p][y + q] == ".":
                        s[x + p][y + q] = now
                        de.append((x + p, y + q))
            now += 1
st = s[a][b]
en = s[c][d]
es = [set() for i in range(now)]
for i in range(h):
    for j in range(w):
        if s[i][j] != "#":
            for p in range(-2, 3):
                for q in range(-2, 3):
                    if 0 <= i + p < h and 0 <= j + q < w and s[i + p][j + q] != "#":
                        es[s[i][j]].add(s[i + p][j + q])
                        es[s[i + p][j + q]].add(s[i][j])
from heapq import heappush, heapify, heappop


def dijkstra(s):
    INF = 1 << 32
    d = [INF] * now  # 頂点sからの最短距離
    v = -1
    que = [(0, s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in es[v]:
            if d[e] > d[v] + 1:
                d[e] = d[v] + 1
                heappush(que, (d[e], e))
    return d[en] if d[en] < INF else -1


print(dijkstra(st))

Submission status: Accepted

Solution code:
def dfs(x,y,visited,grid,dp,r,c,n):
    stack = [(x,y)]
    k = 0
    while k < len(stack):
        x,y = stack[k]
        if (x,y) not in visited:
            dp[x][y] = n
            visited.add((x,y))
            if x+1 < r and grid[x+1][y] == '.':
                stack.append((x+1,y))

            if y+1 < c and grid[x][y+1] == '.':
                stack.append((x,y+1))

            if x-1 >= 0 and grid[x-1][y] == '.':
                stack.append((x-1,y))

            if y-1 >= 0 and grid[x][y-1] == '.':
                stack.append((x,y-1))

        k += 1

def shortestPath(x,y,edges):
    stack = [(x,0)]
    visited = set()
    k = 0
    while k < len(stack):
        x,d = stack[k]
        if x not in visited:
            visited.add(x)
            if x == y:
                print(d)
                return
            
            for kid in edges[x]:
                stack.append((kid,d+1))

        k += 1

    print(-1)

def main():
    r,c = map(int,input().split())
    x1,y1 = map(int,input().split())
    x2,y2 = map(int,input().split())
    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1
    dp = [[0 for j in range(c)] for i in range(r)]
    grid = []
    for i in range(r):
        grid.append(input())

    visited = set()
    n = 1
    for i in range(r):
        for j in range(c):
            if (i,j) not in visited and grid[i][j] == '.':
                dfs(i,j,visited,grid,dp,r,c,n)
                n += 1

    edges = {}
    for i in range(1,n):
        edges[i] = set()

    for i in range(r):
        for j in range(c):
            if grid[i][j] == '.':
                x = dp[i][j]
                for k in range(max(0,i-2),min(r,i+3)):
                    for l in range(max(0,j-2),min(c,j+3)):
                        y = dp[k][l]
                        if x != y and y != 0:
                            edges[x].add(y)
                            edges[y].add(x)

    x = dp[x1][y1]
    y = dp[x2][y2]
    shortestPath(x,y,edges)

main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()

def main():
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    dh, dw = map(int, input().split())
    dh -= 1
    dw -= 1
    S = [input() for _ in range(H)]

    repn = [[] for _ in range(H * W)]  # (cost, to)
    for h in range(H):
        for w in range(W):
            if S[h][w] != '.': continue
            if w > 0 and S[h][w - 1] == '.':
                repn[h * W + w].append((0, h * W + w - 1))
            if w < W - 1 and S[h][w + 1] == '.':
                repn[h * W + w].append((0, h * W + w + 1))
            if h > 0 and S[h - 1][w] == '.':
                repn[h * W + w].append((0, (h - 1) * W + w))
            if h < H - 1 and S[h + 1][w] == '.':
                repn[h * W + w].append((0, (h + 1) * W + w))

            for ph in range(5):
                for pw in range(5):
                    if abs(ph - 2) + abs(pw - 2) <= 1: continue
                    nh = h + ph - 2
                    nw = w + pw - 2
                    if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                        repn[h * W + w].append((1, nh * W + nw))

    q = [(0, ch * W + cw)]
    visited = [10**18] * (H * W)
    visited[ch * W + cw] = 0
    while q:
        cost, u = heappop(q)
        if visited[u] < cost: continue
        for dcost, nu in repn[u]:
            if visited[nu] > cost + dcost:
                visited[nu] = cost + dcost
                heappush(q, (cost + dcost, nu))

    ans = visited[dh * W + dw]
    if ans == 10**18:
        print(-1)
    else:
        print(ans)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

def input():
    return sys.stdin.readline()[:-1]
def smax(a,b):
    if a>b:
        return a
    else:
        return b

def smin(a,b):
    if a<b:
        return a
    else:
        return b

from collections import deque

def BFS(vi,c,e_list,color_list):
        
    Q = deque([vi])
    color_list[vi] = c
    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if color_list[v1]==-1:
                color_list[v1]=c
                Q.appendleft(v1)



def main():
    H,W = list(map(int,input().split()))
    s1,s2 = list(map(int,input().split()))
    g1,g2 = list(map(int,input().split()))
    s1,s2 = s1-1,s2-1
    g1,g2 = g1-1,g2-1
    S = [input() for i in range(H)]

    def z(i,j):
        return i*W + j

    e_list = [[] for i in range(H*W)]

    for i in range(H):
        for j in range(W):
            if i!=H-1:
                if S[i][j]=="." and S[i+1][j]==".":
                    e_list[z(i,j)].append(z(i+1,j))
                    e_list[z(i+1,j)].append(z(i,j))
            if j!=W-1:
                if S[i][j]=="." and S[i][j+1]==".":
                    e_list[z(i,j)].append(z(i,j+1))
                    e_list[z(i,j+1)].append(z(i,j))

    color_list = [-1]*(H*W)
    c = 0


    for i in range(H*W):
        if S[i//W][i%W] == ".":
            if color_list[i]==-1:
                BFS(i,c,e_list,color_list)
                c+=1

    comp = max(color_list)+1
    e_list = [set([]) for i in range(comp)]


    for x in range(H*W):
        i,j = x//W,x%W
        if color_list[x]!=-1:
            for y in range(25):
                i1,j1 = y//5,y%5
                i2 = i1 + i - 2
                j2 = j1 + j - 2
                if 0<=i2 and i2<=H-1 and 0<=j2 and j2<=W-1:
                    if color_list[z(i2,j2)]!=-1 and color_list[z(i2,j2)]!=color_list[x]:
                        e_list[color_list[z(i2,j2)]].add(color_list[x])
                        e_list[color_list[x]].add(color_list[z(i2,j2)])

    vi = color_list[z(s1,s2)]  #change
    INF = float('inf')
    N = comp
    Q = deque([vi])

    checked_list = [False]*N
    checked_list[vi]=True

    min_path_list = [INF]*N #change
    min_path_list[vi] = 0
    #print(e_list)
    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if not checked_list[v1]:
                checked_list[v1]=True
                Q.appendleft(v1)
                min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) #change
    if min_path_list[color_list[z(g1,g2)]]<=10**26:
        print(min_path_list[color_list[z(g1,g2)]])
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
dydx4 = ((-1,0),(0,-1),(0,1),(1,0))
def check(i,j):
  return 0 <= i < h and 0 <= j < w 
def on_block(i,j):
  return S[i][j] == "#"
h,w = map(int,input().split())
ci,cj = map(int,input().split())
ci-=1;cj-=1
gi,gj = map(int,input().split())
gi-=1;gj-=1
S = [list(input()) for i in range(h)]
grid = [[inf] * w for i in range(h)]
grid[ci][cj] = 0
que = collections.deque()
que.append((0,ci,cj))
while que:
  now,si,sj = que.popleft()
  if now > grid[si][sj]:continue
  for di,dj in dydx4:
    ni = si + di
    nj = sj + dj
    if not check(ni,nj):continue
    if on_block(ni,nj): continue
    else:
      if now < grid[ni][nj] :
        grid[ni][nj] = now
        que.appendleft((now,ni,nj))
        # heapq.heappush(que,(now,ni,nj))
  for i in range(si-2,si+3):
    for j in range(sj-2,sj+3):
      if not check(i,j):continue
      if on_block(i,j):continue
      else:
        if now + 1 < grid[i][j] :
          grid[i][j] = now + 1
          que.append((now+1,i,j))
          # heapq.heappush(que,(now+1,i,j))
print(grid[gi][gj] if grid[gi][gj] != inf else -1)
# print(*grid,sep = "\n")

Submission status: Accepted

Solution code:
def bsf_dist_grid(grid,start):
    H = len(grid)
    W = len(grid[0])
    d = [[-1]*W for _ in [0]*H]
    d[start[0]][start[1]] = 0
    q = [start[::-1]]
    while q:
        qq = []
        for xy in q:
            x,y = xy
            d0 = d[y][x]
            for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
                if (not 0<=x+dx<W) or (not 0<=y+dy<H): continue
                if d[y+dy][x+dx] != -1: continue
                if not grid[y+dy][x+dx]: continue
                d[y+dy][x+dx] = d0
                q.append((x+dx,y+dy))
            for dx,dy in ((2,0),(2,1),(2,2),(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 (not 0<=x+dx<W) or (not 0<=y+dy<H): continue
                if d[y+dy][x+dx] != -1: continue
                if not grid[y+dy][x+dx]: continue
                qq.append(((x+dx,y+dy),d0+1))
        q = []
        for qq2,d2 in qq:
            x,y = qq2
            if d[y][x] != -1: continue
            d[y][x] = d2
            q.append(qq2)
    return d

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
s = [[c=="." for c in input()] for _ in [0]*H]

d = bsf_dist_grid(s,(Ch-1,Cw-1))

print(d[Dh-1][Dw-1])

Submission status: Accepted

Solution code:
import sys
my_input = sys.stdin.readline
from collections import deque
H, W = map(int, my_input().split())
Sh, Sw = map(int, my_input().split())
Sh, Sw = Sh - 1, Sw - 1
Gh, Gw = map(int, my_input().split())
Gh, Gw = Gh - 1, Gw - 1
G = [list(my_input()) for _ in range(H)]
INF = 10 ** 9

dist = [[INF] * W for _ in range(H)]
dist[Sh][Sw] = 0
que = deque([[Sh, Sw]])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
directions5 = []
for i in range(-2, 3):
    for j in range(-2, 3):
        directions5.append((i, j))


while que:
    nh, nw = que.pop()
    for dh, dw in directions:
        fh, fw = nh + dh, nw + dw
        if not ((0 <= fh < H) and (0 <= fw < W)):
            continue
        if G[fh][fw] == '#':
            continue
        if dist[fh][fw] <= dist[nh][nw]:
            continue
        dist[fh][fw] = dist[nh][nw]
        que.append([fh, fw])

    for dh, dw in directions5:
        fh, fw = nh + dh, nw + dw
        if not ((0 <= fh < H) and (0 <= fw < W)):
            continue
        if G[fh][fw] == '#':
            continue
        if dist[fh][fw] <= dist[nh][nw] + 1:
            continue
        dist[fh][fw] = dist[nh][nw] + 1
        que.appendleft([fh, fw])

print(dist[Gh][Gw] if dist[Gh][Gw] != INF else - 1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, combinations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from operator import itemgetter
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7
DEBUG = 'ONLINE_JUDGE' not in sys.argv

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)

def main():
    H,W=mis()
    ch,cw=mis()
    ch-=1
    cw-=1
    dh,dw=mis()
    dh-=1
    dw-=1
    S = [input() for _ in range(H)]
    #
    q = deque()
    nq = deque()
    q.append((ch, cw))
    reached = set()
    reached.add((ch, cw))
    zone = set()
    m = 0
    #
    def isv(h, w):
        return (h, w) not in reached and 0<=h<H and 0<=w<W and S[h][w]=='.'
    #
    while True:
        while q:
            h, w = q.popleft()
            zone.add((h, w))
            for nh, nw in ((h+1, w), (h-1, w), (h, w+1), (h, w-1)):
                if isv(nh, nw):
                    q.append((nh, nw))
                    reached.add((nh, nw))
        if (dh, dw) in reached:
            print(m)
            return
        for h, w in zone:
            for th in range(-2+h, 2+1+h):
                for tw in range(-2+w, 2+1+w):
                    if isv(th, tw):
                        nq.append((th, tw))
                        reached.add((th, tw))
        m += 1
        zone.clear()
        q, nq = nq, q
        if not q:
            print(-1)
            return







main()

Submission status: Accepted

Solution code:
from collections import deque

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

F = [["#"]*(W+4)]
F += [["#"]*(W+4)]
F += [["#"]+["#"]+list(input())+["#"]+["#"] for _ in range(H)]
F += [["#"]*(W+4)]
F += [["#"]*(W+4)]

res = [[-1]*(W+4) for _ in range(H+4)]

Q = deque()
Q2 = deque()
Q.append([C[0]+1,C[1]+1])
Q2.append([C[0]+1,C[1]+1])
f_n = True
nd = ((0,1),(0,-1),(1,0),(-1,0))
bnum = 0

while f_n:
  f_n = False
  while len(Q)>0:
    x,y = Q.popleft()
    Q2.append([x,y])
    for dx,dy in nd:
      xx = x+dx
      yy = y+dy
      if F[xx][yy] == "." and res[xx][yy] == -1:
        Q.append([xx,yy])
        res[xx][yy] = bnum
  bnum += 1
  while len(Q2)>0:
    x,y = Q2.popleft()
    for i in range(-2,3):
      for j in range(-2,3):
        xx = x+i
        yy = y+j
        if F[xx][yy] == "." and res[xx][yy] == -1:
          Q.append([xx,yy])
          res[xx][yy] = bnum
          f_n = True
        

print(res[D[0]+1][D[1]+1])

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
from collections import deque
def main():
    H, W = map( int, input().split())
    Ch, Cw = map( lambda x: int(x)-1, input().split())
    Dh, Dw = map( lambda x: int(x)-1, input().split())
    S = [ input() for _ in range(H)]
    k = 10**7
    R = [ [k]*W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                R[i][j] = -1
    R[Ch][Cw] = 0
    T = [ [False]*W for _ in range(H)]
    d = deque([(Ch, Cw)])
    MW = [(-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)]
    while d:
        # print(d)
        # print(R)
        x, y = d.popleft()
        if T[x][y]:
            continue
        else:
            T[x][y] = True
        magic = R[x][y]
        if x == Dh and y == Dw:
            break
        if x > 0:
            if R[x-1][y] > magic:
                R[x-1][y] = magic
                d.appendleft((x-1,y))
        if x < H-1:
            if R[x+1][y] > magic:
                R[x+1][y] = magic
                d.appendleft((x+1,y))
        if y > 0:
            if R[x][y-1] > magic:
                R[x][y-1] = magic
                d.appendleft((x,y-1))
        if y < W-1:
            if R[x][y+1] > magic:
                R[x][y+1] = magic
                d.appendleft((x,y+1))
        for a, b in MW:
            tx, ty = x+a, y+b
            if tx < 0 or tx > H-1:
                continue
            if ty < 0 or ty > W-1:
                continue
            if R[tx][ty] > magic:
                R[tx][ty] = magic+1
                d.append((tx,ty))

    if R[Dh][Dw] == k:
        print(-1)
    else:
        print(R[Dh][Dw])
        
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():

    H, W = map(int, input().split())
    h1, w1 = map(int, input().split())
    h2, w2 = map(int, input().split())
    h1 = h1-1
    w1 = w1-1
    h2 = h2-1
    w2 = w2-1
    S = []
    for _ in range(H):
        S.append(input())

    cur = [[h1, w1]]
    visited = set([(h1, w1)])
    vis = set([(h1, w1)])
    count = 0
    mv = [[-1, 0], [1, 0], [0, 1], [0, -1]]
    while cur:
        while cur:
            temp = []
            for h, w in cur:
                for i, j in mv:
                    x, y = h+i, w+j
                    if 0 <= x < H and 0<= y < W and (x, y) not in visited and S[x][y] == '.':
                        visited.add((x, y))
                        vis.add((x, y))
                        temp.append([x, y])
                        if (x, y) == (h2, w2):
                            return count
            cur = temp

        # print(cur)
        cur = []
        count += 1
        temp = set()
        for h, w in vis:
            for i in range(-2, 3):
                for j in range(-2, 3):
                    x, y = h+i, w+j
                    if 0 <= x < H and 0<= y < W and (x, y) not in visited and S[x][y] == '.':
                        cur.append([x, y])
                        visited.add((x, y))
                        temp.add((x, y))
                        if (x, y) == (h2, w2):
                            return  count
        # print(cur)
        vis = temp
    return -1


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, C, D, S):

    C = (C[0]-1, C[1]-1)
    D = (D[0]-1, D[1]-1)
    q = deque()
    q.append((0, C))
    memo = {}
    while q:
        c, (x, y) = q.popleft()
        if (x, y) in memo:
            continue
        memo[(x, y)] = c
        for nx, ny in [(x, y-1), (x, y+1), (x-1, y), (x+1, y)]:
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if (nx, ny) not in memo:
                    q.appendleft((c, (nx, ny)))

        for nx in range(x-2, x+3):
            for ny in range(y-2, y+3):
                if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                    if (nx, ny) not in memo:
                        q.append((c+1, (nx, ny)))


    return -1 if tuple(D) not in memo else memo[D]


def main():
    H, W = read_int_n()
    C = read_int_n()
    D = read_int_n()
    S = [read_str() for _ in range(H)]
    print(slv(H, W, C, D, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

INF = 10**18

H, W = map(int, input().split())
Ch, Cw = map(lambda x:int(x) - 1, input().split())
Dh, Dw = map(lambda x:int(x) - 1, input().split())
S = [input() for _ in range(H)]

dist = [[None for j in range(W)] for i in range(H)]
dist[Ch][Cw] = 0

queue = deque()
queue.append((Ch, Cw))

while queue:
    x, y = queue.popleft()
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if dx == dy == 0:
                continue
            nx = x + dx
            ny = y + dy
            if not (0 <= nx < H and 0 <= ny < W):
                continue
            if S[nx][ny] == '#':
                continue
            if (dx == 0 and dy == 1) or (dx == 0 and dy == -1) or (dx == 1 and dy == 0) or (dx == -1 and dy == 0):
                if dist[nx][ny] == dist[x][y] + 1 or dist[nx][ny] is None:
                    dist[nx][ny] = dist[x][y]
                    queue.appendleft((nx, ny))
            else:
                if dist[nx][ny] is not None:
                    continue
                dist[nx][ny] = dist[x][y] + 1
                queue.append((nx, ny))

print(dist[Dh][Dw] if dist[Dh][Dw] is not None else -1)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
#input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

grid = [[0 for _ in range(W)] for _ in range(H)]
grid[Ch][Cw] = 1

stack1 = [(Ch, Cw)]
stack2 = []

answer = 1

#print(grid)

while 1:
    while stack1:
        sh, sw = stack1.pop()
    
        stack2.append((sh, sw))
    
        for i, j in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
            nh, nw = sh + i, sw + j
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != "#" and grid[nh][nw] == 0:
                if nh == Dh and nw == Dw:
                    print(answer - 1)
                    exit()
                grid[nh][nw] = answer
                stack1.append((nh, nw))
    #print(grid)
    
    if len(stack2) == 0:
        break
    
    answer += 1
    while stack2:
        sh, sw = stack2.pop()
        for i in range(-2, 3):
            for j in range(-2, 3):
                nh, nw = sh + i, sw + j
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != "#" and grid[nh][nw] == 0:
                    if nh == Dh and nw == Dw:
                        print(answer - 1)
                        exit()
                    grid[nh][nw] = answer
                    stack1.append((nh, nw))
    #print(grid)

print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
state = [list(input().rstrip()) for _ in range(H)]

def nexts1(h, w):
    ret = []
    if h != 0: ret.append((h-1, w))
    if h != H-1: ret.append((h+1, w))
    if w != 0: ret.append((h, w-1))
    if w != W-1: ret.append((h, w+1))
    return ret

def nexts2(h, w):
    ret = []
    for nh in range(h-2, h+3):
        for nw in range(w-2, w+3):
            if 0 <= nh < H and 0 <= nw < W:
                ret.append((nh, nw))
    return ret


def bfs():
    checked = [[-1]*W for _ in range(H)]
    P = {(sh, sw)}
    cnt = 0
    while P:
        q = []
        for h, w in P:
            if checked[h][w] == -1:
                checked[h][w] = 1
                q.append((h, w))
        P = set()
        while q:
            qq = []
            for h, w in q:
                if h == gh and w == gw:
                    return cnt
                for nh, nw in nexts1(h, w):
                    if state[nh][nw] == ord(".") and checked[nh][nw] == -1:
                        checked[nh][nw] = checked[h][w]
                        qq.append((nh, nw))
                for nh, nw in nexts2(h, w):
                    if checked[nh][nw] == -1 and state[nh][nw] == ord(".") and not (nh, nw) in P:
                        P.add((nh, nw))
            q = qq
        cnt += 1
    return -1

def main():
    print(bfs())


if __name__ == "__main__":
    main()