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 defaultdict, deque

def main():
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1
    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)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque
h,w = map(int,input().split())
sx,sy = map(int,input().split())
sx -= 1
sy -= 1
gx,gy = map(int,input().split())
gx -= 1
gy -= 1
route = []
for i in range(h):
  lst = list(input())
  route.append(lst)
  
brock = [['

que = deque([])
dx = [-1,0,1,0]
dy = [0,-1,0,1]

brock[sx][sy] = 0
que.append((sx,sy))



while que:
  
  (p,q) = que.popleft()
  if (p,q) == (gx,gy):
    print(brock[gx][gy])
    sys.exit()
  for i in range(4):
    p2,q2 = p+dx[i],q+dy[i]
    if 0 <= p2 < h and 0<= q2 < w and route[p2][q2] == '.' and (brock[p2][q2] == '
      brock[p2][q2] = brock[p][q]
      que.appendleft((p2,q2))
  
  for j in range(-2,3):
    for k in range(-2,3):
      p3 = p+j
      q3 = q+k
      if 0 <= p3 < h and 0<= q3 < w and route[p3][q3] == '.' and brock[p3][q3] == '
        brock[p3][q3] = brock[p][q]+1
        que.append((p3,q3))
        
        
            
                  
              
print(-1)

Solution (Python):
def main():
    H, W = [int(s) for s in input().split()]
    sh, sw = [int(s) -1 for s in input().split()]
    gh, gw = [int(s) -1 for s in input().split()]
    maze = []
    for i in range(H):
        maze.append(input())
    queue = [(sh, sw)]
    skip = 0
    seen = {(sh, sw)}
    nqs = set()
    while queue:
        nq = []
        while queue:
            x, y = queue.pop()
            if x == gh and gw == y:
                print(skip)
                return
            for i,j in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                if 0 <= i+x < H and 0 <= j+y < W:
                    ns = (i+x, j+y)
                    if maze[i+x][j+y] == '.':
                        if ns in seen:
                            continue
                        seen.add(ns)
                        queue.append(ns)
            ns = (x,y)
            if ns not in nqs:
                nqs.add(ns)
                nq.append(ns)

        skip += 1
        queue = []
        for x, y in nq:
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if 0 <= i+x < H and 0 <= j+y < W:
                        if maze[i+x][j+y] == '.':
                            ns = (i+x, j+y)
                            if ns not in seen:
                                seen.add(ns)
                                queue.append(ns)
        
    print(-1)

main()

Solution (Python):
from collections import deque
H, W = map(int, input().split())
C_h, C_w = map(lambda x:int(x) - 1,input().split())
D_h, D_w = map(lambda x:int(x) - 1,input().split())
S = [input() for _ in range(H)]

waiting = deque()
went = [[10**9]*W for _ in range(H)]
waiting.append([0, C_h, C_w])

ans = -1
while len(waiting) > 0:
    n, cur_h, cur_w = waiting.popleft()
    if cur_h == D_h and cur_w == D_w:
        ans = n
        break
    if went[cur_h][cur_w] > n:
        went[cur_h][cur_w] = n
        for i in range(-2, 3):
            for j in range(-2, 3):
                next_h = cur_h + i
                next_w = cur_w + j
                if 0 <= next_h < H and 0 <= next_w < W:
                    if (i == 0 and j == -1) or (i == 0 and j == 1) or (i == -1 and j == 0) or (i == 1 and j == 0):
                        if went[next_h][next_w] > n and S[next_h][next_w] == '.':
                            waiting.appendleft([n, next_h, next_w])
                    else:
                        if went[next_h][next_w] > n + 1 and S[next_h][next_w] == '.':
                            waiting.append([n + 1, next_h, next_w])

print(ans)

Solution (Python):
from collections import deque


def main():
    h, w = map(int, input().split())
    cs = list(map(int, input().split()))
    ds = list(map(int, input().split()))
    S = [[s for s in input()] for _ in range(h)]

    curq = deque()
    nexq = deque([(cs[0] - 1, cs[1] - 1)])
    l = 0
    while len(nexq) > 0:
        curq, nexq = nexq, deque()
        while len(curq) > 0:
            y, x = curq.popleft()
            if S[y][x] != ".":
                continue

            S[y][x] = l
            for dy in range(-2, 3):
                for dx in range(-2, 3):
                    if 0 <= y + dy < h and 0 <= x + dx < w and S[y + dy][x + dx] == ".":
                        if abs(dx) + abs(dy) < 2:
                            curq.append((y + dy, x + dx))
                        else:
                            nexq.append((y + dy, x + dx))
        l += 1

    ans = S[ds[0] - 1][ds[1] - 1]
    print(ans if ans != "." else -1)


if __name__ == '__main__':
    main()

Solution (Python):

INF = float("inf")
import sys
input = sys.stdin.readline
from collections import*

def bfs():
    q = deque([(sx, sy)])
    dist = [[INF] * W for _ in range(H)]
    dist[sx][sy] = 0
    
    while q:
        x, y = q.popleft()
        b = dist[x][y]
        if (x, y) == (gx, gy):
            return b
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] > b and c[nx][ny] == ".":
                dist[nx][ny] = b
                q.appendleft((nx, ny))
        b += 1
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] > b and c[nx][ny] == ".":
                    dist[nx][ny] = b
                    q.append((nx, ny)) 
    return -1

H, W = map(int, input().split())
cx, cy = map(int, input().split())
dx, dy = map(int, input().split())
sx, sy, gx, gy = cx - 1, cy - 1, dx - 1, dy - 1
c = [input()[:-1] for _ in range(H)]
ans = bfs()
print(ans if ans != INF else -1)

Solution (Python):

INF = 10**7
import sys
input = sys.stdin.readline
from collections import*

def bfs():
    q = deque([(sx, sy)])
    dist = [[INF] * W for _ in range(H)]
    dist[sx][sy] = 0
    
    while q:
        x, y = q.popleft()
        b = dist[x][y]
        if (x, y) == (gx, gy):
            return b
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] > b and c[nx][ny] == ".":
                dist[nx][ny] = b
                q.appendleft((nx, ny))
        B = b + 1
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] > B and c[nx][ny] == ".":
                    dist[nx][ny] = B
                    q.append((nx, ny)) 
    return -1

H, W = map(int, input().split())
cx, cy = map(int, input().split())
dx, dy = map(int, input().split())
sx, sy, gx, gy = cx - 1, cy - 1, dx - 1, dy - 1
c = [input()[:-1] for _ in range(H)]
ans = bfs()
print(ans if ans != INF else -1)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

graph = [0] + [0] * h
for i in range(h):
    graph[i + 1] = '0' + input().strip()

from collections import deque

def bfs(graph, queue, dist):
    while queue:
        current_h, current_w = queue.popleft()

        for dh, dw in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            next_h, next_w = current_h + dh, current_w + dw
            if not ((1 <= next_h <= h) and (1 <= next_w <= w)):
                continue
            if graph[next_h][next_w] == '
                continue
            if dist[next_h][next_w] != -1 and dist[next_h][next_w] <= dist[current_h][current_w]:
                continue
            else:
                dist[next_h][next_w] = dist[current_h][current_w]
                queue.appendleft((next_h, next_w))

        for dh in range(-2, 3):
            for dw in range(-2, 3):
                next_h, next_w = current_h + dh, current_w + dw
                if not ((1 <= next_h <= h) and (1 <= next_w <= w)):
                    continue
                if graph[next_h][next_w] == '
                    continue
                if dist[next_h][next_w] != -1:
                    continue
                else:
                    dist[next_h][next_w] = dist[current_h][current_w] + 1
                    queue.append((next_h, next_w))

queue = deque([(ch, cw)])
dist = [-1] + [0] * h
for i in range(h):
    dist[i + 1] = [0] + [-1] * w
dist[ch][cw] = 0
bfs(graph, queue, dist)
print(dist[dh][dw])

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 = []
for i in range(h):
  s += [input()]
t = [[h*w]*w for i in range(h)]
t[c[0]-1][c[1]-1] = 0
p = deque([[c[0]-1,c[1]-1]])
while p:
  q = p.popleft()
  u = t[q[0]][q[1]]
  for i in range(-2,3):
    if 0 <= q[0]+i and q[0]+i < h:
      for j in range(-2,3):
         if 0 <= q[1]+j and q[1]+j < w:
            if s[q[0]+i][q[1]+j] == ".":
              if abs(i) + abs(j) == 1:
                if t[q[0]+i][q[1]+j] > u:
                  t[q[0]+i][q[1]+j] = u
                  p.appendleft([q[0]+i,q[1]+j])
              else:
                if t[q[0]+i][q[1]+j] > u+1:
                  t[q[0]+i][q[1]+j] = u+1
                  p.append([q[0]+i,q[1]+j])
ans = t[d[0]-1][d[1]-1]
if ans == h*w:
  ans = -1
print(ans)

Solution (Python):
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 = H * W

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

num_step = [[INF for w in range(W)] for h in range(H)]
num_step[Ch - 1][Cw - 1] = 0


queue = [(Ch - 1, Cw - 1)]
num_warp = 0


while not queue == []:
    magic_tiles = []
    while not queue == []:
        h = queue.pop() 
        if h[0] == Dh - 1 and h[1] == Dw - 1:
            print(num_warp)
            exit()
        for i in range(4):
            if 0 <= h[0]+dy[i] < H and 0 <= h[1]+dx[i] < W and S[h[0]+dy[i]][h[1]+dx[i]] == '.' \
                 and num_step[h[0]+dy[i]][h[1]+dx[i]] > num_warp:
                queue.append((h[0]+dy[i], h[1]+dx[i]))
                num_step[h[0]+dy[i]][h[1]+dx[i]] = num_warp

        
        mx = [-2, -1 , 0, 1, 2]
        my = [-2, -1 , 0, 1, 2]

        for x in mx:
            for y in my:
                 if 0 <= h[0] + y < H and 0 <= h[1] + x < W and S[h[0] + y][h[1] + x] == '.' \
                     and num_step[h[0] + y][h[1] + x] == INF:
                    magic_tiles.append((h[0] + y, h[1] + x))

    num_warp += 1

    
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            num_step[magic[0]][magic[1]] = num_warp
            queue.append((magic[0], magic[1]))

print(-1)

Solution (Python):
h,w = map(int,input().split())
c = list(map(int,input().split()))
c[0] -= 1
c[1] -= 1
d = list(map(int,input().split()))
d[0] -= 1
d[1] -= 1
p = []
q = [[None for i in range(w)]for i in range(h)]
r = [[] for i in range(10**6)]
for i in range(h):
    s = input()
    s = list(s)
    p.append(s)
from collections import deque
de = deque()
de.append([c[0],c[1]])
q[c[0]][c[1]] = 0
g = 0
while q[d[0]][d[1]] == None and g < 10**6-3:
    while de:
        v = de.pop()
        r[g].append([v[0],v[1]])
        for i in (-1,1):
            j = 0
            if 0 <= v[0]-i <= h-1:
                if 0 <= v[1]-j <= w-1:
                    if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                        q[v[0]-i][v[1]-j] = g
                        de.append([v[0]-i,v[1]-j])
        for j in (-1,1):
            i = 0
            if 0 <= v[0]-i <= h-1:
                if 0 <= v[1]-j <= w-1:
                    if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                        q[v[0]-i][v[1]-j] = g
                        de.append([v[0]-i,v[1]-j])
    g += 1
    while r[g-1]:
        v = r[g-1].pop()
        for i in range(-2,3):
            for j in range(-2,3):
                if (abs(i) == 1 and j == 0) or (abs(j) == 1 and i == 0):
                    continue
                else:
                    if 0 <= v[0]-i <= h-1:
                        if 0 <= v[1]-j <= w-1:
                            if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                                q[v[0]-i][v[1]-j] = g
                                de.append([v[0]-i,v[1]-j])
if q[d[0]][d[1]] == None:
    print(-1)
else:
    print(q[d[0]][d[1]])

Solution (Python):
h,w = map(int,input().split())
c = list(map(int,input().split()))
c[0] -= 1
c[1] -= 1
d = list(map(int,input().split()))
d[0] -= 1
d[1] -= 1
p = []
q = [[None for i in range(w)]for i in range(h)]
r = [[] for i in range(10**6)]
for i in range(h):
    s = input()
    s = list(s)
    p.append(s)
from collections import deque
de = deque()
de.append([c[0],c[1]])
q[c[0]][c[1]] = 0
g = 0
while q[d[0]][d[1]] == None and g < 10**6-3:
    while de:
        v = de.popleft()
        r[g].append([v[0],v[1]])
        for i in (-1,1):
            j = 0
            if 0 <= v[0]-i <= h-1:
                if 0 <= v[1]-j <= w-1:
                    if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                        q[v[0]-i][v[1]-j] = g
                        de.append([v[0]-i,v[1]-j])
        for j in (-1,1):
            i = 0
            if 0 <= v[0]-i <= h-1:
                if 0 <= v[1]-j <= w-1:
                    if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                        q[v[0]-i][v[1]-j] = g
                        de.append([v[0]-i,v[1]-j])
    g += 1
    while r[g-1]:
        v = r[g-1].pop()
        for i in range(-2,3):
            for j in range(-2,3):
                if (abs(i) == 1 and j == 0) or (abs(j) == 1 and i == 0):
                    continue
                else:
                    if 0 <= v[0]-i <= h-1:
                        if 0 <= v[1]-j <= w-1:
                            if p[v[0]-i][v[1]-j] == '.' and q[v[0]-i][v[1]-j] == None:
                                q[v[0]-i][v[1]-j] = g
                                de.append([v[0]-i,v[1]-j])
if q[d[0]][d[1]] == None:
    print(-1)
else:
    print(q[d[0]][d[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)]
q = deque()
q.appendleft([si,sj])
dist[si][sj] = 0
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
    q.appendleft([ni,nj])
    dist[ni][nj] = d
    
  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
      q.append([ni,nj])
      dist[ni][nj] = d+1
      
ans = dist[ti][tj]
if ans == inf:
  ans = -1
print(ans)

Solution (Python):
import queue

H,W = map(int,input().split())
C = [int(i)+1 for i in input().split()]
D = [int(i)+1 for i in input().split()]

l = []
l.append([-1]*(W+4))
l.append([-1]*(W+4))
for _ in range(H):
    l.append([-1,-1]+ [0 if i=="." else -1 for i in input()] + [-1,-1])
l.append([-1]*(W+4))
l.append([-1]*(W+4))

l[C[0]][C[1]] = 1 

def p():
    for i in l[2:2+H]:
        print(",".join([str(j) for j in i[2:2+W]]))

q = queue.Queue()
q.put(C)
now = 1
q2 = queue.Queue()
while True:
    while not q.empty():
        x,y = q.get()
        q2.put([x,y])
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            if l[x+i][y+j] ==0:
                q.put([x+i,y+j])
                l[x+i][y+j] = now
    if l[D[0]][D[1]] > 0:
        print(l[D[0]][D[1]]-1)
        break
    now += 1
    if q2.empty():
        print(-1)
        break
    while not q2.empty():
        x,y = q2.get()
        for i in range(-2,3):
            for j in range(-2,3):
                if l[x+i][y+j] ==0:
                    q.put([x+i,y+j])
                    l[x+i][y+j] = now
    if l[D[0]][D[1]] > 0:
        print(l[D[0]][D[1]]-1) 
        break

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)]
q = deque()
q.appendleft([si,sj])
dist[si][sj] = 0
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 dist[ni][nj] <= d+1:
        continue
      if s[ni][nj] == "
        continue
      dist[ni][nj] = d+1
      q.append([ni,nj])

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

Solution (Python):

"""
Created on Fri Sep 11 11:57:24 2020

@author: liang
"""

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

from collections import deque
q = deque()
adj1 = [(0,1), (0,-1), (1,0), (-1,0)]
visited = [[False]*W for _ in range(H)]

q.append((sy, sx, 0))

while q:
    cy, cx, cost = q.popleft()
    
    if (cy,cx) == (gy,gx):
        print(cost)
        break
    if not visited[cy][cx]:
        
        visited[cy][cx] = True
        
        for a in adj1:
            ny, nx = cy + a[0], cx + a[1]
            if ny >= H or ny < 0:
                continue
            if nx >= W or nx < 0:
                continue
            if field[ny][nx] == "
                continue
            if not visited[ny][nx]:
                q.appendleft((ny, nx, cost))
        
        for i in range(-2,3):
            for j in range(-2,3):
                ny, nx = cy + i, cx + j
                if ny >= H or ny < 0:
                    continue
                if nx >= W or nx < 0:
                    continue
                if field[ny][nx] == "
                    continue
                if not visited[ny][nx]:
                    q.append((ny, nx, cost+1))
else:
    print(-1)

Solution (Python):
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()))

Ss = [str(input()) for _ in range(H)]
group = [[-1 for _ in range(W)] for _ in range(H)]

moves = [[-1,0], [1,0], [0,-1], [0,1]]

from collections import deque
todo = deque()
now_group = -1
for i in range(H):
    for j in range(W):
        if group[i][j] == -1 and Ss[i][j]==".":
            todo.append([i,j])
            now_group += 1
            group[i][j] = now_group
        while len(todo) > 0:
            checking = todo.pop()
            for move in moves:
                now = [checking[0]+move[0],checking[1]+move[1]]
                if not (0 <= now[0] <H and 0 <= now[1] <W):
                    continue
                if group[now[0]][now[1]] == -1 and Ss[now[0]][now[1]]==".":
                    todo.append(now)
                    group[now[0]][now[1]] = now_group

can_waap = [set() for _ in range(now_group+1)]

for i in range(H):
    for j in range(W):
        if group[i][j] ==-1:
            continue
        for yoko in range(-2,3):
            for tate in range(-2,3):
                now = [tate+i, yoko+j]
                if not (0<=now[0]<H and 0<=now[1]<W):
                    continue
                if group[now[0]][now[1]] == -1:
                    continue
                
                if group[i][j] != group[now[0]][now[1]]:
                    can_waap[group[i][j]].add(group[now[0]][now[1]])
                    can_waap[group[now[0]][now[1]]].add(group[i][j])

start = group[C[0]][C[1]]
goal = group[D[0]][D[1]]
import sys
import copy
seen = set([start])
nows = [start]

if start==goal:
    print(0)
    sys.exit()
for step in range(now_group+1):
    pre_nows = copy.deepcopy(nows)
    nows = []
    for pre_now in pre_nows:
        for j in can_waap[pre_now]:
            if j not in seen:
                seen.add(j)
                nows.append(j)
                if j == goal:
                    print(step+1)
                    sys.exit()

print(-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

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

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

for i in range(H):
  s.append(input())
  
q = deque()
inf = 10**9
dist = [[inf] * W for i in range(H)]
q.append([si,sj])
dist[si][sj] = 0

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



from collections import deque
H,W = map(int,input().split())
sx,sy = map(int,input().split())
gx,gy = map(int,input().split())
sx,sy,gx,gy = sx-1,sy-1,gx-1,gy-1

C=[list(input()) for i in range(H)]
inf = float("inf")

for i in range(H):
    for j in range(W):
        if C[i][j] == ".":
            C[i][j] =0
        else:
            C[i][j]=1

d0=[[1,0],[0,1],[-1,0],[0,-1]]
d1=[[-2,-2],[-2,-1],[-2,0],[-2,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]]

dist = [[inf]*W for i in range(H)]
dist[sx][sy]=0
que=deque([[0,sx,sy]])

while que:
    L,x,y = que.popleft()
    for dx,dy in d0:
        nx,ny=x+dx,y+dy
        if 0<=nx<H and 0<=ny<W and L < dist[nx][ny] and C[nx][ny]==0:
            dist[nx][ny] = L
            que.appendleft([L,nx,ny])
            
    for dx,dy in d1:
        nx,ny=x+dx,y+dy
        if 0<=nx<H and 0<=ny<W and L+1 < dist[nx][ny] and C[nx][ny]==0:
            dist[nx][ny] = L+1
            que.append([L+1,nx,ny])
ans=dist[gx][gy]
if ans==inf:print(-1)
else: print(ans)

Solution (Python):



from collections import deque
H,W = map(int,input().split())
sx,sy = map(int,input().split())
gx,gy = map(int,input().split())
sx,sy,gx,gy = sx-1,sy-1,gx-1,gy-1

C=[list(input()) for i in range(H)]
inf = float("inf")

for i in range(H):
    for j in range(W):
        if C[i][j] == ".":
            C[i][j] =0
        else:
            C[i][j]=1

d0=[[1,0],[0,1],[-1,0],[0,-1]]
d1=[[-2,-2],[-2,-1],[-2,0],[-2,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]]

dist = [[inf]*W for i in range(H)]
dist[sx][sy]=0
que=deque([[0,sx,sy]])

while que:
    L,x,y = que.popleft()
    for dx,dy in d0:
        nx,ny=x+dx,y+dy
        if 0<=nx<H and 0<=ny<W and L+C[nx][ny] < dist[nx][ny] and C[nx][ny]==0:
            dist[nx][ny] = L+C[nx][ny]
            que.appendleft([L,nx,ny])
            
    for dx,dy in d1:
        nx,ny=x+dx,y+dy
        if 0<=nx<H and 0<=ny<W and L+C[nx][ny]+1 < dist[nx][ny] and C[nx][ny]==0:
            dist[nx][ny] = L+C[nx][ny]+1
            que.append([L+1,nx,ny])
ans=dist[gx][gy]
if ans==inf:print(-1)
else: print(ans)

Solution (Python):



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

Solution (Python):
from collections import deque

INF = 10 ** 12

class BFS:
    def __init__(self, H, W, S, C, D):
        self.H = H
        self.W = W
        self.S = S
        
        self.C = C
        
        self.D = D

        
        
        
        
        
        self.board_states = [[INF] * W for i in range(H)]
        self.board_states[C[0]][C[1]] = 0
        self.queue = deque([C])

    def is_legal_move(self, move):
        h = move[0]
        w = move[1]

        if h < 0 or h >= self.H or w < 0 or w >= self.W:
            return False
        return self.S[h][w] == "."

    def walk(self):
        while len(self.queue) > 0:
            move = self.queue.popleft()
            step_count = self.get_boart_states(move)

            if move == self.D:
                return

            up = (move[0]-1, move[1])
            down = (move[0]+1, move[1])
            left = (move[0], move[1]-1)
            right = (move[0], move[1]+1)

            next_moves = list(filter(self.is_legal_move, [up, down, left, right]))

            for next_move in next_moves:
                if self.get_boart_states(next_move) > step_count:
                    
                    self.queue.appendleft(next_move)
                    self.set_boart_states(next_move, step_count)

            for i in range(-2, 3):
                for j in range(-2, 3):
                    next_move = (move[0]+i, move[1]+j)
                    if not self.is_legal_move(next_move):
                        continue

                    if self.get_boart_states(next_move) > step_count + 1:
                        self.queue.append(next_move)
                        self.set_boart_states(next_move, step_count + 1)

    def set_boart_states(self, move, value):
        self.board_states[move[0]][move[1]] = value

    def get_boart_states(self, move):
        return self.board_states[move[0]][move[1]]

    def print_board_states(self):
        for l in self.board_states:
            print(l)

H, W = map(int, input().split())
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 = [ [None] * W for i in range(H) ]
for i in range(H):
    l = input()
    for j, s in enumerate(l):
        S[i][j] = s

bfs = BFS(H, W, S, (C_h, C_w), (D_h, D_w))
bfs.walk()
goal_state = bfs.get_boart_states((D_h, D_w))
print(goal_state if goal_state != INF else -1)

Solution (Python):
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 = H * W
 
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
 







 
num_step = [[INF for w in range(W)] for h in range(H)]
num_step[Ch - 1][Cw - 1] = 0
 

queue = [(Ch - 1, Cw - 1)]
num_warp = 0
 

while not queue == []:
    magic_tiles = []
    while not queue == []:
        h = queue.pop() 
        if h[0] == Dh - 1 and h[1] == Dw - 1:
            print(num_warp)
            exit()
        
        
        
        
        
        for i in range(4):
            if 0 <= h[0]+dy[i] < H and 0 <= h[1]+dx[i] < W and S[h[0]+dy[i]][h[1]+dx[i]] == '.' \
                 and num_step[h[0]+dy[i]][h[1]+dx[i]] > num_warp:
                queue.append((h[0]+dy[i], h[1]+dx[i]))
                num_step[h[0]+dy[i]][h[1]+dx[i]] = num_warp
 
        
        mx = [-2, -1 , 0, 1, 2]
        my = [-2, -1 , 0, 1, 2]
 
        for x in mx:
            for y in my:
                 if 0 <= h[0] + y < H and 0 <= h[1] + x < W and S[h[0] + y][h[1] + x] == '.' \
                     and num_step[h[0] + y][h[1] + x] == INF:
                    magic_tiles.append((h[0] + y, h[1] + x))
 
    num_warp += 1
 
    
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            num_step[magic[0]][magic[1]] = num_warp
            queue.append((magic[0],magic[1]))
 
print(-1)