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

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

inf = 10 ** 10
cost = [[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()
cost[ch][cw] = 0
q.append([ch, cw, 0])

while q:
    x, y, c = 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 cost[nx][ny] > c:
            cost[nx][ny] = c
            q.appendleft([nx, ny, c])

    for dx, dy in warp:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == '.' and cost[nx][ny] > c + 1:
            cost[nx][ny] = c + 1
            q.append([nx, ny, c + 1])

ans = cost[dh][dw] if cost[dh][dw] != inf else -1
print(ans)

Solution (Python):
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 = [list(input()) for i in range(H)]
S[Ch][Cw] = "

ans = 0
warp_after = [[Ch, Cw]]
warp_before = []
queue1 = [[1,0],[-1,0],[0,1],[0,-1]]
queue2 = [
        [-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]
    ]

def nowRange(now):
    r = []
    for i in queue1:
        j = now[0] + i[0]
        k = now[1] + i[1]
        if H > j > -1 and W > k > -1:
            if S[j][k] == "
                pass
            elif j == Dh and k == Dw:
                print(ans)
                exit()
            elif S[j][k] == ".":
                S[j][k] = "
                r = r + [[j,k]]
    return r


def stepRange(trout):
    r = []
    for i in trout:
        r = r + nowRange(i)
    if len(r) != 0:
        return r + stepRange(r)
    else:
        return []


def nowWarp(now):
    r = []
    for i in queue2:
        j = now[0] + i[0]
        k = now[1] + i[1]
        if H > j > -1 and W > k > -1:
            if S[j][k] == "
                pass
            elif j == Dh and k == Dw:
                print(ans)
                exit()
            elif S[j][k] == ".":
                S[j][k] = "
                r = r + [[j,k]]
            
    return r


def warpRange(trout):
    r = []
    for i in trout:
        r = r + nowWarp(i)
    if len(r) != 0:
        return r
    else:
        print(-1)
        exit()


while True:
    warp_before = stepRange(warp_after) + warp_after
    ans += 1
    warp_after = warpRange(warp_before)

Solution (Python):
import heapq

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())
s, t = sy * W + sx, ty * W + tx
graph = [input() for _ in range(H)]

INF = 1 << 30
dist = [INF] * (H * W)
que = []

def push(v, d):
    if(dist[v] <= d):
        return
    dist[v] = d
    heapq.heappush(que, (d, v))

def move(ny, nx, d):
    if ny < 0 or ny >= H or nx < 0 or nx >= W:
        return
    if graph[ny][nx] == '.':
        push(ny * W + nx, d)

push(s, 0)

while que:
    d, v = heapq.heappop(que)
    if d > dist[v]:
        continue
    if v == t:
        break
    y, x = divmod(v, W)
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            move(y + dy, x + dx, d + (abs(dy) + abs(dx) > 1))

if dist[t] == INF:
    print(-1)
else:
    print(dist[t])

Solution (Python):
import sys

INF = 10 ** 18
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict


def li():
    return [int(x) for x in input().split()]


from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

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

def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch - 1][Cw - 1] = 0
    que = deque([])
    que.append((Cw - 1, Ch - 1))

    while que:
        
        
        x, y = que.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue
            if S[ny][nx] != '.':
                continue
            
            if costmap[ny][nx] == -1 or costmap[y][x] < costmap[ny][nx]:
                
                que.appendleft((nx, ny))
                costmap[ny][nx] = costmap[y][x]
        
        for i in range(x - 2, x + 3):
            for j in range(y - 2, y + 3):
                nx, ny = i, j
                
                if nx < 0 or nx >= W or ny < 0 or ny >= H:
                    continue
                if S[ny][nx] != '.':
                    continue
                
                if costmap[ny][nx] == -1 or costmap[y][x] + 1 < costmap[ny][nx]:
                    
                    que.append((nx, ny))
                    costmap[ny][nx] = costmap[y][x] + 1
    return costmap


costmap = bfs()

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

Solution (Python):
import sys

INF = 10 ** 18
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict


def li():
    return [int(x) for x in input().split()]


from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

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


def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch - 1][Cw - 1] = 0
    que = deque([])
    que.append((Cw, Ch))

    while que:
        
        
        x, y = que.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx <= 0 or nx > W or ny <= 0 or ny > H:
                continue
            if S[ny - 1][nx - 1] != '.':
                continue
            
            if costmap[ny - 1][nx - 1] == -1 or costmap[y - 1][x - 1] < costmap[ny - 1][nx - 1]:
                
                que.appendleft((nx, ny))
                costmap[ny - 1][nx - 1] = costmap[y - 1][x - 1]
        
        for i in range(x - 2, x + 3):
            for j in range(y - 2, y + 3):
                nx, ny = i, j
                
                if nx <= 0 or nx > W or ny <= 0 or ny > H:
                    continue
                if S[ny - 1][nx - 1] != '.':
                    continue
                
                if costmap[ny - 1][nx - 1] == -1 or costmap[y - 1][x - 1] + 1 < costmap[ny - 1][nx - 1]:
                    
                    que.append((nx, ny))
                    costmap[ny - 1][nx - 1] = costmap[y - 1][x - 1] + 1
    return costmap


costmap = bfs()

print(costmap[Dh - 1][Dw - 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 i in range(h)]
 

dx=[1,0,-1,0]
dy=[0,1,0,-1]
def bfs():
  maze=[[-1]*w for i in range(h)]
  maze[ch-1][cw-1]=0
  qu=deque([])
  qu.append((cw-1,ch-1))
  magic=0
  
  while qu:
    x,y=qu.popleft()
    for i in range(4):
      nx=dx[i]+x
      ny=dy[i]+y
      if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]):
        qu.appendleft((nx,ny))
        maze[ny][nx]=maze[y][x]
    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        nx=i
        ny=j
        if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]+1):
          qu.append((nx,ny))
          maze[ny][nx]=maze[y][x]+1
  return maze
    
maze = bfs()
print(maze[dh-1][dw-1])

Solution (Python):
from collections import deque

h, w = map(int, input().split())
c = list(map(int, input().split()))
d = list(map(int, input().split()))
s = [list(input()) for _ in range(h)]

c = [i-1 for i in c]
d = [i-1 for i in d]

t0 = [(0, 1), (0, -1), (1, 0), (-1, 0)]
t1 = []
for i in range(-2, 3):
    for j in range(-2, 3):
        t1.append((i, j))
for i in t0:
    t1.remove(i)
t1.remove((0, 0))

check = [[-1]*w for _ in range(h)]
q = deque()
q.appendleft((c[0], c[1], 0))

while q:
    y, x, b = q.pop()
    if x == d[1] and y == d[0]:
        print(b)
        exit()
    if check[y][x] == -1:
        check[y][x] = b
        for dy, dx in t0:
            ydy, xdx = y+dy, x+dx
            if (0 <= xdx < w) and (0 <= ydy < h):
                if s[ydy][xdx] == '.' and check[ydy][xdx] == -1:
                    q.append((ydy, xdx, b))
        for dy, dx in t1:
            ydy, xdx = y+dy, x+dx
            if (0 <= xdx < w) and (0 <= ydy < h):
                if s[ydy][xdx] == '.' and check[ydy][xdx] == -1:
                    q.appendleft((ydy, xdx, b+1))
print(-1)

Solution (Python):
H,W = map(int,input().split())

start = tuple(map(lambda x:x - 1, map(int,input().split())))
goal = tuple(map(lambda x:x - 1, map(int,input().split())))

S = [input() for i in range(H)]

from collections import deque
q = deque([])


q.append([start[0], start[1], 0])
INF = 10 ** 10
cost = [[INF] * W for i in range(H)]

while q:
  y,x,c = q.popleft()
  if S[y][x] == "
    continue
  if cost[y][x] <= c:
    continue
  cost[y][x] = c
  for i in range(-2,3):
    for j in range(-2,3):
      if i == 0 and j == 0:
        continue
      if 0 <= y + i < H and 0 <= x + j < W:
        if abs(i) + abs(j) == 1:
          q.appendleft([y + i, x + j, c])
        else:
          q.append([y + i, x + j, c + 1])

if cost[goal[0]][goal[1]] == INF:
  print(-1)
else:
  print(cost[goal[0]][goal[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 -= 1
cw -= 1
dh -= 1
dw -= 1

maze = []
for i in range(H):
    h = list(input())
    maze.append(h)

dist = [[float("inf") for _ in range(W)] for _ in range(H)]
dist[ch][cw] = 0

queue = deque([(ch, cw, 0)])

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

    if y == dh and x == dw:
        print(d)
        exit()

    for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y + i, x + j
        if 0 <= new_y < H and 0 <= new_x < W:
            if maze[new_y][new_x] != '
                if dist[new_y][new_x] > d:
                    dist[new_y][new_x] = d
                    queue.appendleft((new_y, new_x, d))

    for i in range(-2, 3):
        for j in range(-2, 3):
            new_y, new_x = y + i, x + j
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x] != '
                    if dist[new_y][new_x] > d+1:
                        dist[new_y][new_x] = d+1
                        queue.append((new_y, new_x, d+1))

print(-1)

Solution (Python):
from collections import deque
import sys

h, w = map(int, input().split())
sy, sx = map(lambda x: int(x)-1, input().split())
gy, gx = map(lambda x: int(x)-1, input().split())
S = [[0 if s == '.' else -1 for s in input()] for _ in range(h)]

d = deque([(sy, sx)])
cur = 1
while True:
    visited = set()
    while d:
        y, x = d.pop()
        visited.add((y, x))
        S[y][x] = cur
        if (y, x) == (gy, gx):
            print(cur-1)
            sys.exit()
        for dyi, dxi in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            if 0<=y+dyi<h and 0<=x+dxi<w and S[y+dyi][x+dxi] == 0:
                d.append((y+dyi, x+dxi))

    for y, x in visited:
        for dyi in range(-2, 3):
            for dxi in range(-2, 3):
                if 0<=y+dyi<h and 0<=x+dxi<w and S[y+dyi][x+dxi] == 0:
                    d.append((y+dyi, x+dxi))
    if not d:
        print(-1)
        sys.exit()
    cur += 1

Solution (Python):
from collections import deque


def main():
    INF = 10 ** 7
    H, W = list(map(int, input().split()))
    CH, CW = list(map(lambda x: int(x) - 1, input().split()))
    DH, DW = list(map(lambda x: int(x) - 1, input().split()))
    S = [input() for _ in range(H)]
    if S[DH][DW] == '
        print(-1)
        return
    
    walk_list = [[1, 0], [-1, 0], [0, -1], [0, 1]]
    
    warp_list = [[-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]]
    
    cnt = [[INF for _ in range(W)] for _ in range(H)]

    warp_checked = [[0 for _ in range(W)] for _ in range(H)]
    warp_que = deque([(DH, DW)])
    c = 0
    while len(warp_que) > 0:
        
        walk_que = deque()
        while len(warp_que) > 0:
            h, w = warp_que.pop()
            cnt[h][w] = c
            walk_que.append((h, w))
            tmp_walk_que = deque([(h, w)])
            while len(tmp_walk_que) > 0:
                h, w = tmp_walk_que.pop()
                for dh, dw in walk_list:
                    nh, nw = h + dh, w + dw
                    if 0 <= nh < H and 0 <= nw < W and \
                        S[nh][nw] == '.' and cnt[nh][nw] == INF:
                        cnt[nh][nw] = c
                        tmp_walk_que.append((nh, nw))
                        walk_que.append((nh, nw))
        
        while len(walk_que) > 0:
            h, w = walk_que.pop()
            for dh, dw in warp_list:
                nh, nw = h + dh, w + dw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and \
                    warp_checked[nh][nw] == 0 and cnt[nh][nw] == INF:
                    warp_checked[nh][nw] = 1
                    warp_que.append((nh, nw))
        c += 1

    if cnt[CH][CW] == INF:
        print(-1)
    else:
        print(cnt[CH][CW])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

h,w = na()
ch,cw = na()
dh,dw = na()
ch,cw = ch-1,cw-1
dh,dw = dh-1,dw-1
s = []
for i in range(h):
  s.append(ns())

from collections import deque

g = [[10000000000]*w for i in range(h)]
g[ch][cw] = 0
d = deque([(ch,cw,0)])

while d:
  x,y,num = d.popleft()
  pq = [(-1,0),(0,1),(1,0),(0,-1)]
  for p,q in pq:
    if not (0<=x+p<h and 0<=y+q<w):
      continue
    u = s[x+p][y+q]
    if u == '.':
      if num < g[x+p][y+q]:
        g[x+p][y+q] = num
        d.appendleft((x+p,y+q,num))

  for i in range(-2,3):
    for j in range(-2,3):
      if not (0<=x+i<h and 0<=y+j<w):
        continue
      p = s[x+i][y+j]
      if p == '.':
        if num+1 < g[x+i][y+j]:
          g[x+i][y+j] = num+1
          d.append((x+i,y+j,num+1))

ans = g[dh][dw]

print('-1' if ans == 10000000000 else 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())

maze = ["
maze.append("

for i in range(H):
    maze.append("
maze.append("
maze.append("

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

for i in range(H+4):
    for j in range(W+4):
        if maze[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]]
warp = [[-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]]

movelst = deque([[Ch, Cw]])
movelst2 = deque([])

while len(movelst) > 0:
    x, y = movelst.popleft()
    movelst2.append([x, y])
    for p, q in move:
        v1, v2 = x+p, y+q
        if ans[v1][v2] == -1:
            movelst.append([v1, v2])
            ans[v1][v2] = ans[x][y]
    
    if len(movelst) == 0:
        while len(movelst2) > 0:
            x2, y2 = movelst2.popleft()
            for v1, v2 in warp:
                i, j = x2+v1, y2+v2
                if ans[i][j] == -1:
                    ans[i][j] = ans[x2][y2] + 1
                    movelst.append([i, j])

print(ans[Dh][Dw])

Solution (Python):
from collections import deque

h,w = map(int,input().split())
cy,cx = map(int,input().split())
dy,dx = map(int,input().split())
s = [input() for j in range(h)]

chk = [[-1]*(w) for _ in range(h)]

seg = [[] for _ in range(h*w)]

div = 0

vx = [0,1,0,-1]
vy = [1,0,-1,0]

q = deque()
q.appendleft([cy-1,cx-1,0])

while len(q) > 0:
    y,x,div = q.popleft()
    
    if chk[y][x] != -1:
        continue
    chk[y][x] = div
    for i in range(4):
        y_n = y + vy[i]
        x_n = x + vx[i]
        if y_n >= 0 and y_n <= h-1 and x_n >= 0 and x_n <= w-1:
            if s[y_n][x_n] == '.':
                if chk[y_n][x_n] == -1:
                    q.appendleft([y_n,x_n,div])
                    
    for i in range(5):
        for j in range(5):
            y_n = y + (-2+i)
            x_n = x + (-2+j)
            
            if y_n >= 0 and y_n <= h-1 and x_n >= 0 and x_n <= w-1:
                if s[y_n][x_n] == '.':
                    if chk[y_n][x_n] == -1:
                        q.append([y_n,x_n,div+1])
                        
                        
print(chk[dy-1][dx-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 -= 1
Cw -= 1
Dh -= 1
Dw -= 1

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "
                continue
            if not reached[nh][nw] > d + 1:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

Solution (Python):
import sys
import collections
import itertools


def resolve(in_):
    H, W = map(int, next(in_).split())
    Ch, Cw = map(int, next(in_).split())
    Dh, Dw = map(int, next(in_).split())

    ch = Ch - 1
    cw = Cw - 1
    dh = Dh - 1
    dw = Dw - 1
    S = tuple(s.strip() for s in in_)
    wall_i = ord(b'
    
    used = [[False for h in range(W)] for w in range(H)]

    qu = collections.deque()
    qu.append((ch, cw))
    for ans in itertools.count():
        if not qu:
            return -1
        
        roads = []
        
        while qu:
            h, w = qu.popleft()
            if used[h][w]:
                continue
            
            used[h][w] = True
            roads.append((h, w))
            if dh == h and dw == w:
                return ans

            for h0, w0 in ((h - 1, w), (h + 1, w), (h, w - 1), (h, w + 1)):
                if not (0 <= h0 < H and 0 <= w0 < W):
                    continue
                if S[h0][w0] == wall_i:
                    continue
                qu.append((h0, w0))
        
        for h1, w1 in roads:
            for h2 in range(h1 - 2, h1 + 3):
                for w2 in range(w1 - 2, w1 + 3):
                    if not (0 <= h2 < H and 0 <= w2 < W):
                        continue
                    if used[h2][w2]:
                        continue
                    if S[h2][w2] == wall_i:
                        continue
                    qu.append((h2, w2))

    return ans

def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


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 = [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())
ARR = []

for i in range(H):
    ARR.append(input())




def calculate(h, w, ch, cw, dh, dw, arr):

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

    q = deque()

    q.append((ch - 1, cw - 1))
    status[ch - 1][cw - 1] = 0

    while len(q) > 0:
        currentY, currentX = q.popleft()
        childrens = [(currentY, currentX - 1), (currentY + 1, currentX), (currentY, currentX + 1),
                     (currentY - 1, currentX)]

        for child in childrens:
            childY, childX = child
            if childX >= 0 and childX < w and childY >= 0 and childY < h:
                if arr[childY][childX] == ".":
                    if status[childY][childX] == -1:
                        q.insert(0,(childY, childX))
                        status[childY][childX] = status[currentY][currentX]
                    else:
                        if status[childY][childX] > status[currentY][currentX]:
                            status[childY][childX] = status[currentY][currentX]
                            q.insert(0,(childY, childX))

        for i in range(-2, 3):
            for j in range(-2, 3):
                childY = currentY + i
                childX = currentX + j
                if (childY, childX) in childrens:
                    continue

                if childX >= 0 and childX < w and childY >= 0 and childY < h:
                    if arr[childY][childX] == ".":
                        if status[childY][childX] == -1:
                            status[childY][childX] = (status[currentY][currentX] + 1)
                            q.append((childY, childX))
                        else:
                            if status[childY][childX] > (status[currentY][currentX] + 1):
                                status[childY][childX] = (status[currentY][currentX] + 1)
                                q.append((childY, childX))
    print(status[dh-1][dw-1])
calculate(H,W,CH,CW,DH,DW,ARR)

Solution (Python):

from collections import deque
d = deque() 

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

d.appendleft((Ch-1, Cw-1, 0))
score = [[-1] * W for _ in range(H)]
score[Ch-1][Cw-1] = 0

walk = [(-1, 0), (1, 0), (0, -1), (0, 1)]
warp = list()
for i in range(-2, 3):
  for j in range(-2, 3):
    if (i, j) != (0, 0) and (i, j) not in walk:
      warp.append((i, j))

while len(d) > 0:
  
  y, x, s = d.popleft()
  
  
  for i in range(len(walk)):
    dy, dx = walk[i]
    if 0 <= y+dy < H and 0 <= x+dx < W: 
      if score[y+dy][x+dx] == -1 or score[y+dy][x+dx] > s:
        if Shw[y+dy][x+dx] == ".":
          d.appendleft((y+dy, x+dx, s))
          score[y+dy][x+dx] = s
          
  
  for i in range(len(warp)):
    dy, dx = warp[i]
    if 0 <= y+dy < H and 0 <= x+dx < W:
      if score[y+dy][x+dx] == -1 or score[y+dy][x+dx] > s+1:
        if Shw[y+dy][x+dx] == ".":
          d.append((y+dy, x+dx, s+1))
          score[y+dy][x+dx] = s+1

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

Solution (Python):
import math




import collections
import bisect
from collections import deque
from copy import copy, deepcopy
import time

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

def main():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch+=-1
    Cw+=-1
    Dh,Dw = map(int,input().split())
    Dh+=-1
    Dw+=-1
    S = [None for i in range(H)]
    
    for i in range(H):
        S[i] = input()
        
    ans=0
    visited = [[False for i in range(W)] for j in range(H)]
    walk_deque = deque()
    walk_deque.append((Ch,Cw))
    visited[Ch][Cw]=True
    while(1):
        new_visited = []
        while(len(walk_deque) != 0):
            Ph,Pw = walk_deque.popleft()
            new_visited.append([Ph,Pw])
            
            if Ph==Dh and Pw==Dw:
                print(ans)
                return
            for i in range(4):
                tmph = Ph+dy[i]
                tmpw = Pw+dx[i]
                if tmph >= 0 and tmph <=H-1 and tmpw >= 0 and tmpw <=W-1:
                    if S[tmph][tmpw]=='.' and not visited[tmph][tmpw]:
                        walk_deque.append((tmph,tmpw))
                        visited[tmph][tmpw]=True

        
        for h,w in new_visited:
            for x in [-2,-1,0,1,2]:
                for y in [-2,-1,0,1,2]:
                    tmph = h+y
                    tmpw = w+x
                    if tmph >= 0 and tmph <=H-1 and tmpw >= 0 and tmpw <=W-1:
                        if S[tmph][tmpw]=='.' and not visited[tmph][tmpw]:
                            walk_deque.append((h+y,w+x))
                            visited[h+y][w+x]=True
        ans+=1
        if len(walk_deque)==0:
            print(-1)
            return
        
if __name__ == '__main__':
    main()

Solution (Python):
m_d = list()    
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i,j) not in [(0,0),(-1,0),(0,-1),(1,0),(0,1)]:
            m_d += [(i,j)]

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()



INF = int(1e9)

dist = [[INF for j in range(w+4)] for i in range(h+4)]


S = ['
S = ['
S = S + ['


from collections import deque
q_a = deque() 
q_b = deque() 


si, sj = si+1, sj+1
ti, tj = ti+1, tj+1
dist[si][sj] = 0
q_a.append([si,sj])

while (len(q_a)>0):
    i, j = ij = q_a.popleft()
    d = dist[i][j]
    w = False
    for di, dj in [(-1,0),(0,-1),(1,0),(0,1)]:
        ni, nj = di+i, dj+j
        if (S[ni][nj]=='
            w = True
            continue 
        if (dist[ni][nj]<=d):
            continue 
        dist[ni][nj] = d
        q_a.append([ni,nj])
        
    if w: q_b.append(ij)

    if len(q_a) == 0:
        while (len(q_b)>0):
            i, j = q_b.popleft()
            d = dist[i][j]
            for di, dj in m_d:
                ni, nj = di+i, dj+j
                if (S[ni][nj]=='
                    continue 
                if (dist[ni][nj]<=d):
                    continue 
                dist[ni][nj] = d+1
                q_a.append([ni,nj])

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)

Solution (Python):
m_d = list()    
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i,j) not in [(0,0),(-1,0),(0,-1),(1,0),(0,1)]:
            m_d += [(i,j)]

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()



INF = int(1e9)

dist = [[INF for j in range(w+4)] for i in range(h+4)]


S = ['
S = ['
S = S + ['


from collections import deque
q_a = deque() 
q_b = deque() 


si, sj = si+1, sj+1
ti, tj = ti+1, tj+1
dist[si][sj] = 0
q_a.append([si,sj])

while (len(q_a)>0):
    i, j = ij = q_a.popleft()
    q_b.append(ij)
    d = dist[i][j]
    for di, dj in [(-1,0),(0,-1),(1,0),(0,1)]:
        ni, nj = di+i, dj+j
        if (S[ni][nj]=='
            continue 
        if (dist[ni][nj]<=d):
            continue 
        dist[ni][nj] = d
        q_a.append([ni,nj])

    if len(q_a) == 0:
        while (len(q_b)>0):
            i, j = q_b.popleft()
            d = dist[i][j]
            for di, dj in m_d:
                ni, nj = di+i, dj+j
                if (S[ni][nj]=='
                    continue 
                if (dist[ni][nj]<=d):
                    continue 
                dist[ni][nj] = d+1
                q_a.append([ni,nj])

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)