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
import sys

H, W = map(int, input().split())
xs, ys = map(int, input().split())
xt, yt = map(int, input().split())
xs -= 1
ys -= 1
xt -= 1
yt -= 1
G = [input() for _ in range(H)]

D_wk = [[1,0], [0,1], [-1,0], [0,-1]]
D_tl = 2



possible = set()
for i in range(H):
  for j in range(W):
    if G[i][j] == ".":
      possible.add(i * W + j)


def append_walk(c, x, y):
  for dx, dy in D_wk:
    if 0 <= x+dx <= H-1 and 0 <= y+dy <= W-1 and ((x+dx)*W+(y+dy)) in possible and ((x+dx)*W+(y+dy)) not in visited:
      task.appendleft([c, x+dx, y+dy])
def append_tele(c, x, y):
  for dx in range(-D_tl, D_tl+1):
    for dy in range(-D_tl, D_tl+1):
      if 0 <= x+dx <= H-1 and 0 <= y+dy <= W-1 and ((x+dx)*W+(y+dy)) in possible and ((x+dx)*W+(y+dy)) not in visited:
        task.append([c+1, x+dx, y+dy])

task = deque([[0, xs, ys]])
visited = set()
while task:
  while True:
    c, x, y = task.popleft()
    if x*W+y not in visited:
      break
    if not task:
      print(-1)
      sys.exit()    
  if x == xt and y == yt:
    print(c)
    
    sys.exit()  
  visited.add(x*W+y)
  
  append_walk(c, x, y)
  append_tele(c, x, y)
  
print(-1)

Solution (Python):
import sys
read = sys.stdin.read

from collections import deque
def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    maze = []
    dummy_row = ['
    maze.append(dummy_row)
    maze.append(dummy_row)
    for _ in range(h):
        row = ['
        maze.append(row)
    maze.append(dummy_row)
    maze.append(dummy_row)
    maze[ch + 1][cw + 1] = 0
    maze[dh + 1][dw + 1] = 'G'
    q = deque()
    q.append((ch+1, cw+1))
    r = float('inf')
    move_y = [-1, 0, 1, 0]
    move_x = [0, 1, 0, -1]
    while q:
        koko = q.popleft()
        koko_y = koko[0]
        koko_x = koko[1]
        koko_num = maze[koko_y][koko_x]
        for k1 in range(4):
            j1 = koko_y + move_y[k1]
            j2 = koko_x + move_x[k1]
            if maze[j1][j2] == 'G':
                r = min(r, koko_num)
            elif maze[j1][j2] == '.':
                maze[j1][j2] = koko_num
                q.appendleft((j1, j2))
            elif type(maze[j1][j2]) == int:
                if maze[j1][j2] > koko_num:
                    maze[j1][j2] = koko_num
                    q.appendleft((j1, j2))
        for i1 in range(koko_y - 2, koko_y + 3):
            for i2 in range(koko_x - 2, koko_x + 3):
                if maze[i1][i2] == 'G':
                    r = min(r, koko_num + 1)
                elif maze[i1][i2] == '.':
                    maze[i1][i2] = koko_num + 1
                    q.append((i1, i2))
                elif type(maze[i1][i2]) == int:
                    if maze[i1][i2] > koko_num + 1:
                        maze[i1][i2] = koko_num + 1
                        q.append((i1, i2))
    if r == float('inf'):
        print(-1)
    else:
        print(r)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def main():
    h, w = map(int, input().split())
    c = list(map(lambda x: int(x)+1, input().split()))
    d = list(map(lambda x: int(x)+1, input().split()))
    s = ['

    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
    ans[c[0]][c[1]] = 0

    move1 = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    move2 = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if abs(i)+abs(j) > 1]

    yet = deque([(c[0], c[1])])
    done = deque()

    while yet:
        y, x = yet.popleft()
        done.append((y, x))
        for dy, dx in move1:
            ydy, xdx = y+dy, x+dx
            if ans[ydy][xdx] == -1:
                yet.append((ydy, xdx))
                ans[ydy][xdx] = ans[y][x]

        if len(yet) == 0:
            while done:
                y, x = done.popleft()
                for dy, dx in move2:
                    ydy, xdx = y+dy, x+dx
                    if ans[ydy][xdx] == -1:
                        ans[ydy][xdx] = ans[y][x] + 1
                        yet.append((ydy, xdx))

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

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def main():
    h, w = map(int, input().split())
    start_h, start_w = map(lambda x: int(x)+1, input().split())
    goal_h, goal_w = map(lambda x: int(x)+1, input().split())

    s = ["
    s.append("
    for _ 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
    ans[start_h][start_w] = 0

    move1 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    move2 = [(-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)]

    yet = deque([(start_h, start_w)])
    done = deque()

    while yet:
        x1, y1 = yet.popleft()
        done.append((x1, y1))
        for (p, q) in move1:
            v1, v2 = x1+p, y1+q
            if ans[v1][v2] == -1: 
                yet.append((v1, v2))
                ans[v1][v2] = ans[x1][y1]

        if len(yet) == 0:
            while done:
                x2, y2 = done.popleft()
                for (p, q) in move2:
                    i, j = x2+p, y2+q
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        yet.append((i, j))

    print(ans[goal_h][goal_w])

if __name__ == "__main__":
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque

def main():
    h, w = map(int,input().split())
    h += 4
    w += 4
    C_h, C_w = map(int,input().split())
    C_h += 1
    C_w += 1
    D_h, D_w = map(int,input().split())
    D_h += 1
    D_w += 1
    S = ["
    for hh in range(2, h-2):
        S[hh] = "
    queue = deque([C_h*w + C_w])
    ans = [-1]*(h*w)
    ans[C_h*w + C_w] = 0
    visited = [False]*(h*w)
    visited[C_h*w + C_w] = True

    queue_0 = deque([C_h*w + C_w])
    while queue_0:
        node = queue_0.popleft()
        for xnode in (node - 1, node + 1, node - w, node + w):
            if S[xnode//w][xnode%w] == "." and not visited[xnode]:
                visited[xnode] = True
                ans[xnode] = 0
                queue_0.append(xnode)
                queue.append(xnode)
    while queue:
        node = queue.popleft()
        node_h = node//w
        node_w = node%w
        for xnode_h in (node_h - 2, node_h - 1, node_h, node_h + 1, node_h + 2):
            for xnode_w in (node_w - 2, node_w - 1, node_w, node_w + 1, node_w + 2):
                xnode = xnode_h*w + xnode_w
                if S[xnode_h][xnode_w] == "." and not visited[xnode]:
                    next_ans = ans[node] + 1
                    ans[xnode] = next_ans
                    queue.append(xnode)
                    visited[xnode] = True

                    queue_0 = deque([xnode])
                    while queue_0:
                        node2 = queue_0.popleft()
                        for xnode2 in (node2 - 1, node2 + 1, node2 - w, node2 + w):
                            if S[xnode2//w][xnode2%w] == "." and not visited[xnode2]:
                                visited[xnode2] = True
                                ans[xnode2] = next_ans
                                queue_0.append(xnode2)
                                queue.append(xnode2)




    print(ans[D_h*w + D_w])
        
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())
grid = []
cost = []
INF = 10**9+7

for i in range(H):
    b = input()
    grid.append(b)
    c = [INF for _ in range(W)]
    cost.append(c)

p = (Ch,Cw)
dqe = deque([p])
cost[Ch][Cw] = 0
while len(dqe) != 0:
    x,y = dqe.popleft()
    comsumption = cost[x][y]
    for nx,ny in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:
        if nx < 0 or nx >= H or ny < 0 or ny >= W:
            continue
        if grid[nx][ny] == '
            continue
        if cost[nx][ny] <= comsumption:
            continue
        cost[nx][ny] = comsumption
        np = (nx,ny)
        dqe.appendleft(np)
    
    for nx in range(x-2,x+3):
        for ny in range(y-2,y+3):
            if (nx == x and ny == y):
                continue
            if nx < 0 or nx >= H or ny < 0 or ny >= W:
                continue
            if grid[nx][ny] == '
                continue
            if cost[nx][ny] <= comsumption+1:
                continue
            cost[nx][ny] = comsumption+1
            np = (nx,ny)
            dqe.append(np)

ans = cost[Dh][Dw]
if ans == INF:
    ans = -1

print(ans)

Solution (Python):
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '
        elif (0<=ny<h and 0<=nx<w) and G[ny][nx] != '
            if abs(dy)+abs(dx)<=1:
                G[ny][nx] = '
                D[ny][nx] = D[y][x]
                Q.append((ny, nx))
            elif D[ny][nx] == 10**6:
                D[ny][nx] = D[y][x]+1
                Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Solution (Python):
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

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

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

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

maze[dh-1][dw-1] = "g"

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

ans = 0
queue = deque([(ch-1, cw-1)])
check = deque([])
while True:
    while queue:
        y, x = queue.popleft()
        check.append((y, x))
        for dxi, dyi in zip(dx, dy):
            if not (0<=x+dxi<w and 0<=y+dyi<h):
                continue
            if maze[y+dyi][x+dxi] == "g":
                print(ans)
                exit()
            if maze[y+dyi][x+dxi] != ".":
                pass
            else:
                queue.append((y+dyi, x+dxi))
                maze[y+dyi][x+dxi] = ans
    ans += 1
    while check:
        y, x = check.popleft()
        for i in range(-2,3):
            for j in range(-2,3):
                if not (0<=x+i<w and 0<=y+j<h):
                    continue
                if maze[y+j][x+i] == "g":
                    print(ans)
                    exit()
                if maze[y+j][x+i] != ".":
                    pass
                else:
                    maze[y+j][x+i] = ans
                    queue.append((y+j, x+i))
    if not queue:
        print(-1)
        exit()

Solution (Python):
from collections import deque

def main():
  h,w=map(int,input().split())
  cy,cx=map(int,input().split())
  dy,dx=map(int,input().split())

  M=["
  for i in range(2):
    M.insert(0,"
    M.append("

  C=[[-1 if M[j][i]=="." else -2 for i in range(w+4)] for j in range(h+4)]
  C[-~cy][-~cx]=0
  QA,QB=deque(),deque()
  QA.append((-~cy,-~cx,0))
  W=[[i,j] for i in range(-2,3) for j in range(-2,3) if abs(i)+abs(j)>1]

  while QA:
    h,w,c=QA.popleft()
    QB.append((h,w,c))

    for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
      dh,dw=h+i,w+j
      if C[dh][dw]==-1:
        C[dh][dw]=c
        QA.appendleft((dh,dw,c))

    if QA:
      continue

    while QB:
      h,w,c=QB.popleft()
      for i,j in W:
        dh,dw=h+i,w+j
        if C[dh][dw]==-1:
          C[dh][dw]=-~c
          QA.append((dh,dw,-~c))

  print(C[-~dy][-~dx])

if __name__ == "__main__":
  main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

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 _ in range(h):
    s.append(list(input()))
from collections import deque, defaultdict
def bfs(x, y):
    wp = defaultdict(list)
    d = [[-1] * w for _ in range(h)]
    d[x][y] = 0
    queue = deque([(x, y)])
    while queue:
        u, v = queue.popleft()
        wp[0].append((u, v))
        next_grid = [(u - 1, v), (u + 1, v), (u, v - 1), (u, v + 1)]
        for x, y in next_grid:
            if 0 <= x < h and 0 <= y < w and s[x][y] != '
                d[x][y] = d[u][v]
                queue.append((x, y))
    for i in range(10**6):
        if len(wp[i]) == 0:
            break
        queue = deque([])
        for x, y in wp[i]:
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    u, v = x + dx, y + dy
                    if 0 <= u < h and 0 <= v < w and s[u][v] == '.' and d[u][v] < 0:
                        d[u][v] = i + 1
                        queue.append((u, v))
        while queue:
            u, v = queue.popleft()
            wp[i + 1].append((u, v))
            next_grid = [(u - 1, v), (u + 1, v), (u, v - 1), (u, v + 1)]
            for x, y in next_grid:
                if 0 <= x < h and 0 <= y < w and s[x][y] != '
                    d[x][y] = d[u][v]
                    queue.append((x, y))
    return d

d = bfs(ch, cw)
print(d[dh][dw])

Solution (Python):
from collections import deque

H,W=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
field=[list(input()) for _ in range(H)]
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1

Walk=[[1,0],[0,1],[-1,0],[0,-1]]
Warp=[[i,j] for i in range(-2,3) for j in range(-2,3)] 

dist=[[-1]*W for _ in range(H)]
que=deque()
dist[sy][sx]=0
que.append([sy,sx])

while que:
    y,x=que.popleft()
    for walk in Walk:
        nx,ny=x+walk[0],y+walk[1]
        if nx<0 or nx>=W or ny<0 or ny>=H: continue
        if field[ny][nx]=="
        if dist[ny][nx]!=dist[y][x]:
            dist[ny][nx]=dist[y][x]
            que.appendleft([ny,nx])
    
    for warp in Warp:
        nx,ny=x+warp[0],y+warp[1]
        if nx<0 or nx>=W or ny<0 or ny>=H: continue
        if field[ny][nx]=="
        if dist[ny][nx]==-1:
            dist[ny][nx]=dist[y][x]+1
            que.append([ny,nx])

print(dist[gy][gx])

Solution (Python):
from collections import deque
def main():
  h,w = map(int,input().split())
  ch,cw = map(lambda x:int(x)+1,input().split())
  dh,dw = map(lambda x:int(x)+1,input().split())
  s = [["
  m1 = ((-1,0),(0,-1),(0,1),(1,0))
  m2 = [(i,j) for i in range(-2,3) for j in range(-2,3) if abs(i)+abs(j)>1]
  a = deque([(ch,cw)])
  b = deque()
  i = 0
  while a:
    while a:
      ah,aw = a.popleft()
      if s[ah][aw]!=".":
        continue
      b.append((ah,aw))
      s[ah][aw] = i
      for bh,bw in m1:
        bh,bw = ah+bh,aw+bw
        if s[bh][bw]==".":
          a.append((bh,bw))
    while b:
      ah,aw = b.popleft()
      for bh,bw in m2:
        bh,bw = ah+bh,aw+bw
        if s[bh][bw]==".":
          a.append((bh,bw))
    i += 1
  ans = s[dh][dw]
  print(ans if ans != "." else -1)

if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin
import collections

input = stdin.readline

Y, X = map(int, input().split())
sy, sx = map(int, input().split())
sy -= 1
sx -= 1
ey, ex = map(int, input().split())
ey -= 1
ex -= 1
grid = [[c for c in inp] for inp in stdin.read().splitlines()]
dis = [[float('inf')] * X for _ in range(Y)]

Q = collections.deque()
Q.append((sy, sx,))
dis[sy][sx] = 0
while Q:
    cy, cx = Q.popleft()
    for ny, nx in [(cy + 1, cx), (cy - 1, cx), (cy, cx + 1), (cy, cx - 1)]:
        if 0 <= ny < Y and 0 <= nx < X and grid[ny][nx] == '.' and dis[ny][nx] > dis[cy][cx]:
            Q.appendleft((ny,nx))
            dis[ny][nx] = dis[cy][cx]
    for dy in range(-2,3):
        for dx in range(-2,3):
            ny = cy + dy
            nx = cx + dx
            if 0 <= ny < Y and 0 <= nx < X and grid[ny][nx] == '.' and dis[ny][nx] > dis[cy][cx] + 1:
                Q.append((ny,nx))
                dis[ny][nx] = dis[cy][cx] + 1

print(dis[ey][ex] if dis[ey][ex] != float('inf') else -1)

Solution (Python):
from collections import deque

di = [-1,0,1,0]
dj = [0,-1,0,1]

H,W = map(int,input().split())
si,sj = map(int,input().split())
ti,tj = map(int,input().split())
si -= 1
sj -= 1
ti -= 1
tj -= 1

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

inf = 10**9

dist = [[inf] * W for i in range(H)]
dist[si][sj] = 0
q = deque()
q.appendleft([si,sj])

while(len(q) > 0):
  tmp = q.popleft()
  i = tmp[0]
  j = tmp[1]
  d = dist[i][j]
  for v in range(4):
    ni = i + di[v]
    nj = j + dj[v]
    if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
      continue
    if s[ni][nj] == "
      continue
    if dist[ni][nj] <= d:
      continue
    dist[ni][nj] = d
    q.appendleft([ni,nj])
    
  for ei in range(-2, 3, 1):
    for ej in range(-2, 3, 1):
      ni = i + ei
      nj = j + ej
      if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
        continue
      if s[ni][nj] == "
        continue
      if dist[ni][nj] <= d+1:
        continue
      dist[ni][nj] = d+1
      q.append([ni,nj])
      
ans = dist[ti][tj]
if ans == inf:
  ans = -1
print(ans)

Solution (Python):
import collections

def WizMove(sh,sw,cost):
    q.append([sh,sw])
    s[sh][sw] = cost
    nextQ.append([sh,sw])

h,w = list(map(int,input().split()))

c = list(map(int,input().split()))
c = [c[0] - 1,c[1] - 1]
d = list(map(int,input().split()))
d = [d[0] - 1,d[1] - 1]

s = []

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

q = collections.deque()
nextQ = collections.deque()

q.append(c)
nextQ.append(c)
s[c[0]][c[1]] = 0
cost = 0

while len(nextQ) > 0:
    while len(q) > 0:
        wiz = q.popleft()
        if wiz[0] > 0:
            if s[wiz[0] - 1][wiz[1]] == ".":
                WizMove(wiz[0] - 1 , wiz[1] , cost)
        if wiz[0] < h - 1:
            if s[wiz[0] + 1][wiz[1]] == ".":
                WizMove(wiz[0] + 1 , wiz[1] , cost)
        if wiz[1] > 0:
            if s[wiz[0]][wiz[1] - 1] == ".":
                WizMove(wiz[0] , wiz[1] - 1 , cost)
        if wiz[1] < w - 1:
            if s[wiz[0]][wiz[1] + 1] == ".":
                WizMove(wiz[0] , wiz[1] + 1 , cost)
    cost += 1
    count = len(nextQ)
    for k in range(count):
        wiz = nextQ.popleft()
        for i in range(max(0,wiz[0]-2),min(h,wiz[0] + 3)):
            for j in range(max(0,wiz[1]-2),min(w,wiz[1] + 3)):
                if s[i][j] == ".":
                    WizMove(i,j,cost)

ans = s[d[0]][d[1]]
if ans == ".":
    ans = -1
print(ans)

Solution (Python):
from _collections import deque


h,w=map(int,input().split())
cx,cy=map(int,input().split())
dx,dy=map(int,input().split())
s=[[] for _ in range(h+2)]
for i in range(h):
    x=list(input())
    x.insert(0,"
    x.append("
    s[i+1]=x
s[0]=s[-1]=["




dep=[[10**10]*(w+2) for _ in range(h+2)]
dep[cx][cy]=0
data=deque([[cx,cy,0]])
while len(data)>0:
  xy=data.popleft()
  x,y=xy[0],xy[1]
  if xy[2]==dep[x][y]:
    if s[x-1][y]=="." and dep[x-1][y]>dep[x][y]:
        dep[x-1][y]=dep[x][y]
        data.appendleft([x-1,y,dep[x][y]])
    if s[x+1][y] == "." and dep[x+1][y] > dep[x][y]:
        dep[x+1][y] = dep[x][y]
        data.appendleft([x + 1,y,dep[x][y]])
    if s[x][y-1] == "." and dep[x][y-1] > dep[x][y]:
        dep[x][y-1] = dep[x][y]
        data.appendleft([x,y-1,dep[x][y]])
    if s[x][y+1] == "." and dep[x][y+1] > dep[x][y]:
        dep[x][y+1] = dep[x][y]
        data.appendleft([x,y+1,dep[x][y]])

    for i in range(5):
        for j in range(5):
            if 0<=x-2+i<=h+1 and 0<=y-2+j<=w+1 and s[x-2+i][y-2+j]=="." and dep[x-2+i][y-2+j]>dep[x][y]+1:
                dep[x-2+i][y-2+j]=dep[x][y]+1
                data.append([x-2+i,y-2+j,dep[x][y]+1])

print(dep[dx][dy] if dep[dx][dy]<10**10 else -1)

Solution (Python):
from _collections import deque


h,w=map(int,input().split())
cx,cy=map(int,input().split())
dx,dy=map(int,input().split())
s=[[] for _ in range(h+2)]
for i in range(h):
    x=list(input())
    x.insert(0,"
    x.append("
    s[i+1]=x
s[0]=s[-1]=["




dep=[[10**10]*(w+2) for _ in range(h+2)]
dep[cx][cy]=0
data=deque([[cx,cy,0]])
while len(data)>0:
  xy=data.popleft()
  x,y=xy[0],xy[1]
  if xy[2]==dep[x][y]:
    if s[x-1][y]=="." and dep[x-1][y]>dep[x][y]:
        dep[x-1][y]=dep[x][y]
        data.appendleft([x-1,y,dep[x][y]])
    if s[x+1][y] == "." and dep[x+1][y] > dep[x][y]:
        dep[x+1][y] = dep[x][y]
        data.appendleft([x + 1,y,dep[x][y]])
    if s[x][y-1] == "." and dep[x][y-1] > dep[x][y]:
        dep[x][y-1] = dep[x][y]
        data.appendleft([x,y-1,dep[x][y]])
    if s[x][y+1] == "." and dep[x][y+1] > dep[x][y]:
        dep[x][y+1] = dep[x][y]
        data.appendleft([x,y+1,dep[x][y]])

    for i in range(5):
        for j in range(5):
            if 0<=x-2+i<=h+1 and 0<=y-2+j<=w+1 and s[x-2+i][y-2+j]=="." and dep[x-2+i][y-2+j]>dep[x][y]+1:
                dep[x-2+i][y-2+j]=dep[x][y]+1
                data.append([x-2+i,y-2+j,dep[x][y]+1])

print(dep[dx][dy] if dep[dx][dy]<10**10 else -1)

Solution (Python):
from _collections import deque
h,w=map(int,input().split())
cx,cy=map(int,input().split())
dx,dy=map(int,input().split())
s=[[] for _ in range(h+2)]
for i in range(h):
    x=list(input())
    x.insert(0,"
    x.append("
    s[i+1]=x
s[0]=s[-1]=["


dep=[[10**10]*(w+2) for _ in range(h+2)]
dep[cx][cy]=0
data=deque([[cx,cy]])
data2=deque([])
while len(data)>0:
    while len(data)>0:
        xy=data.popleft()
        x,y=xy[0],xy[1]
        data2.append([x,y])
        if s[x-1][y]=="." and dep[x-1][y]>dep[x][y]:
            dep[x-1][y]=dep[x][y]
            data.append([x-1,y])

        if s[x+1][y] == "." and dep[x+1][y] > dep[x][y]:
            dep[x+1][y] = dep[x][y]
            data.append([x + 1,y])

        if s[x][y-1] == "." and dep[x][y-1] > dep[x][y]:
            dep[x][y-1] = dep[x][y]
            data.append([x,y-1])

        if s[x][y+1] == "." and dep[x][y+1] > dep[x][y]:
            dep[x][y+1] = dep[x][y]
            data.append([x,y+1])


    while len(data2)>0:
        xy=data2.popleft()
        x,y=xy[0],xy[1]
        for i in range(5):
            for j in range(5):
                if 0<=x-2+i<=h+1 and 0<=y-2+j<=w+1 and s[x-2+i][y-2+j]=="." and dep[x-2+i][y-2+j]>dep[x][y]+1:
                    dep[x-2+i][y-2+j]=dep[x][y]+1
                    data.append([x-2+i,y-2+j])

print(dep[dx][dy] if dep[dx][dy]<10**10 else -1)

Solution (Python):

import base64
import subprocess
import zlib


exe_bin = "c%1EgeSA~LmFT^aY|CIQK}=

open("./kyomu", 'wb').write(zlib.decompress(base64.b85decode(exe_bin)))
subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Solution (Python):
from _collections import deque


h,w=map(int,input().split())
cx,cy=map(int,input().split())
dx,dy=map(int,input().split())
s=[[] for _ in range(h+2)]
for i in range(h):
    x=list(input())
    x.insert(0,"
    x.append("
    s[i+1]=x
s[0]=s[-1]=["




dep=[[10**10]*(w+2) for _ in range(h+2)]
dep[cx][cy]=0
data=deque([[cx,cy]])
while len(data)>0:
    xy=data.popleft()
    x,y=xy[0],xy[1]

    if s[x-1][y]=="." and dep[x-1][y]>dep[x][y]:
        dep[x-1][y]=dep[x][y]
        data.appendleft([x-1,y])
    if s[x+1][y] == "." and dep[x+1][y] > dep[x][y]:
        dep[x+1][y] = dep[x][y]
        data.appendleft([x + 1,y])
    if s[x][y-1] == "." and dep[x][y-1] > dep[x][y]:
        dep[x][y-1] = dep[x][y]
        data.appendleft([x,y-1])
    if s[x][y+1] == "." and dep[x][y+1] > dep[x][y]:
        dep[x][y+1] = dep[x][y]
        data.appendleft([x,y+1])

    for i in range(5):
        for j in range(5):
            if 0<=x-2+i<=h+1 and 0<=y-2+j<=w+1 and s[x-2+i][y-2+j]=="." and dep[x-2+i][y-2+j]>dep[x][y]+1:
                dep[x-2+i][y-2+j]=dep[x][y]+1
                data.append([x-2+i,y-2+j])

print(dep[dx][dy] if dep[dx][dy]<10**10 else -1)

Solution (Python):
from _collections import deque


h,w=map(int,input().split())
cx,cy=map(int,input().split())
dx,dy=map(int,input().split())
s=[[] for _ in range(h+2)]
for i in range(h):
    x=list(input())
    x.insert(0,"
    x.append("
    s[i+1]=x
s[0]=s[-1]=["




dep=[[10**10]*(w+2) for _ in range(h+2)]
dep[cx][cy]=0
data=deque([[cx,cy]])
while len(data)>0:
    xy=data.popleft()
    x,y=xy[0],xy[1]

    if s[x-1][y]=="." and dep[x-1][y]>dep[x][y]:
        dep[x-1][y]=dep[x][y]
        data.appendleft([x-1,y])
    if s[x+1][y] == "." and dep[x+1][y] > dep[x][y]:
        dep[x+1][y] = dep[x][y]
        data.appendleft([x + 1,y])
    if s[x][y-1] == "." and dep[x][y-1] > dep[x][y]:
        dep[x][y-1] = dep[x][y]
        data.appendleft([x,y-1])
    if s[x][y+1] == "." and dep[x][y+1] > dep[x][y]:
        dep[x][y+1] = dep[x][y]
        data.appendleft([x,y+1])

    for i in range(5):
        for j in range(5):
            if 0<=x-2+i<=h+1 and 0<=y-2+j<=w+1 and s[x-2+i][y-2+j]=="." and dep[x-2+i][y-2+j]>dep[x][y]+1:
                dep[x-2+i][y-2+j]=dep[x][y]+1
                data.append([x-2+i,y-2+j])

print(dep[dx][dy] if dep[dx][dy]<10**10 else -1)

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

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

used = [[-1]*W for _ in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
q = deque()
flag = True
num = 0
for k in range(H):
    for l in range(W):
        if S[k][l] == "
            continue
        used[k][l] = num
        q.append((num, k, l))
        while q:
            temp = q.popleft()
            num = temp[0]
            i = temp[1]
            j = temp[2]

            if i > 0 and S[i-1][j] == "." and used[i-1][j] == -1:
                used[i-1][j] = num
                q.append((num, i-1, j))
            if j > 0 and S[i][j-1] == "." and used[i][j-1] == -1:
                used[i][j-1] = num
                q.append((num, i, j-1))
            if i < H-1 and S[i+1][j] == "." and used[i+1][j] == -1:
                used[i+1][j] = num
                q.append((num, i+1, j))
            if j < W-1 and S[i][j+1] == "." and used[i][j+1] == -1:
                used[i][j+1] = num
                q.append((num, i, j+1))
        num += 1

E = [[] for _ in range(num)]
for i in range(H):
    for j in range(W):
        for k in range(i-2, i+3):
            for l in range(j-2, j+3):
                if k < 0 or k > H-1 or l < 0 or l > W-1:
                    continue
                if S[k][l] == "
                    continue
                if used[i][j] != used[k][l] and used[i][j] not in E[used[k][l]]:
                    E[used[i][j]].append(used[k][l])
                    E[used[k][l]].append(used[i][j])


dist = [10**6]*num
q = deque()
q.append((0, used[Ch][Cw]))
dist[used[Ch][Cw]] = 0
while q:
    temp = q.popleft()
    d = temp[0]
    i = temp[1]
    for e in E[i]:
        if dist[e] > d+1:
            dist[e] = d+1
            q.append((d+1, e))
if num == 1:
    print(0)
elif dist[used[Dh][Dw]] == 10**6:
    print(-1)
else:
    print(dist[used[Dh][Dw]])