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

Solution (Python):


from collections import deque

q = deque()

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


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



for i in range(h):
  
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]

ban_list[ch][cw] = 0


cost = 0
ph = ch
pw = cw

q.append([ph, pw])








loop = True
while loop:
  
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  
  
  
  if ph == 0:
    pass
  else:
    if ban_list[ph-1][pw] != "
      if ban_list[ph-1][pw] == "." or cost < ban_list[ph-1][pw]:
        ban_list[ph-1][pw] = cost
        
        q.appendleft([ph-1, pw])
    else:
      pass

  
  if pw == w -1:
    pass
  else:
    if ban_list[ph][pw + 1] != "
      if ban_list[ph][pw + 1] == "." or cost < ban_list[ph][pw + 1]:
        ban_list[ph][pw + 1] = cost
        q.appendleft([ph, pw+1])
    else:
      pass

  
  if ph == h -1:
    pass
  else:
    if ban_list[ph+1][pw] != "
      if ban_list[ph+1][pw] == "." or cost < ban_list[ph+1][pw]:
        ban_list[ph+1][pw] = cost
        q.appendleft([ph+1, pw])
    else:
      pass

  
  if pw == 0:
    pass
  else:
    if ban_list[ph][pw - 1] != "
      if ban_list[ph][pw - 1] == "." or cost < ban_list[ph][pw - 1]:
        ban_list[ph][pw - 1] = cost
        q.appendleft([ph, pw-1])
    else:
      pass


  
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        
        
        
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])

  if len(q) == 0:
    loop = False


result = ban_list[dh][dw]
if result == ".":
  result = -1





print(result)

Solution (Python):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 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)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '
        dst[h][w] = d
        for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
        for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Solution (Python):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 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)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if h < 0 or H <= h or w < 0 or W <= w or dst[h][w] >= 0 or S[h][w] == '
    dst[h][w] = d
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])

Solution (Python):
from collections import deque
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
C=(Ch,Cw)
D=(Dh,Dw)
S=[list(input()) for i in range(H)]
dist=[[10**15 for j in range(W)] for i in range(H)]
dist[Ch][Cw]=0
q=deque([C])
dx=[1,0,-1,0]
dy=[0,1,0,-1]
while(len(q)>0):
    x,y=q.popleft()
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=nx<H and 0<=ny<W:
            if S[nx][ny]=="
                continue
            if dist[nx][ny]>dist[x][y]:
                dist[nx][ny]=dist[x][y]
                q.appendleft((nx,ny))
    for i in range(-2,3):
        for j in range(-2,3):
            nx=x+i
            ny=y+j
            if 0<=nx<H and 0<=ny<W:
                if S[nx][ny]=="
                    continue
                if dist[nx][ny]>dist[x][y]+1:
                    dist[nx][ny]=dist[x][y]+1
                    q.append((nx,ny))
if dist[Dh][Dw]==10**15:
    print(-1)
else:
    print(dist[Dh][Dw])

Solution (Python):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 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)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if dst[h][w] >= 0 or S[h][w] == '
    if dst[h][w] == -1 or d < dst[h][w]: dst[h][w] = d

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '
        if dst[nh][nw] >= 0: continue
        dq.appendleft((nh, nw, d))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '
        if dst[nh][nw] >= 0: continue
        dq.append((nh, nw, d+1))

print(dst[eh][ew])

Solution (Python):
from collections import deque
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
maze = [[9]*(w+4)]
maze.append([9]*(w+4))
for i in range(h):
  s = input()
  tmp = [9,9]
  for i in s:
    if i == "
      tmp.append(9)
    else:
      tmp.append(0)
  tmp.append(9)
  tmp.append(9)
  maze.append(tmp)
maze.append([9]*(w+4))
maze.append([9]*(w+4))


pos = deque()
pos.append([ch+1,cw+1,0])
while len(pos)>0:
  x, y, hop = pos.popleft()
  
  
  if (x,y) == (dh+1,dw+1):
    print(hop)
    break
  maze[x][y] = 3
  
  if maze[x-1][y] <3:
    pos.appendleft([x-1,y,hop])
    maze[x-1][y] = 3  
    
  if maze[x+1][y] <3:
    pos.appendleft([x+1,y,hop])
    maze[x+1][y] = 3
    
  if maze[x][y-1] <3:
    pos.appendleft([x,y-1,hop])
    maze[x][y-1] = 3
    
  if maze[x][y+1] <3:
    pos.appendleft([x,y+1,hop])
    maze[x][y+1] = 3

  
  move = [(i,j) for i in range(-2,3) for j in range(-2,3)]
  for dx,dy in move:
    if maze[x+dx][y+dy] <2:
      pos.append([x+dx,y+dy,hop+1])
      maze[x+dx][y+dy] = 2
  
else:
  print(-1)

Solution (Python):
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 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)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if dst[h][w] >= 0 or S[h][w] == '
    dst[h][w] = d

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '
        if dst[nh][nw] >= 0: continue
        dq.appendleft((nh, nw, d))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '
        if dst[nh][nw] >= 0: continue
        dq.append((nh, nw, d+1))

print(dst[eh][ew])

Solution (Python):
from collections import deque
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
maze = [[9]*(w+4)]
maze.append([9]*(w+4))
for i in range(h):
  s = input()
  tmp = [9,9]
  for i in s:
    if i == "
      tmp.append(9)
    else:
      tmp.append(0)
  tmp.append(9)
  tmp.append(9)
  maze.append(tmp)
maze.append([9]*(w+4))
maze.append([9]*(w+4))


pos = deque()
pos.append([ch+1,cw+1,0])
while len(pos)>0:
  x, y, hop = pos.popleft()
  
  
  if (x,y) == (dh+1,dw+1):
    print(hop)
    break
  maze[x][y] = 3
  
  if maze[x-1][y] <3:
    pos.appendleft([x-1,y,hop])
    maze[x-1][y] = 3  
    
  if maze[x+1][y] <3:
    pos.appendleft([x+1,y,hop])
    maze[x+1][y] = 3
    
  if maze[x][y-1] <3:
    pos.appendleft([x,y-1,hop])
    maze[x][y-1] = 3
    
  if maze[x][y+1] <3:
    pos.appendleft([x,y+1,hop])
    maze[x][y+1] = 3

  move =[(-2,0),(-2,1),(-2,2),(-2,-1),(-2,-2),(2,0),(2,1),(2,2),(2,-1),(2,-2),(0,-2),(-1,-2),(1,-2),(0,2),(-1,2),(1,2),(-1,1),(-1,-1),(1,1),(1,-1)]
  for dx,dy in move:
    if maze[x+dx][y+dy] <2:
      pos.append([x+dx,y+dy,hop+1])
      maze[x+dx][y+dy] = 2
  
else:
  print(-1)

Solution (Python):
from sys import *
from collections import deque
H, W = map(int, stdin.readline().split())
personY, personX = map(int, stdin.readline().split())
gH, gW = map(int, stdin.readline().split())

grid = [input() for x in range(H)]
visited = [[10**10] * W for i in range(H)]
options = deque([[personY-1, personX-1]])

visited[personY-1][personX-1] = 0
while(options):
    y,x = options.popleft()
    if y+1 < H and  grid[y+1][x] == ".":
        if visited[y+1][x] > visited[y][x]:
            options.appendleft((y+1, x))
            visited[y+1][x] = visited[y][x]

    if  y-1 >= 0 and grid[y-1][x] == ".":
        if visited[y-1][x] > visited[y][x]:
            options.appendleft((y-1, x))
            visited[y-1][x] = visited[y][x]

    if x+1 < W and grid[y][x+1] == ".":
        if visited[y][x+1] > visited[y][x]:
            options.appendleft((y, x+1))
            visited[y][x+1] = visited[y][x]

    if x-1 >= 0 and grid[y][x-1] == ".":
        if visited[y][x-1] > visited[y][x]:
            options.appendleft((y, x-1))
            visited[y][x-1] = visited[y][x]
   
    for Y,X in [(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)]:
       if x+X >= 0 and x+X < W and y+Y >= 0 and y+Y < H and grid[y+Y][x+X] == ".":
           if visited[y+Y][x+X] > visited[y][x] +1:
               options.append((y+Y, x+X))
               visited[y+Y][x+X] = visited[y][x]+1

print(-1 if visited[gH-1][gW-1] == 10**10 else visited[gH-1][gW-1] )

Solution (Python):
from sys import *
from collections import deque
H, W = map(int, stdin.readline().split())
personY, personX = map(int, stdin.readline().split())
gH, gW = map(int, stdin.readline().split())

grid = [list(stdin.readline().strip()) for x in range(H)]
visited = [ [10**10] * W for i in range(H)]
options = deque([[personY-1, personX-1]])

visited[personY-1][personX-1] = 0
while(options):
    y,x = options.popleft()
    if y+1 < H and  grid[y+1][x] == ".":
        if visited[y+1][x] > visited[y][x]:
            options.appendleft((y+1, x))
            visited[y+1][x] = visited[y][x]

    if  y-1 >= 0 and grid[y-1][x] == ".":
        if visited[y-1][x] > visited[y][x]:
            options.appendleft((y-1, x))
            visited[y-1][x] = visited[y][x]

    if x+1 < W and grid[y][x+1] == ".":
        if visited[y][x+1] > visited[y][x]:
            options.appendleft((y, x+1))
            visited[y][x+1] = visited[y][x]

    if x-1 >= 0 and grid[y][x-1] == ".":
        if visited[y][x-1] > visited[y][x]:
            options.appendleft((y, x-1))
            visited[y][x-1] = visited[y][x]
   
    for Y,X in [(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)]:
       if x+X >= 0 and x+X < W and y+Y >= 0 and y+Y < H and grid[y+Y][x+X] == ".":
           if visited[y+Y][x+X] > visited[y][x] +1:
               options.append((y+Y, x+X))
               visited[y+Y][x+X] = visited[y][x]+1

print(-1 if visited[gH-1][gW-1] == 10**10 else visited[gH-1][gW-1] )

Solution (Python):
from collections import *

def main():
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    s = ["
    s.append("
    for i in range(H):
        s.append("
    s.append("
    s.append("
    
    ans = [[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if s[i][j] == "
                ans[i][j] = -2
    ch += 1; cw += 1
    dh += 1; dw += 1
    ans[ch][cw] = 0
    
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    magic = [[-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]]
    
    mylist = deque([[ch,cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x,y = mylist.popleft()
        mylist2.append([x,y])
        for p,q in move:
            v1,v2 = x+p,y+q
            if ans[v1][v2] == -1:
                mylist.append([v1,v2])
                ans[v1][v2] = ans[x][y]
        if len(mylist) == 0:
            while len(mylist2) > 0:
                x2,y2 = mylist2.popleft()
                for v1,v2 in magic:
                    i,j = x2+v1,y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i,j])
    print(ans[dh][dw])
 
if __name__ == "__main__":
    main()

Solution (Python):
from collections import *

def main():
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    s = ["
    s.append("
    for i in range(H):
        s.append("
    s.append("
    s.append("
    
    ans = [[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if s[i][j] == "
                ans[i][j] = -2
    ch += 1; cw += 1
    dh += 1; dw += 1
    ans[ch][cw] = 0
    
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    magic = [
        [-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],\
        [-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],\
        [0,-2],[0,-1],[0,0],[0,1],[0,2],\
        [1,-2],[1,-1],[1,0],[1,1],[1,2],\
        [2,-2],[2,-1],[2,0],[2,1],[2,2]
        ]
    
    mylist = deque([[ch,cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x,y = mylist.popleft()
        mylist2.append([x,y])
        for p,q in move:
            v1,v2 = x+p,y+q
            if ans[v1][v2] == -1:
                mylist.append([v1,v2])
                ans[v1][v2] = ans[x][y]
        if len(mylist) == 0:
            while len(mylist2) > 0:
                x2,y2 = mylist2.popleft()
                for v1,v2 in magic:
                    i,j = x2+v1,y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i,j])
    print(ans[dh][dw])
 
if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=list(sys.stdin)

dirs=[-2,-1,0,1,2]
dist=[[10**6]*W for _ in range(H)]
dist[si][sj]=0
dq=deque()
dq.append((0,si,sj))
ok=False
while dq:
    k,i,j=dq.popleft()
    if k>dist[i][j]:
        continue
    if i==ti and j==tj:
        ok=True
        break
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='
                continue
            if abs(di)+abs(dj)==1:
                append=dq.appendleft
                nk=k
            else:
                append=dq.append
                nk=k+1
            if k>=dist[ni][nj]:
                continue
            dist[ni][nj]=nk
            append((nk,ni,nj))
      
if ok:
    ans=dist[ti][tj]
else:
    ans=-1

print(ans)

Solution (Python):
from collections import deque

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

ch,cw,dh,dw = ch-1,cw-1,dh-1,dw-1
S = [[""]*w for i in range(h)]

for i in range(h):
    s = input()
    for j in range(w):
        S[i][j] = s[j]
        
visited = [[-1]*w for _ in range(h)]

visited[ch][cw] = 0

INF = 10**9
dist = [[INF]*w for _ in range(h)]
Q = deque([])
Q.append([ch,cw])
dist[ch][cw] = 0

while Q:
    y,x = Q.popleft()
    d = dist[y][x]
    
    for i, j in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
      nx = x + i
      ny = y + j
      if (nx < 0 or nx >= w or ny < 0 or ny >= h): 
          continue
      if S[ny][nx] == "
          continue
      if dist[ny][nx] <= d:
          continue
      dist[ny][nx] = d
      Q.appendleft([ny,nx])
      
    
    for ey in range(-2,3):
        for ex in range(-2,3):
            nx = x + ex
            ny = y + ey
            if (nx < 0 or nx >= w or ny < 0 or ny >= h): 
              continue
            if S[ny][nx] == "
              continue
            if dist[ny][nx] <= d+1:     
              continue
            dist[ny][nx] = d+1
            Q.append([ny,nx])
      
ans = dist[dh][dw]

if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
import sys
from collections import deque

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=list(sys.stdin)

dirs=[-2,-1,0,1,2]
dist=[[float('inf')]*W for _ in range(H)]
dist[si][sj]=0
dq=deque()
dq.append((0,si,sj))
ok=False
while dq:
    k,i,j=dq.popleft()
    if k>dist[i][j]:
        continue
    if i==ti and j==tj:
        ok=True
        break
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='
                continue
            if abs(di)+abs(dj)==1:
                append=dq.appendleft
                nk=k
            else:
                append=dq.append
                nk=k+1
            if k>=dist[ni][nj]:
                continue
            dist[ni][nj]=nk
            append((nk,ni,nj))
      
if ok:
    ans=dist[ti][tj]
else:
    ans=-1

print(ans)

Solution (Python):
import sys
from collections import deque

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=list(sys.stdin)

dirs=[-2,-1,0,1,2]
dist=[[float('inf')]*W for _ in range(H)]
dist[si][sj]=0
dq=deque()
dq.append((0,si,sj))
ok=False
while dq:
    k,i,j=dq.popleft()
    if i==ti and j==tj:
        ok=True
        break
    if k>dist[i][j]:
        continue
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='
                continue
            if abs(di)+abs(dj)==1:
                append=dq.appendleft
                nk=k
            else:
                append=dq.append
                nk=k+1
            if k>=dist[ni][nj]:
                continue
            dist[ni][nj]=nk
            append((nk,ni,nj))
      
if ok:
    ans=dist[ti][tj]
else:
    ans=-1

print(ans)

Solution (Python):
import sys
from collections import deque

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=list(sys.stdin)

dirs=[-2,-1,0,1,2]
dist=[[float('inf')]*W for _ in range(H)]
dist[si][sj]=0
dq=deque()
dq.append((0,si,sj))
ok=False
while dq:
    k,i,j=dq.popleft()
    if i==ti and j==tj:
        ok=True
        break
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='
                continue
            if abs(di)+abs(dj)==1:
                append=dq.appendleft
                nk=k
            else:
                append=dq.append
                nk=k+1
            if k>=dist[ni][nj]:
                continue
            dist[ni][nj]=nk
            append((nk,ni,nj))
      
if ok:
    ans=dist[ti][tj]
else:
    ans=-1

print(ans)

Solution (Python):
import sys
from collections import deque

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=list(sys.stdin)

dirs=[-2,-1,0,1,2]
dist=[[float('inf')]*W for _ in range(H)]
dist[si][sj]=0
dq=deque()
dq.append((0,si,sj))
ok=False
while dq:
    k,i,j=dq.popleft()
    if i==ti and j==tj:
        ok=True
        break
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='
                continue
            if abs(di)+abs(dj)==1:
                append=dq.appendleft
                nk=k
            else:
                append=dq.append
                nk=k+1
            if k>=dist[ni][nj]:
                continue
            dist[ni][nj]=nk
            append((nk,ni,nj))
      
if ok:
    ans=dist[ti][tj]
else:
    ans=-1

print(ans)

Solution (Python):




import itertools as it
from collections import deque

def main(H, W, Ch, Cw, Dh, Dw, S):

    
    visited =  [[False for _ in range(W)] for __ in range(H)]

    
    root = (Ch, Cw)
    
    
    empty_while = True
    count = 0

    """DFS"""
    def DFS(node, block=set([])):
        def pick_next(node):
            h,w = node
            assert S[h][w]
            for next_h, next_w in [
                (h+1, w), 
                (h, w+1), 
                (h, w-1), 
                (h-1, w)  
            ]:
                try:
                    if next_w < 0 or next_h < 0:
                        raise IndexError
                    if not visited[next_h][next_w]:
                        if S[next_h][next_w]:
                            return next_h, next_w
                except IndexError:
                    pass
            return False

        
        visited[node[0]][node[1]] = True
        block.add(node)

        
        while pick_next(node):
            next_node = pick_next(node)
            if node:
                
                h, w = next_node
                visited[h][w] = True
                block.add(next_node)

                
                DFS(next_node, block)
        
        return frozenset(block)

    """BFS"""
    def BFS(node):
        def pick_next(node):
            h,w = node
            r = range(-2, 3)
            for h_offset, w_offset in it.product(r,r):
                next_h = h + h_offset
                next_w = w + w_offset
                try:
                    if next_w < 0 or next_h < 0:
                        raise IndexError
                    if not visited[next_h][next_w]:
                        if S[next_h][next_w]:
                            return next_h, next_w
                except IndexError:
                    pass
            return False

        queue = deque([])
        levels = {}

        start = DFS(node)
        if visited[Dh][Dw]: 
            return 0

        queue.append(start)  
        levels[start] = 0

        while queue:
            block = queue.popleft()
            
            if visited[Dh][Dw]:
                    return levels[next_block]

            for node in block:

                while pick_next(node):
                    next_node = pick_next(node)

                    
                    next_block = DFS(next_node, block=set([]))
                    queue.append(next_block)
                    levels[next_block] = levels[block] + 1


        return -1 

    node = root
    count = BFS(node)    
        
    print(count)
    pass

if __name__ == '__main__':
    H, W = list(map(int, input().split()))
    Ch, Cw = list(map(int, input().split()))
    Dh, Dw = list(map(int, input().split()))
    S = [[False for _ in range(W)] for __ in range(H)]

    for h in range(H):
        S_row = input()
        for w, s in enumerate(S_row):
            if s=='.':
                S[h][w] = True
            else:
                S[h][w] = False

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

    main(H, W, Ch, Cw, Dh, Dw, S)

Solution (Python):
import sys
from collections import deque


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    h, w = nm()
    Ch, Cw = nm()
    Dh, Dw = nm()
    S = [list(ns()) for _ in range(h)]
    pos = deque([(Ch, Cw)])
    cost = [[float('Inf')] * w for _ in range(h)]
    cost[Ch - 1][Cw - 1] = 0


    warp = deque([(Ch, Cw)])
    while pos:
        while pos:
            c_i, c_j = pos.pop()
            for i, j in [(1, 0), (0, -1), (-1, 0), (0, 1)]:
                if 0 <= c_i + i - 1 < h and 0 <= c_j + j - 1 < w \
                        and cost[c_i + i - 1][c_j + j - 1] > cost[c_i - 1][c_j - 1] \
                        and S[c_i + i - 1][c_j + j - 1] == '.':
                    cost[c_i + i - 1][c_j + j - 1] = cost[c_i - 1][c_j - 1]
                    pos.append((c_i + i, c_j + j))
                    warp.append((c_i + i, c_j + j))

        warp_sub = []
        while warp:
            c_i, c_j = warp.pop()
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if 0 <= c_i + i - 1 < h and 0 <= c_j + j - 1 < w \
                            and cost[c_i + i - 1][c_j + j - 1] > cost[c_i - 1][c_j - 1] + 1 \
                            and S[c_i + i - 1][c_j + j - 1] == '.':
                        cost[c_i + i - 1][c_j + j -
                                          1] = cost[c_i - 1][c_j - 1] + 1
                        pos.append((c_i + i, c_j + j))
                        warp_sub.append((c_i + i, c_j + j))

        warp.extend(warp_sub)

    print(cost[Dh - 1][Dw - 1] if cost[Dh - 1][Dw - 1] != float('Inf') else -1)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
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())
ma = [list(input()) for i in range(h)]
visit = [[-1 for i in range(w)] for j in range(h)]
cou = -1
p = [(0,1),(0,-1),(1,0),(-1,0)]
for i in range(h):
    for j in range(w):
        if visit[i][j] != -1 or ma[i][j] == "
            continue
        cou += 1
        visit[i][j] = cou
        d = deque()
        d.append((i,j))
        while d:
            now = d.popleft()
            for x , y in p:
                if 0 <= now[0]+x < h and 0 <= now[1]+y < w:
                    if ma[now[0]+x][now[1]+y] == "." and visit[now[0]+x][now[1]+y] == -1:
                        visit[now[0]+x][now[1]+y] = cou
                        d.append(((now[0]+x,now[1]+y)))

st = visit[ch][cw]
go = visit[dh][dw]
route = [set() for i in range(cou+1)]

for i in range(h):
    for j in range(w):
        if visit[i][j] == -1:
            continue
        for s in range(-2,3,1):
            for t in range(-2,3,1):
                if 0<=i+s<h and 0<=j+t<w:
                    if visit[i+s][j+t] != -1 and visit[i+s][j+t] != visit[i][j]:
                        route[visit[i][j]].add(visit[i+s][j+t])

kyori = [-1 for i in range(cou+1)]
kyori[st] = 0
d = deque()
d.append(st)

while d:
    now = d.popleft()
    for i in route[now]:
        if kyori[i] == -1:
            kyori[i] = kyori[now] + 1
            d.append(i)

print(kyori[go])

Solution (Python):
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())
maze=[input() for i in range(H)]
di=[[-1 for _ in range(W)] for _ in range(H)]
adj=[]
for i in range(-1,2):
  for j in range(-1,2):
    if i==0 or j==0:
      adj.append((i,j))
warp=[]
for i in range(-2,3):
  for j in range(-2,3):
    if (i,j) not  in adj:
      warp.append((i,j))
adj.remove((0,0))
from collections import deque
dq=deque([(CH,CW,0)])
while dq:
  h,w,d=dq.popleft()
  if 0<=h<H and 0<=w<W and di[h][w]<0 and maze[h][w]=='.':
    di[h][w]=d
  else:
    continue
  for i in range(len(adj)):
    dq.appendleft((h+adj[i][0],w+adj[i][1],d))
  for i in range(len(warp)):
    dq.append((h+warp[i][0],w+warp[i][1],d+1))
print(di[DH][DW])