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:
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 True:
    _nexts=[]
    for n in 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 len(nexts)==0:
        break

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

Submission status: Accepted

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

s = list()
offsets = list()

for i in range(-2, 3):
    for j in range(-2, 3):
        offsets.append((i, j))


def print_map(m):
    for mm in m:
        print(mm)


def label(num, x, y):
    res = list()
    if not (0 <= x < h and 0 <= y < w):
        return res
    if s[x][y] != ".":
        return res
    s[x][y] = num

    res += label(num, x - 1, y)
    res += label(num, x + 1, y)
    res += label(num, x, y - 1)
    res += label(num, x, y + 1)

    res.append((x, y))

    return res


def find_next(x, y):
    res = list()

    for offset in offsets:
        xx, yy = x + offset[0], y + offset[1]
        if not (0 <= xx < h and 0 <= yy < w):
            continue

        if s[xx][yy] == ".":
            res.append((xx, yy))

    return res


for i in range(h):
    s.append(list(input()))

stage = 0
labeled = label(stage, dh - 1, dw - 1)

stage += 1

while len(labeled) > 0:
    new_labeled = list()
    for l in labeled:
        nexts = find_next(l[0], l[1])
        for n in nexts:
            new_labeled += label(stage, n[0], n[1])

    labeled = new_labeled
    stage += 1

if s[ch - 1][cw - 1] != ".":
    print(s[ch - 1][cw - 1])
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
def main():
    h, w = map(int, input().split())
    S = list(map(lambda x: int(x) - 1, input().split()))
    G = list(map(lambda x: int(x) - 1, input().split()))
    A = [list(input()) for _ in range(h)]
    INF = 100000000
    score = [[INF] * w for _ in range(h)]
    score[S[0]][S[1]] = 0
    visited = [[False] * w for _ in range(h)]
    stack = deque([S])
    dxy = [[1, 0], [-1, 0], [0, -1], [0, 1]]
    while stack:
        y, x = stack.popleft()
        if visited[y][x]:
            continue
        else:
            visited[y][x] = True
        count = 0
        for dx, dy in dxy:
            X = x + dx
            Y = y + dy
            if Y < 0 or Y >= h or X < 0 or X >= w:
                continue
            elif A[Y][X] == '.':
                stack.appendleft([Y, X])
                score[Y][X] = min(score[Y][X], score[y][x])
        if count == 0 and A[y][x] == '.':
            for i in range(-2, 3):
                for j in range(-2, 3):
                    X = x + j
                    Y = y + i
                    if Y < 0 or Y >= h or X < 0 or X >= w:
                        continue
                    if A[Y][X] == '.' and score[Y][X] > score[y][x] + 1:
                        stack.append([Y, X])
                        score[Y][X] = min(score[Y][X], score[y][x] + 1)
    print(score[G[0]][G[1]]) if score[G[0]][G[1]] != INF else print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

S = [0 for i in range(H+4)]
S[0] = "#"*(W+4)
S[1] = "#"*(W+4)
S[H+2] = "#"*(W+4)
S[H+3] = "#"*(W+4)
for i in range(2, H+2):
  S[i] = "##" + input() + "##"
  
B = [ [-1 for i in range(W+4)] for i in range(H+4)]

def search(i,j,c):
  global B
  B[i][j] = c
  L = [(-1,0), (1, 0), (0, -1), (0, 1)]
  for X in L:
    if S[i+X[0]][j+X[1]] == '.' and B[i+X[0]][j+X[1]] < 0:
        search(i+X[0],j+X[1],c)
        
#<01>[2--H+1]<H+2,3>#
c = 0
for i in range(2,H+2):
  for j in range(2,W+2):
    if S[i][j] == '.' and B[i][j] < 0:
      search(i, j, c)
      c += 1

Cc = B[Ch+1][Cw+1]
Dc = B[Dh+1][Dw+1]
dic = {i:set() for i in range(c)}

for i in range(2, H+2):
  for j in range(2, W+2):
    if B[i][j] >= 0:
      for x in range(-2, 3):
        for y in range(-2, 3):
          if S[i+x][j+y] == '.' and B[i][j] != B[i+x][j+y]:
            dic[B[i][j]].add(B[i+x][j+y])

ans = [-1 for i in range(c)]
ans[Cc] = 0
not_check = [1 for i in range(c)]
not_check[Cc] = 0
next_check = {Cc}
#
t = 0
while len( next_check ):
  t += 1
  tmp = set()
  for i in next_check:
    for j in dic[i]:
      if not_check[j]:
        not_check[j] = 0
        ans[j] = t
        tmp.add( j )
  next_check = {i for i in tmp}
#
print(ans[Dc])

Submission status: Accepted

Solution code:
def main():
    import collections
    import sys
    input = sys.stdin.buffer.readline
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    input = sys.stdin.readline
    S = [input() for i in range(H)]

    q = collections.deque()
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    flag = True

    r = set()
    ss = []
    start = -1
    goal = -1
    # D = collections.defaultdict(int)
    D = dict()
    for i in range(H):
        for j in range(W):
            if (i, j) in r or S[i][j] == '#':
                continue
            q.append((i, j))
            ss.append(set([(i, j)]))
            r.add((i, j))
            L = len(ss)
            D[(i, j)] = L-1
            while(q):
                x, y = q.popleft()
                for k, l in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
                    if 0 <= k <= H-1 and 0 <= l <= W-1 and S[k][l] != '#' and (k, l) not in r:
                        r.add((k, l))
                        D[(k, l)] = L - 1
                        q.append((k, l))
                        ss[-1].add((k, l))
            if start == -1 and (Ch, Cw) in ss[-1]:
                start = L - 1
            if goal == -1 and (Dh, Dw) in ss[-1]:
                goal = L - 1

    if D[Ch, Cw] == D[(Dh, Dw)]:
        print(0)
        exit(0)

    G = [set() for i in range(len(ss))]
    for id, X in enumerate(ss):
        for x, y in X:
            for i in range(x-2, x+3):
                if 0 <= i <= H-1:
                    for j in range(y-2, y+3):
                        if 0 <= j <= W-1:
                            if S[i][j] != '#' and D[(i, j)] != id:
                                G[id].add(D[(i, j)])

    r = set()
    r.add(start)
    q.append((start, 0))
    while(q):
        x, c = q.popleft()
        if x == goal:
            print(c)
            flag = False
            break
        for y in G[x]:
            if y in r:
                continue
            else:
                r.add(y)
                q.append((y, c+1))
    # print(G)
    if flag:
        print(-1)


main()

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

h,w = m()

c = l()

d = l()

s = [list(input()[:-1]) for i in range(h)]

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

po = [cl.deque([]) for i in range(h*w // 2 + 1)]

now = 0
po[0] = cl.deque([[c[0]-1,c[1]-1]])
d[0] -= 1
d[1] -= 1
dire = [[1,0],[0,1],[-1,0],[0,-1]]

#data[c[0]-1][c[1]-1] = 0

while True:
    if now >= h*w // 2 + 1:
        break
    if len(po[now]) == 0:
        now += 1
        continue
    else:
        popo = po[now].popleft()
        if data[popo[0]][popo[1]] != -1 and data[popo[0]][popo[1]] < now:
            continue
        else:
            data[popo[0]][popo[1]] = now
            for kkk in dire:
                if (popo[0] + kkk[0] >= 0 and popo[0] + kkk[0] < h) and (popo[1] + kkk[1] >= 0 and popo[1] + kkk[1] < w):
                    if s[popo[0] + kkk[0]][popo[1] + kkk[1]] == "#":
                        continue
                    if data[popo[0] + kkk[0]][popo[1] + kkk[1]] == -1 or data[popo[0] + kkk[0]][popo[1] + kkk[1]] > now:
                        data[popo[0] + kkk[0]][popo[1] + kkk[1]] = now
                        po[now].append([popo[0]+ kkk[0],popo[1] + kkk[1]])

            for i in range(5):
                i -= 2
                if i + popo[0] < 0 or i + popo[0] >= h:
                    continue
                for j in range(5):
                    j -= 2
                    if j + popo[1] < 0 or j + popo[1] >= w:
                        continue
                    elif s[popo[0]+ i][popo[1] + j] == ".":
                        if data[popo[0]+ i][popo[1] + j] > now+1 or data[popo[0]+ i][popo[1] + j] == -1:
                            if now + 1 <= h*w // 2:
                                data[popo[0]+ i][popo[1] + j] = now+1
                                po[now+1].append([popo[0]+ i,popo[1] + j])


print(data[d[0]][d[1]])

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
H, W = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1

C = [list(input()) for i in range(H)]
inf = float("inf")
for i in range(H):
    for j in range(W):
        if C[i][j] == ".":
            C[i][j] = 0
        else:
            C[i][j] = 1
d0 = [[1, 0], [0, 1], [-1, 0], [0, -1]]
d1 = [[-2, -2], [-2, -1], [-2, 0], [-2, 2], [-1, 2], [0, 2], [-2, 1], [-1, -2], [-1, -1], [-1, 1], [0, -2], [1, -2], [1, -1], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]
# d1 = [[i, j] for i in range(-2, 3) for j in range(-2, 2)]
dist = [[inf] * W for i in range(H)]
dist[sx][sy] = 0
que = deque([[0, sx, sy]])
while que:
    L, x, y = que.popleft()
    # if x == gx and y == gy:
    #     break
    for dx, dy in d0:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and L + C[nx][ny] < dist[nx][ny] and C[nx][ny] == 0:
            dist[nx][ny] = L + C[nx][ny]
            que.appendleft([L, nx, ny])
    for dx, dy in d1:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and L + C[nx][ny] + 1 < dist[nx][ny] and C[nx][ny] == 0:
            dist[nx][ny] = L + C[nx][ny] + 1
            que.append([L + 1, nx, ny])
            # que.appendleft([L + 1, nx, ny])

            # if C[nx][ny] == 1:
            #     que.append([L + 1, nx, ny])
            # else:
            #     que.appendleft([L, nx, ny])
# for h in range(H):
#     print(dist[h])

ans = dist[gx][gy]
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
h,w=map(int,input().split())
ch,cw=map(int,input().split())
ch-=1
cw-=1
stack=[(ch,cw)]
dh,dw=map(int,input().split())
dh-=1
dw-=1
b=[w*[-1]for _ in range(h)]
for i in range(h):
  for j,t in enumerate(input()):
    if t=="#":b[i][j]=10**10
b[ch][cw]=0
dxy=((-1,0),(1,0),(0,-1),(0,1))
for ans in range(10**6):
  for x,y in stack:
    b[x][y]=1
    if x==dh and y==dw:
      print(ans)
      exit()
    for dx,dy in dxy:
      if 0<=x+dx<h and 0<=y+dy<w:
        if b[x+dx][y+dy]==10**10:continue
        if b[x+dx][y+dy]==-1:
          stack.append((x+dx,y+dy))
          b[x+dx][y+dy]=1
  stackk=[]
  for x,y in stack:
    for xx in range(max(0,x-2),min(h,x+3)):
      for yy in range(max(0,y-2),min(w,y+3)):
        if b[xx][yy]==-1:stackk.append((xx,yy))
  stack=stackk
print(-1)

Submission status: Accepted

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 = [input() for _ in range(H)]
ch-=1
cw-=1
dh-=1
dw-=1

walk = [(0, 1), (1, 0), (-1, 0), (0, -1)]
jump = [(-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)]
step = 0
already = set()
already.add((ch,cw))
next = set()
next.add((ch,cw))
while len(next) > 0:
    d = deque(list(next))
    step_already = list(next)
    while len(d) > 0:
        pop = d.popleft()
        for h, w in walk:
            nh, nw = pop[0]+h, pop[1]+w
            if (nh, nw) not in already and nh >= 0 and nh<H and nw >= 0 and nw<W and S[nh][nw] != '#':
                if nh == dh and nw == dw:
                    print(step)
                    exit()
                already.add((nh, nw))
                step_already.append((nh, nw))
                d.append((nh,nw))
    next = set()
    step += 1
    for h, w in step_already:
        for jh, jw in jump:
            nh, nw = h+jh, w+jw
            if (nh, nw) not in already and nh >= 0 and nh<H and nw >= 0 and nw<W and S[nh][nw] != '#':
                if nh == dh and nw == dw:
                    print(step)
                    exit()
                next.add((nh,nw))
                already.add((nh,nw))

print(-1)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

H,W = LI()
Ch,Cw = LI()
Dh,Dw = LI()

Q = [list(map(str,input())) for _ in range(H)]
D = [(0,1),(0,-1),(-1,0),(1,0)]

visited = [[-1]*W for _ in range(H)]

s = (Ch-1,Cw-1)
c = 0
visited[Ch-1][Cw-1] = c
S = [s]
Sc = [s]
while True:
    while S:
        v = S.pop()
        for d in D:
            new = (v[0]+d[0],v[1]+d[1])
            if new[0] == Dh-1 and new[1] == Dw-1:
                print(c)
                exit()
            if 0 <= new[0] < H and 0 <= new[1] < W and Q[new[0]][new[1]] == '.' and visited[new[0]][new[1]] == -1:
                visited[new[0]][new[1]] = c
                S.append(new)
                Sc.append(new)
    c += 1
    S = []
    for v in Sc:
        for i in range(-2,3):
            for j in range(-2,3):
                new = (v[0]+i,v[1]+j)
                if new[0] == Dh-1 and new[1] == Dw-1:
                    print(c)
                    exit()
                if 0 <= new[0] < H and 0 <= new[1] < W and visited[new[0]][new[1]] == -1 and Q[new[0]][new[1]] == '.':
                    S.append(new)
                    visited[new[0]][new[1]] = c
    if not S:
        break
    Sc = S[:]
    
print(-1)

Submission status: Accepted

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

H,W=map(int,input().split())
sh,sw=map(int,input().split())
gh,gw=map(int,input().split())
MAP=[input().strip() for i in range(H)]

ANS=[[1<<30]*W for i in range(H)]

sh-=1
sw-=1
gh-=1
gw-=1

ANS[sh][sw]=0

def ca(sc,x,y):
    return sc*(10**8)+x*(10**4)+y

def inv(w):
    sc=w//(10**8)
    w%=(10**8)
    x=w//(10**4)
    y=w%(10**4)

    return sc,x,y

Q=[ca(0,sh,sw)]

while Q:
    sc,x,y=inv(heapq.heappop(Q))

    if sc>ANS[x][y]:
        continue

    for i,j in [(x-2,y-2),(x-2,y-1),(x-2,y),(x-2,y+1),(x-2,y+2),(x-1,y-2),(x-1,y-1),(x-1,y),(x-1,y+1),(x-1,y+2),(x,y-2),(x,y-1),(x,y+1),(x,y+2),(x+1,y-2),(x+1,y-1),(x+1,y),(x+1,y+1),(x+1,y+2),(x+2,y-2),(x+2,y-1),(x+2,y),(x+2,y+1),(x+2,y+2)]:
        if 0<=i<H and 0<=j<W:
            if MAP[i][j]=="." and abs(i-x)+abs(j-y)==1 and ANS[i][j]>sc:
                ANS[i][j]=sc
                heapq.heappush(Q,ca(ANS[i][j],i,j))
            elif MAP[i][j]=="." and abs(i-x)+abs(j-y)>1 and ANS[i][j]>sc+1:
                ANS[i][j]=sc+1
                heapq.heappush(Q,ca(ANS[i][j],i,j))

if ANS[gh][gw]==1<<30:
    print(-1)
else:
    print(ANS[gh][gw])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from sys import stdin, stdout
 
def input():
    return stdin.readline().strip()

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

Cx, Cy = input().split()
Cx = int(Cx)
Cy = int(Cy)

Dx, Dy = input().split()
Dx = int(Dx)
Dy = int(Dy)

matrix = []

for _ in range(H):
    row = list(input())
    matrix += [row]

# print("reading done")

from collections import deque


visited = set()

def bfs(x, y, label):
    global visited
    worklist = deque([(x, y)])
    while len(worklist):
        (x, y) = worklist.popleft()
        matrix[x][y] = label
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            new_x, new_y = x+dx, y+dy
            if 0 <= new_x < H and 0 <= new_y < W and matrix[new_x][new_y] == '.' and (new_x, new_y) not in visited:
                worklist.append((new_x, new_y))
                visited.add((new_x, new_y))
    
# for row in matrix:
#     print(''.join(map(str, row)))

curr_label = 0
for x in range(0, H):
    for y in range(0, W):
        if matrix[x][y] == '.':
            bfs(x, y, curr_label)
            curr_label += 1

# for row in matrix:
#     print(''.join(map(str, row)))

# print("cc done")

neighbours = []

for _ in range(0, curr_label):
    neighbours += [set()]

for x in range(H):
    for y in range(W):
        u = matrix[x][y]
        if u == '#': continue
        for dx in [-2, -1, 0, 1, 2]:
            for dy in [-2, -1, 0, 1, 2]:
                new_x = x + dx
                new_y = y + dy

                if 0 <= new_x < H and 0 <= new_y < W and matrix[new_x][new_y] != '#':
                    v = matrix[new_x][new_y]
                    if u == v: continue

                    neighbours[u].add(v)
                    neighbours[v].add(u)

Cx -= 1
Cy -= 1

Dx -= 1
Dy -= 1

source = matrix[Cx][Cy]
target = matrix[Dx][Dy]

import sys

if source == '#' or target == '#':
    print(-1)
    sys.exit(0)

visited = set([source])
frontier = set([source])

if target in frontier:
    print(0)
    sys.exit(0)

# print(neighbours, source, target)

count = 1
while len(frontier):
    next_frontier = set()
    for u in frontier:
        for v in neighbours[u]:
            if v not in visited:
                visited.add(v)
                next_frontier.add(v)
    if target in next_frontier:
        print(count)
        count += 1
        sys.exit(0)

    count += 1
    frontier = next_frontier

print(-1)

Submission status: Accepted

Solution code:
import copy
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 = []
for i in range(h):
    S.append(list(input()))
#print(S)

def by_walk(stack):
    walk_point = copy.copy(stack)
    while stack != []:
        temp = []
        for i, j in stack:
            warp_counter = S[i][j]
            next_points = [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]
            for next_point in next_points:
                next_h, next_w = next_point
                if next_h >= 0 and next_h < h and next_w >= 0 and next_w < w:
                    if S[next_h][next_w] ==".":
                        S[next_h][next_w] = warp_counter
                        temp.append(next_point)
                        walk_point.append(next_point)
        stack = temp
    return walk_point

def warp(stack):
    warp_point = []
    for i, j in stack:
        warp_counter = S[i][j]
        for shift_i in range(-2, 3):
            for shift_j in range(-2, 3):
                new_i = i + shift_i
                new_j = j + shift_j
                if not(new_i == i and new_j == j):
                    if new_i >= 0 and new_i < h and new_j >= 0 and new_j < w:
                        if S[new_i][new_j] == ".":
                            S[new_i][new_j] = warp_counter + 1
                            warp_point.append((new_i, new_j))
    return warp_point

stack = [(ch, cw)]
S[ch][cw] = 0
"""
ans = by_walk(stack)
print(ans)
ans = warp(ans)
print(*S, sep="\n")
print(ans)
"""
while stack != []:
    stack = by_walk(stack)
    #print(*S, sep="\n")
    #print(stack)
    if S[dh][dw] != ".":
        print(S[dh][dw])
        break
    stack = warp(stack)
    #print(*S, sep="\n")
    #print(stack)
    if S[dh][dw] != ".":
        print(S[dh][dw])
        break
else:
    print(-1)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
inpl = lambda: list(map(int,input().split()))
H, W = inpl()
sh, sw = inpl()
start = (sh-1, sw-1)
gh, gw = inpl()
goal = (gh-1, gw-1)
S = [input() for _ in range(H)]

count = [[-1]*W for _ in range(H)]
count[start[0]][start[1]] = 0
q = [(0, start)]
while q:
    d, p = heappop(q)
    if p == goal:
        print(d)
        exit()
    h, w = p
    if d > count[h][w]:
        continue
    for dh, dw in ((1,0), (-1,0), (0,1), (0,-1)):
        nh, nw = h+dh, w+dw
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and (count[nh][nw] < 0 or count[nh][nw] > d):
            count[nh][nw] = d
            heappush(q, (d, (nh, nw)))
    for dh in range(-2,3):
        for dw in range(-2,3):
            nh, nw = h+dh, w+dw
            if (dh,dw) != (0,0) and 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and count[nh][nw] < 0:
                count[nh][nw] = d+1
                heappush(q, (d+1, (nh, nw)))
print(-1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

from collections import deque
import itertools

h,w = map(int,readline().split())
cx,cy = map(int,readline().split())
gx,gy = map(int,readline().split())
cx -= 1
cy -= 1
grid = [readline().rstrip() for i in range(h)]

dist = [[INF]*w for i in range(h)]
dist[cx][cy] = 0

l2 = list(itertools.product([-2,-1,0,1,2],repeat = 2))
l1 = [(-1,0),(1,0),(0,-1),(0,1)]
q1 = deque([(cx,cy)])
q2 = deque([(cx,cy)])

while q1 or q2:
    if q1:
        x,y = q1.popleft()
        for dy,dx in l1:
            ny,nx = y+dy, x+dx
            if not (0 <= ny < w and 0 <= nx < h):
                continue
            if grid[nx][ny] == '#':
                continue
            if dist[nx][ny] != INF:
                continue
            if dist[nx][ny] > dist[x][y]:
                dist[nx][ny] = dist[x][y]
                q1.append((nx,ny))
                q2.append((nx,ny))
    else:
        x,y = q2.popleft()
        for dy,dx in l2:
            ny,nx = y+dy, x+dx
            if not (0 <= ny < w and 0 <= nx < h):
                continue
            if grid[nx][ny] == '#':
                continue
            if dist[nx][ny] != INF:
                continue
            if dist[nx][ny] > dist[x][y]+1:
                dist[nx][ny] = dist[x][y]+1
                q1.append((nx,ny))
                q2.append((nx,ny))

print(dist[gx-1][gy-1] if dist[gx-1][gy-1] != INF else -1)

Submission status: Accepted

Solution code:
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def solve(dist, start, goal):
    H,W = len(dist),len(dist[0])

    q = [start]
    dist[start[0]][start[1]] = 0
    cnt = 0
    while q:
        nq = []
        while q:
            x,y = q.pop()
            if (x,y) == goal:
                return cnt
            if dist[x][y] < cnt:
                continue
            for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
                nx,ny = x+dx,y+dy
                if 0<=ny<W and 0<=nx<H and dist[nx][ny] > cnt:
                    dist[nx][ny] = cnt
                    q.append((nx,ny))
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx,ny = x+dx,y+dy
                    if 0<=ny<W and 0<=nx<H and dist[nx][ny] > cnt+1:
                        dist[nx][ny] = cnt+1
                        nq.append((nx,ny))
        q = nq
        cnt += 1
    return -1




if __name__ == '__main__':
    H,W = map(int,readline().split())
    start = tuple(map(lambda i:int(i)-1,readline().split()))
    goal = tuple(map(lambda i:int(i)-1,readline().split()))

    dist = [[10**7 if c=='.' else -1 for c in t.decode()] for t in read().split()]

    print(solve(dist,start,goal))

Submission status: Accepted

Solution code:
from collections import deque
def main():
    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
    m = [[0]*(w+4)]
    m.append([0]*(w+4))
    for i in range(h):
        s = input()
        temp = [0,0]
        for j in s:
            if j == ".":
                temp.append(1)
            else:
                temp.append(0)
        temp.append(0)
        temp.append(0)
        m.append(temp)
    m.append([0]*(w+4))
    m.append([0]*(w+4))

    t = [[1000000]*(w+4) for _ in range(h+4)]


    queue = deque([(ch,cw,0)])
    t[ch][cw] = 0
    
    while(len(queue) > 0):
        q = queue.popleft()
        nh = q[0]
        nw = q[1]
        dir = [(1,0),(-1,0),(0,1),(0,-1)]
        
        for d in dir:
            if m[nh + d[0]][nw + d[1]] == 1 and t[nh + d[0]][nw + d[1]] > q[2]:
                queue.appendleft((nh + d[0] , nw + d[1], q[2]))
                t[nh + d[0]][nw + d[1]] = q[2]

        dir = [(1,1),(-1,1),(-1,-1),(1,-1),(-2,2),(-1,2),(0,2),(1,2),(2,2),(-2,1),(2,1),(-2,0),(2,0),(-2,-1),(2,-1),(-2,-2),(-1,-2),(0,-2),(1,-2),(2,-2)]

        for d in dir:
            if m[nh + d[0]][nw + d[1]] == 1 and t[nh + d[0]][nw + d[1]] > q[2]+1:
                queue.append((nh + d[0] , nw + d[1], q[2] + 1))
                t[nh + d[0]][nw + d[1]] = q[2]+1
        

    print(t[dh][dw] if t[dh][dw] != 1000000 else -1)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
#from bisect import bisect_left, bisect_right
#from itertools import combinations, permutations, product
from heapq import heappush, heappop
#from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

dist = defaultdict(lambda: float('inf'))
def dijkstra(start, end):
	dist[start] = 0
	heap = []
	heappush(heap, (0, start))
	while heap:
		d, n = heappop(heap)
		if n == end:
			return d
		if dist[n] != d:
			continue
		edges = get_edges(n)
		for nn, ed in edges:
			nd = d + ed
			if dist[nn] > nd:
				dist[nn] = nd
				heappush(heap, (nd, nn))
	return -1

def get_edges(n):
	i, j = n
	edges = []
	if M[i][j] == '#': return edges
	for di in range(-2, +3):
		for dj in range(-2, +3):
			ni, nj = i+di, j+dj
			if di == 0 and dj == 0: continue
			if not(0 <= ni < H and 0 <= nj < W): continue
			if M[ni][nj] == '#': continue
			if (di, dj) in [(1,0),(-1,0),(0,1),(0,-1)]:
				edges.append(((ni, nj), 0))
			else:
				edges.append(((ni, nj), 1))
	return edges

H, W = rl()
C = rl()
D = rl()
M = []
for i in range(H):
	s = rs()
	M.append(s)

start = tuple([C[0]-1, C[1]-1])
end = tuple([D[0]-1, D[1]-1])
d = dijkstra(start, end)
print(d)