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


import sys
from collections import deque
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("

"""
s
['
 '
 '
 '
 '
 '
"""  
ans = [[-1]*(w+4) for i in range(h+4)]

"""
ans
[
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1], 
	[-1, -1, -1, -1, -1, -1]]
"""

for i in range(h+4):
    for j in range(w+4):
        if s[i][j] == "
        	ans[i][j] = -2

"""
ans
[
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2]]
"""

ch += 1
cw += 1
dh += 1
dw += 1

ans[ch][cw] = 0

"""
ans
[
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2,  0, -1, -2, -2], 
	[-2, -2, -1, -1, -2, -2], 
	[-2, -2, -2, -2, -2, -2], 
	[-2, -2, -2, -2, -2, -2]]
"""
move = [[1,0],[-1,0],[0,1],[0,-1]]
"""
l = []
for i in range(-2,3):
	for j in range(-2,3):
		l.append([i,j])
lの中身が魔法の移動変位。magicにコピペ    
"""
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:
    y,x = mylist.popleft()
    mylist2.append([y, x])
    
    for p,q in move:
        vy,vx = y+p, x+q
        if ans[vy][vx]== -1:
            mylist.append([vy,vx])
            ans[vy][vx] =ans[y][x]
            
            if vy == dh and vx == dw:
                print(ans[vy][vx])
                sys.exit()
    
    
    if len(mylist) == 0:
        while len(mylist2) >0:
            y2, x2 = mylist2.popleft()
            for v1,v2 in magic:
                i,j = y2+v1, x2+v2
                if ans[i][j] == -1:
                    mylist.append([i,j])
                    ans[i][j] = ans[y2][x2] + 1
                    
                    if i == dh and j == dw:
                        print(ans[i][j])
                        sys.exit()
    
    

print(ans[dh][dw])

Solution (Python):
def walk(h, w, maze, que, step):
    search_area = ((h, w - 1), (h, w + 1), (h - 1, w), (h + 1, w))
    for i in range(4):
        search_cell = search_area[i]
        condition1 = search_cell[0] in range(H)
        condition2 = search_cell[1] in range(W)
        if condition1 and condition2:
            if maze[search_cell[0]][search_cell[1]] == '.':
                que.append(search_cell)
                maze[search_cell[0]][search_cell[1]] = step


def warp(h, w, maze, que, step):
    for i in range(-2, 3):
        for j in range(-2, 3):
            search_cell = (h + i, w + j)
            condition1 = search_cell[0] in range(H)
            condition2 = search_cell[1] in range(W)
            if condition1 and condition2:
                if maze[search_cell[0]][search_cell[1]] == '.':
                    que.append(search_cell)
                    maze[search_cell[0]][search_cell[1]] = step


H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [list(input()) for _ in range(H)]
                    
ques = [[(Ch - 1, Cw - 1)]]  
step = 0

i = 0
while True:
    try:
        walk(h=ques[step][i][0], w=ques[step][i][1], maze=maze, que=ques[step], step=step)
        i += 1
    except:
        step += 1
        ques.append([])
        break

while True:
    for cell in ques[step - 1]:
        warp(h=cell[0], w=cell[1], maze=maze, que=ques[step], step=step)
    if ques[step] == []:
        break
    else:
        i = 0
        while True:
            try:
                walk(h=ques[step][i][0], w=ques[step][i][1], maze=maze, que=ques[step], step=step)
                i += 1
            except:
                step += 1
                ques.append([])
                break

if type(maze[Dh - 1][Dw - 1]) == int:
  print(maze[Dh - 1][Dw - 1])
else:
  print(-1)

Solution (Python):

from collections import deque
from math import inf


def bfs(maze, visited, Ch, Cw, Dh, Dw, H, W):
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    while queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j in range(-2, 3):
            for k in range(-2, 3):
                new_y, new_x = y + j, x + k
                if 0 <= new_y < H and 0 <= new_x < W:
                    if maze[new_y][new_x] == "." and j**2 + k**2 == 1 and visited[y][x] < visited[new_y][new_x]:
                        visited[new_y][new_x] = visited[y][x]
                        queue.appendleft([new_y, new_x])
                    elif maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]
    visited = [[inf] * W for i in range(H)]

    dist = bfs(maze, visited, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)
    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
from collections import deque
from math import inf


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


def bfs(maze, Ch, Cw, Dh, Dw, H, W):
    visited = [[inf] * W for i in range(H)]
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[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 queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                visited[new_y][new_x] = visited[y][x]
                queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]

    dist = bfs(maze, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)

    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()

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

maze = [input() for _ in range(H)]
visit = [[-1] * W for _ in range(H)]
visit[Ch][Cw] = 0

DQ = deque([[Ch, Cw]])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

while DQ:
  px, py = DQ.popleft()
  if px==Dh and py==Dw:
    print(visit[px][py])
    exit()
  
  for i in range(4):
    nx = px + dx[i]
    ny = py + dy[i]
    if 0<=nx<=H-1 and 0<=ny<=W-1 and maze[nx][ny]=="." and  (visit[nx][ny]>visit[px][py] or visit[nx][ny]==-1):
      visit[nx][ny] = visit[px][py]
      DQ.appendleft([nx, ny])
    
  for i in range(-2, 3):
    for j in range(-2, 3):
      if i==j==0:
        continue
      nx = px + i
      ny = py + j
      if 0<=nx<=H-1 and 0<=ny<=W-1 and maze[nx][ny]=="." and visit[nx][ny]==-1:
        visit[nx][ny] = visit[px][py] + 1
        DQ.append([nx, ny])

print(-1)

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

maze = [list(input()) for _ in range(H)]
visit = [[-1] * W for _ in range(H)]
visit[Ch][Cw] = 0

DQ = deque([(Ch, Cw)])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

while DQ:
    px, py = DQ.popleft()
    if (px, py) == (Dh, Dw):
        print(visit[px][py])
        exit()

    for i in range(4):
        nx = px + dx[i]
        ny = py + dy[i]
        if 0<=nx<=H-1 and 0<=ny<=W-1 and maze[nx][ny]=="." and (visit[nx][ny]>visit[px][py] or visit[nx][ny]==-1):
            visit[nx][ny] = visit[px][py]
            DQ.appendleft((nx, ny))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == j == 0:
                continue

            nx = px + i
            ny = py + j

            if 0<=nx<=H-1 and 0<=ny<=W-1 and maze[nx][ny]=="." and visit[nx][ny]==-1:
                visit[nx][ny] = visit[px][py] + 1
                DQ.append((nx, ny))

    
    

print(-1)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
INF=10**7

queue = deque()

cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    if d>cost[x][y]:
        continue
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="
            cost[nx][ny]=d
            queue.appendleft([nx,ny,d])

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])

if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)

Solution (Python):
import sys
input = sys.stdin.readline

from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
INF=10**7

queue = deque()

cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    if d>cost[x][y]:
        continue
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="
            cost[nx][ny]=d
            queue.appendleft([nx,ny,d])

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])

if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
INF=10**7

queue = deque()

cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="
            cost[nx][ny]=d
            queue.appendleft([nx,ny,d])
            
            

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])
            
            


if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)

Solution (Python):
from random import randrange

import sys
input = sys.stdin.readline
from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]













INF=10**7

queue = deque()

cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="
            cost[nx][ny]=d
            queue.appendleft([nx,ny,d])
            
            

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])
            
            


if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)

Solution (Python):
"""
01BFS: ステップ数が多ければ後ろに持っていく
"""
def main():
    from collections import deque
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Dh,Dw = map(int,input().split())
    maze = [list(input()) for _ in range(H)]

    que = deque([(Ch-1,Cw-1,0)])
    adjectns = [(1,0),(0,1),(-1,0),(0,-1)]
    for _ in range(100000000):
        if not que:
            break
        h,w,step = que.popleft()
        if h == Dh-1 and w == Dw-1:
            print(step)
            exit()
        else:
            if maze[h][w] == ".":
                maze[h][w] = step
                for a,b in adjectns:
                    x = h + a
                    y = w + b
                    if 0<=x<H and 0<=y<W and maze[x][y]==".":
                        que.appendleft((x,y,step))
                for i in range(-2,3):
                    for j in range(-2,3):
                        x = h+i
                        y = w+j
                        if 0<=x<H and 0<=y<W and maze[x][y]==".":
                            que.append((x,y,step+1))
    print(-1)
main()

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

s = []
for i in range(h):
  t = input()
  s.append(t)

dx = [1,0,-1,0]
dy = [0,1,0,-1]

queue = deque([[ch,cw]])
visited = [[1000000 for i in range(w)] for j in range(h)]
visited[ch][cw] = 0
while queue:
  l,m = queue.popleft()
  d = visited[l][m]
  for k in range(4):
    x = l + dx[k]
    y = m + dy[k]
    if x < 0 or y < 0 or x >= h or y >= w or visited[x][y] <= d or s[x][y] == "
      continue
    visited[x][y] = d
    queue.appendleft([x,y])
  for i in range(-2,3):
    for j in range(-2,3):
      if (i== 1 and j == 0)or(i==-1 and j == 0)or(i==0 and j == 1)or(i==0 and j==-1)or(i==0 and j==0):
        continue
      x = l + i
      y = m + j
      if x < 0 or y < 0 or x >= h or y >= w or visited[x][y] <= d+1 or s[x][y] == "
        continue
      visited[x][y] = d + 1
      queue.append([x,y])
  
if visited[dh][dw] == 1000000:
  print (-1)
else:
  print (visited[dh][dw])

Solution (Python):
from sys import stdin
from queue import Queue
from math import ceil
inp = lambda : stdin.readline().strip()

X = [0,1,0,-1]
Y = [-1,0,1,0]
def isValid(x,y):
    if x >= 0 and y >= 0 and x < h  and y < w:
        return True
    return False


def dfs_iter(x,y):
    stack = [(x,y)]
    while stack:
        x,y = stack.pop()
        if isValid(x,y) and visited[x][y] == -1 and  maze[x][y] != '
            visited[x][y] = curr
            for i,j in zip(X,Y):
                if isValid(x+i,y+j) and visited[x+i][y+j] == -1  and maze[x+i][y+j] != '
                    stack.append((x+i,y+j))
def bfs(n):
    stack = Queue()
    stack.put(n)
    depths = Queue()
    depths.put(0)
    ans = 10**9 + 7
    while not stack.empty():
        node = stack.get()
        depth = depths.get()
        if not visited2[node]:
            visited2[node] = True
            if node == visited[dh-1][dw-1]:
                ans = min(ans,depth)
            for child in adj[node]:
                if not visited2[child]:
                    stack.put(child)
                    depths.put(depth+1)
    if ans == 10**9 + 7:
        return -1
    return ans


h, w = [int(x) for x in inp().split()]
ch,cw = [int(x) for x in inp().split()]
dh, dw = [int(x) for x in inp().split()]
visited  = [[-1]*w for x in range(h)]

maze = []
adj = [set() for i in range(ceil(h*w/2))]
visited2 = [False]*(ceil(h*w/2))
for i in range(h):
    maze.append(list(inp()))

curr = 0
ans = []
for i in range(h):
    for j in range(w):
        if visited[i][j] == -1 and maze[i][j] != '
            dfs_iter(i,j)
            curr += 1
for i in range(h):
    for j in range(w):
        if maze[i][j] != '
            for k in range(-2,3):
                for l in range(-2,3):
                    if not (k==l and l == 0):
                        if isValid(i+k,j + l) and visited[i][j] != visited[i+k][j+l] and maze[i+k][j+l] != '
                            adj[visited[i][j]].add(visited[i+k][j+l])

print(bfs(visited[ch-1][cw-1]))

Solution (Python):
from collections import deque



R, C = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())

sy, sx, gy, gx = sy-1, sx-1, gy-1, gx-1
maze = [list(input()) for i in range(R)]
d = deque()
ds = deque()
maze[sy][sx] = 0
d.append([sy, sx])
ds.append([sy, sx])
while(d or ds):
  while(d):
    [y, x] = d.popleft()
    ds.append([y, x])
    if (y, x) == (gy, gx):
      print(maze[gy][gx])
      exit()
    for [dy, dx] in [[1,0], [-1,0], [0,1], [0,-1]]:
      ny = y + dy
      nx = x + dx
      if  R > ny and ny >= 0 and C > nx and nx >= 0 and maze[ny][nx] == ".":
        maze[ny][nx] = maze[y][x]
        d.append([ny, nx])
        ds.append([ny, nx])

  while(ds):   
    [y, x] = ds.popleft()
    for [dy, dx] 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]]:
      ny = y + dy
      nx = x + dx
      if  R > ny and ny >= 0 and C > nx and nx >= 0 and maze[ny][nx] == ".":
        maze[ny][nx] = maze[y][x]+1
        d.append([ny,nx])
        
        
print(-1)

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)


warp = [[dy, dx] for dy in range(-2, 3) for dx in range(-2, 3) if abs(dy) + abs(dx) > 1]

def main():
    H, W = LI()
    CH, CW = LI1()
    DH, DW = LI1()
    S = SR(H)
    dist = make_list(H, W, default=-1)

    q = deque()
    dist[CH][CW] = 0
    q.append((0, CH, CW))

    while q:
        d, y, x = q.popleft()

        for dy, dx in dire:
            newx, newy = x + dx, y + dy
            if 0 <= newx < W and 0 <= newy < H and S[newy][newx] == ".":
                if dist[newy][newx] == -1 or dist[newy][newx] > d:
                    dist[newy][newx] = d
                    q.appendleft((d, newy, newx))

        for dy, dx in warp:
            newx, newy = x + dx, y + dy
            if 0 <= newx < W and 0 <= newy < H and S[newy][newx] == ".":
                if dist[newy][newx] == -1 or dist[newy][newx] > d + 1:
                    dist[newy][newx] = d + 1
                    q.append((d + 1, newy, newx))

    print(dist[DH][DW])







if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(lambda x: x - 1, map(int, input().split()))
Dh, Dw = map(lambda x: x - 1, map(int, input().split()))
S = []
already = []
yet = 1000000
for i in range(H):
    S.append(input())
    already.append([yet] * W)
queue = deque()
queue.append((Cw, Ch, 0))
already[Ch][Cw] = 0
answer = -1
while len(queue) > 0:
    
    
    x, y, cost = queue.popleft()
    
    if x == Dw and y == Dh:
        answer = cost
        break
    for i in range(-2, 3):
        for j in range(-2, 3):
            new_x, new_y = (x + i, y + j)
            
            if new_x < 0 or new_y < 0 or W <= new_x or H <= new_y:
                continue
            
            if new_x == x and new_y == y:
                continue
            
            if S[new_y][new_x] == '
                continue
            
            if already[new_y][new_x] <= cost:
                continue
            if (i == 0 and j == -1) \
            or (i == 0 and j == 1) \
            or (i == 1 and j == 0) \
            or (i == -1 and j == 0):
                queue.appendleft((new_x, new_y, cost))
                already[new_y][new_x] = cost
            else:
                queue.append((new_x, new_y, cost+1))
                already[new_y][new_x] = cost+1
print(answer)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**6)


def main(input, print):
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    move2 = [(-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())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    table = [input() for _ in range(H)]
    path = [[-1 for _ in range(W)] for _ in range(H)]

    que = deque()
    path[Ch-1][Cw-1] = 0
    que.append((Ch-1, Cw-1))
    while que:
        y, x = que.popleft()
        cnt = path[y][x]

        for k in range(len(move)):
            i, j = move[k]
            nx = x+i
            ny = y+j
            if ny < 0 or nx < 0 or ny >= H or nx >= W:
                continue
            if table[ny][nx] == '
                continue
            if path[ny][nx] == -1 or path[ny][nx] > cnt:
                path[ny][nx] = cnt
                que.appendleft((ny, nx))

        for k in range(len(move2)):
            i, j = move2[k]
            nx = x+i
            ny = y+j
            if ny < 0 or nx < 0 or ny >= H or nx >= W:
                continue
            if table[ny][nx] == '
                continue
            if path[ny][nx] == -1 or path[ny][nx] > cnt+1:
                path[ny][nx] = cnt+1
                que.append((ny, nx))
    if(path[Dh-1][Dw-1] == -1):
        print(-1)
    else:
        print(path[Dh-1][Dw-1])


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Solution (Python):
import heapq

def solve():
    H, W = map(int, input().split())
    sy, sx = map(lambda x: int(x) - 1, input().split())
    ty, tx = map(lambda x: int(x) - 1, input().split())
    graph = [input() for i in range(H)]
    INF = 10 ** 9
    dist = [INF] * (H * W)
    que = []

    def push(y, x, d):
        v = y * W + x
        if dist[v] <= d:
            return
        dist[v] = d
        heapq.heappush(que, (d, v))

    push(sy, sx, 0)

    while que:
        d, v = heapq.heappop(que)
        y, x = divmod(v, W)
        if dist[v] < d:
            continue
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny, nx = y + dy, x + dx
                if ny < 0 or ny >= H or nx < 0 or nx >= W:
                    continue
                if graph[ny][nx] == '
                    continue
                push(ny, nx, d + (abs(dy) + abs(dx) > 1))

    t = ty * W + tx
    if dist[t] == INF:
        return -1
    else:
        return dist[t]

print(solve())

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

s = [list(input()) for _i in range(h)]

bord = [[float('inf') for _i in range(w)] for _j in range(h)]
bord[ch-1][cw-1] = 0

dh, dw = dh-1, dw-1
from collections import deque
q = deque([[ch-1, cw-1]])
while q:
    x, y = q.pop()
    for i, j in [[1,0], [0, 1], [-1, 0], [0, -1]]:
        if 0 <= x+i and 0 <= y+j and x+i < h and y+j < w:
            if s[x+i][y+j]=='.':
                if bord[x][y] < bord[x+i][y+j]:
                    bord[x+i][y+j] = bord[x][y]
                    q.append([x+i, y+j])
            else:
                for n in range(-2, 3):
                    for m in range(-2, 3):
                        if n==0 and m==0:
                            continue
                        if 0 <= x+n and 0 <= y+m and x+n < h and y+m < w:
                            if s[x+n][y+m] == '.':
                                if bord[x][y]+1 < bord[x+n][y+m]:
                                    bord[x+n][y+m] = bord[x][y] + 1
                                    q.appendleft([x+n, y+m])

if bord[dh][dw]==float('inf'):
    print(-1)
else:
    print(bord[dh][dw])

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())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  


walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  
    for dx, dy in warp:  
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Solution (Python):
from collections import deque


def is_inside(x, y, W, H, G):
    return (x <= H-1 and y <= W-1 and
            x >= 0 and y >= 0 and
            G[x][y] != "


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

    G = [list(input()) for _ in range(H)]
    INF = int(1e9)
    q = deque()
    q.append((Cx-1, Cy-1, -INF, Cx-1, Cy-1))
    warps = [[INF] * W for _ in range(H)]
    while q:
        x, y, warp, prev_x, prev_y = q.popleft()

        if warps[x][y] != INF:
            continue

        num_warps = warps[prev_x][prev_y] + warp
        warps[x][y] = num_warps

        for step_x in range(-2, 3):
            for step_y in range(-2, 3):
                x_, y_ = x+step_x, y+step_y
                if is_inside(x_, y_, W, H, G) and warps[x_][y_] == INF:
                    if ((max(abs(step_x), abs(step_y)) == 1) and
                            (min(abs(step_x), abs(step_y)) == 0)):

                        q.appendleft((x_, y_, 0, x, y))
                    else:
                        q.append((x_, y_, 1, x, y))

    ans = warps[Dx-1][Dy-1]
    if ans == INF:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

_INPUT = """\
4 5
1 2
2 5




"""

def main():
    H, W = map(int, input().split())
    c = tuple(map(int, input().split()))
    d = tuple(map(int, input().split()))
    d_y = d[0]-1
    d_x = d[1]-1
    s = [list(input()) for i in range(H)]

    visited = [[-1]*W for j in range(H)]
    visited[c[0]-1][c[1]-1] = 0

    main_q = deque()
    main_q.append((c[0]-1,c[1]-1))
    magic_q = deque()
    direction = [(0,1),(1,0),(-1,0),(0,-1)]

    
    while main_q:
        y, x = main_q.popleft()
        magic_q.append((y,x))

        for i in range(4):
            moved_y = y + direction[i][0]
            moved_x = x + direction[i][1]

            if moved_y < 0 or H -1 < moved_y or moved_x < 0 or W -1 < moved_x:
                continue
            if s[moved_y][moved_x] == '
                continue
            if s[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
                main_q.append((moved_y, moved_x))
                visited[moved_y][moved_x] = visited[y][x]

        if not main_q:
            while magic_q:
                y, x = magic_q.popleft()

                for k in range(-2,3):
                    for l in range(-2,3):
                        moved_y = y + k
                        moved_x = x + l

                        if moved_y < 0 or H -1 < moved_y or moved_x < 0 or W -1 < moved_x:
                            continue
                        if s[moved_y][moved_x] == '
                            continue
                        if s[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
                            main_q.append((moved_y, moved_x))
                            visited[moved_y][moved_x] = visited[y][x] + 1
    print(visited[d_y][d_x])


if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    
    main()