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



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    def bfs(start, goal):
        sy, sx = start
        gy, gx = goal
        q = deque()
        q.append(start)
        ans[sy][sx] = 0

        while q:
            sy, sx = q.popleft()
            # if sy == gy and sx == gx:
            #     return print(ans[gy][gx])
            for dy, dx in drc4:
                ny, nx = dy + sy, dx + sx
                # if G[ny][nx] == "@" or ans[ny][nx] != INF:
                #     if G[ny][nx] != "#":
                #         continue
                if G[ny][nx] == "." and ans[ny][nx] > ans[sy][sx]:
                    ans[ny][nx] = ans[sy][sx]
                    q.append((ny, nx))

            for dy8 in range(-2, 3):
                for dx8 in range(-2, 3):
                    ny8, nx8 = dy8 + sy, dx8 + sx
                    if 1 <= ny8 <= H + 1 and 1 <= nx8 <= W + 1:
                        # if G[ny8][nx8] == "#":
                        #     continue
                        # if G[ny8][nx8] == "@" or ans[ny8][nx8] != INF:
                        #     continue
                        if G[ny8][nx8] == "." and ans[ny8][nx8] > ans[sy][sx] + 1:
                            ans[ny8][nx8] = ans[sy][sx] + 1
                            q.append((ny8, nx8))
        # return print(-1)

    H, W = map(int, input().split())
    sy, sx = map(int, input().split())
    gy, gx = map(int, input().split())
    G = []
    G.append(["@"] * (W + 2))
    G += [["@"] + list(input()) + ["@"] for _ in range(H)]
    G.append(["@"] * (W + 2))

    # visited = [[False] * (W + 2) for _ in range(H+2)]
    INF = 10 ** 7
    ans = [[INF] * (W + 2) for _ in range(H + 2)]

    bfs((sy, sx), (gy, gx))

    print(ans[gy][gx] if ans[gy][gx] < INF else '-1')


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

"""
ダイクストラ　ギリギリ
"""
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
area = [list(input()) for _ in range(h)]
inf = 10**100
dist = [[inf]*w for i in range(h)]

dwalk = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def Dijkstra(ch, cw):
    import heapq
    edgelist = [(0, ch, cw)]
    heapq.heapify(edgelist)
    dist[ch][cw] = 0
    while len(edgelist):
        cost, y, x = heapq.heappop(edgelist)
        if y==dh and x==dw:
            return dist
        # この枝刈がないと通らない
        if dist[y][x] < cost: continue
        for next_y, next_x in dwalk:
            if 0<=y+next_y<h and 0<=x+next_x<w:
                if area[y+next_y][x+next_x]=='#': continue
                if dist[y+next_y][x+next_x]>cost:
                    dist[y+next_y][x+next_x] = cost
                    heapq.heappush(edgelist, (cost, y+next_y, x+next_x))
        for next_y in range(-2, 3):
            for next_x in range(-2, 3):
                    if 0<=y+next_y<h and 0<=x+next_x<w:
                        if area[y+next_y][x+next_x]=='#': continue
                        if dist[y+next_y][x+next_x]>cost+1:
                            dist[y+next_y][x+next_x] = cost+1
                            heapq.heappush(edgelist, (cost+1, y+next_y, x+next_x))
    return dist

dist = Dijkstra(ch, cw)
if dist[dh][dw] == inf:
    print(-1)
else:
    print(dist[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
C0, C1 = map(int, input().split())
D0, D1 = map(int, input().split())

ARR = []

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


def calculate(h, w, c0, c1, d0, d1, arr):
    c0 = c0 - 1
    c1 = c1 - 1
    d0 = d0 - 1
    d1 = d1 - 1

    status = []
    for i in range(H):
        tmp = []
        for j in range(W):
            tmp.append(-1)
        status.append(tmp)

    q = deque()

    q.append((c0, c1, 0))

    while len(q) > 0:
        hIndex, wIndex, index = q.popleft()


        sss = [(hIndex,wIndex - 1), (hIndex, wIndex + 1), ( hIndex - 1, wIndex), (hIndex + 1, wIndex)]


        for sH, sW in sss:
            if (sH >= 0) and (sH < h) and (sW >= 0) and (sW < w):
                if arr[sH][sW] == '.':
                    tmpIndex = index
                    if status[sH][sW] == -1:
                        status[sH][sW] = tmpIndex
                        q.append((sH, sW, tmpIndex))
                    else:
                        if status[sH][sW] > tmpIndex:
                            status[sH][sW] = tmpIndex
                            q.append((sH, sW, tmpIndex))

        for _hIndex in range(hIndex - 2, hIndex + 3):
            for _wIndex in range(wIndex - 2, wIndex + 3):
                if (_hIndex == hIndex) and (_wIndex == wIndex):
                    continue
                if (_hIndex == c0) and (_wIndex == c1):
                    continue
                if (_hIndex, _wIndex) in sss:
                    continue
                if (_hIndex >= 0 and _hIndex < h) and (_wIndex >= 0 and _wIndex < w):
                    if arr[_hIndex][_wIndex] == '.':
                        tmpIndex = index + 1
                        if status[_hIndex][_wIndex] == -1:
                            status[_hIndex][_wIndex] = tmpIndex
                            q.append((_hIndex, _wIndex, tmpIndex))
                        else:
                            if status[_hIndex][_wIndex] > tmpIndex:
                                status[_hIndex][_wIndex] = tmpIndex
                                q.append((_hIndex, _wIndex, tmpIndex))

    if status[d0][d1] >= 0:
        print(status[d0][d1])
    else:
        print(-1)


calculate(H, W, C0, C1, D0, D1, ARR)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
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
area = [list(input()) for _ in range(h)]
inf = 10**100
dist = [[inf]*w for i in range(h)]

dwalk = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def Dijkstra(ch, cw):
    import heapq
    edgelist = [(0, ch, cw)]
    heapq.heapify(edgelist)
    dist[ch][cw] = 0
    while len(edgelist):
        cost, y, x = heapq.heappop(edgelist)
        if y==dh and x==dw:
            return dist
        for next_y, next_x in dwalk:
            if 0<=y+next_y<h and 0<=x+next_x<w:
                if area[y+next_y][x+next_x]=='#': continue
                if dist[y+next_y][x+next_x]>cost:
                    dist[y+next_y][x+next_x] = cost
                    heapq.heappush(edgelist, (cost, y+next_y, x+next_x))
        for next_y in range(-2, 3):
            for next_x in range(-2, 3):
                    if 0<=y+next_y<h and 0<=x+next_x<w:
                        if area[y+next_y][x+next_x]=='#': continue
                        if dist[y+next_y][x+next_x]>cost+1:
                            dist[y+next_y][x+next_x] = cost+1
                            heapq.heappush(edgelist, (cost+1, y+next_y, x+next_x))
    return dist

dist = Dijkstra(ch, cw)
if dist[dh][dw] == inf:
    print(-1)
else:
    print(dist[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
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
area = [list(input()) for _ in range(h)]
inf = 10**100
dist = [[inf]*w for i in range(h)]

dwalk = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def Dijkstra(ch, cw):
    import heapq
    edgelist = [(0, ch, cw)]
    heapq.heapify(edgelist)
    dist[ch][cw] = 0
    while len(edgelist):
        cost, y, x = heapq.heappop(edgelist)
        dist[y][x] = cost
        if y==dh and x==dw:
            return dist
        for next_y, next_x in dwalk:
            if 0<=y+next_y<h and 0<=x+next_x<w:
                if area[y+next_y][x+next_x]=='#': continue
                if dist[y+next_y][x+next_x]>cost:
                    dist[y+next_y][x+next_x] = cost
                    heapq.heappush(edgelist, (cost, y+next_y, x+next_x))
        for next_y in range(-2, 3):
            for next_x in range(-2, 3):
                    if 0<=y+next_y<h and 0<=x+next_x<w:
                        if area[y+next_y][x+next_x]=='#': continue
                        if dist[y+next_y][x+next_x]>cost+1:
                            dist[y+next_y][x+next_x] = cost+1
                            heapq.heappush(edgelist, (cost+1, y+next_y, x+next_x))
    return dist

dist = Dijkstra(ch, cw)
if dist[dh][dw] == inf:
    print(-1)
else:
    print(dist[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
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
area = [list(input()) for _ in range(h)]
inf = 10**100
dist = [[inf]*w for i in range(h)]

dwalk = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def Dijkstra(ch, cw):
    import heapq
    edgelist = [(0, ch, cw)]
    heapq.heapify(edgelist)
    dist[ch][cw] = 0
    while len(edgelist):
        cost, y, x = heapq.heappop(edgelist)
        dist[y][x] = cost
        if y==dh and x==dw:
            return dist
        for next_y, next_x in dwalk:
            if 0<=y+next_y<h and 0<=x+next_x<w:
                if area[y+next_y][x+next_x]=='#': continue
                if dist[y+next_y][x+next_x]>cost:
                    dist[y+next_y][x+next_x] = cost
                    heapq.heappush(edgelist, (cost, y+next_y, x+next_x))
        for next_y in range(-2, 3):
            for next_x in range(-2, 3):
                    if 0<=y+next_y<h and 0<=x+next_x<w:
                        if area[y+next_y][x+next_x]=='#': continue
                        if dist[y+next_y][x+next_x]>cost+1:
                            dist[y+next_y][x+next_x] = cost+1
                            heapq.heappush(edgelist, (cost+1, y+next_y, x+next_x))
    return dist

dist = Dijkstra(ch, cw)
if dist[dh][dw] == inf:
    print(-1)
else:
    print(dist[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import heapq

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()))
  
dpat = ((-1,0),(1,0),(0,-1),(0,1))
mpat = []
for i in range(-2,3):
  for j in range(-2,3):
    if (i,j) in dpat:
      continue
    if i == j and j == 0:
      continue
    mpat.append((i,j))
                
#print(mpat)

#dij
seen = [[False] * W for _ in range(H)]
h = []
# count_of_magic,x,y
heapq.heappush(h, (0,Ch,Cw))
while h:
  c,x,y = heapq.heappop(h)
  if seen[x][y]:
    continue
  seen[x][y] = True
  #print(c,x,y)
  if x == Dh and y == Dw:
    print(c)
    exit(0)
  for dx,dy in dpat:
    nx,ny = x+dx, y+dy
    if 0<=nx<H and 0<=ny<W:
      if seen[nx][ny] or S[nx][ny] == "#":
        continue
      heapq.heappush(h, (c,nx,ny))
  for dx,dy in mpat:
    nx,ny = x+dx, y+dy
    if 0<=nx<H and 0<=ny<W:
      if seen[nx][ny] or S[nx][ny] == "#":
        continue
      heapq.heappush(h, (c+1,nx,ny))
      
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.componentCount = size

    def root(self, index):
        if self.parent[index] == index:  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2):  # 結合
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2:  # 連結されている場合
            return

        self.componentCount -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2]:
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else:
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2]:
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2):
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index):
        return self.size[self.root(index)]

H, W = map(int, input().split())
C = tuple(map(int, input().split()))
D = tuple(map(int, input().split()))
S = [input() for _ in range(H)]

def cord(h, w):
    return h * W + w

tree = UnionFind(H * W + 100)

for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue

        for dh, dw in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            toH, toW = h + dh, w + dw

            if 0 <= toH < H and 0 <= toW < W and S[toH][toW] == '.':
                tree.union(cord(h, w), cord(toH, toW))

roots = [tree.root(i) for i in range(H * W)]
M = max(roots) + 1
edges = [set() for _ in range(M)]

def search(h, w):
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            toH, toW = h + dh, w + dw
            if 0 <= toH < H and 0 <= toW < W and S[toH][toW] == '.':
                if roots[cord(h, w)] == roots[cord(toH, toW)]:
                    continue
                edges[roots[cord(h, w)]].add(roots[cord(toH, toW)])

for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue
        search(h, w)

edges = [list(e) for e in edges]

S = roots[cord(C[0] - 1, C[1] - 1)]
T = roots[cord(D[0] - 1, D[1] - 1)]

INF = 10**18
que = deque([(S, 0)])
minDist = [INF] * M
minDist[S] = 0

while que:
    now, dist = que.popleft()

    for to in edges[now]:
        if minDist[to] > dist + 1:
            minDist[to] = dist + 1
            que.append((to, dist + 1))

print(minDist[T] if minDist[T] < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
import numba
from numba import jit

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [list(map(str, input().split())) for i in range(H)]
inf = float("inf")
dp = [[inf for i in range(W)] for i in range(H)]
dp[Ch-1][Cw-1] = 0
walk_move = [[-1, 0], [0, -1], [0, 1], [1, 0]]
magic_move = []
for a in range(-2, 3):
  for b in range(-2, 3):
    magic_move.append([a, b])

move_lis = [[Ch-1, Cw-1]]
already_lis = [[Ch-1, Cw-1]]

@jit
def main(move_lis, already_lis):
  while True:
    new_move_lis  = []
    for i,j in move_lis:
      if maze[i][0][j] == "#":
        continue
      for k,l in walk_move:
        if 0 <= i+k <= H-1 and 0 <= j+l <= W-1 and maze[i+k][0][j+l] == "." and not [i+k, j+l] in already_lis:
          dp[i+k][j+l] = min(dp[i+k][j+l], dp[i][j])
          new_move_lis.append([i+k, j+l])
          already_lis.append([i+k, j+l])
    if not len(new_move_lis):
      new_already_lis = []
      for o,p in already_lis:
        for m,n in magic_move:
          if not m and not n:
            continue
          if 0 <= o+m <= H-1 and 0 <= p+n <= W-1 and maze[o+m][0][p+n] == ".":
            dp[o+m][p+n] = min(dp[o+m][p+n], dp[o][p]+1)
            new_move_lis.append([o+m, p+n])
            new_already_lis.append([o+m, p+n])
      already_lis = new_already_lis
    if not len(new_move_lis) or dp[Dh-1][Dw-1] != inf:
      break
    else:
      move_lis = new_move_lis
  return dp[Dh-1][Dw-1]

ans = main(move_lis, already_lis)

if ans == inf:
  print("-1")
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [list(map(str, input().split())) for i in range(H)]
inf = float("inf")
dp = [[inf for i in range(W)] for i in range(H)]
dp[Ch-1][Cw-1] = 0
walk_move = [[-1, 0], [0, -1], [0, 1], [1, 0]]
magic_move = []
for a in range(-2, 3):
  for b in range(-2, 3):
    magic_move.append([a, b])

move_lis = [[Ch-1, Cw-1]]
already_lis = [[Ch-1, Cw-1]]
while True:
  new_move_lis  = []
  for i,j in move_lis:
    if maze[i][0][j] == "#":
      continue
    for k,l in walk_move:
      if 0 <= i+k <= H-1 and 0 <= j+l <= W-1 and maze[i+k][0][j+l] == "." and not [i+k, j+l] in already_lis:
        dp[i+k][j+l] = min(dp[i+k][j+l], dp[i][j])
        new_move_lis.append([i+k, j+l])
        already_lis.append([i+k, j+l])
  if not len(new_move_lis):
    new_already_lis = []
    for o,p in already_lis:
      for m,n in magic_move:
        if not m and not n:
          continue
        if 0 <= o+m <= H-1 and 0 <= p+n <= W-1 and maze[o+m][0][p+n] == ".":
          dp[o+m][p+n] = min(dp[o+m][p+n], dp[o][p]+1)
          new_move_lis.append([o+m, p+n])
          new_already_lis.append([o+m, p+n])
    already_lis = new_already_lis
  if not len(new_move_lis) or dp[Dh-1][Dw-1] != inf:
    break
  else:
    move_lis = new_move_lis

if dp[Dh-1][Dw-1] == inf:
  print("-1")
else:
  print(dp[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
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

squares = []
for i in range(H):
    squares.append([None]*(W))

for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            squares[i][j] = -1  # Wall

squares[Ch][Cw]=0

d = deque()
d.append([Ch, Cw])

steps = [[-1,0],[1,0],[0,-1],[0,1]]

warps = 0

def visit(i1, j1, i2, j2):  # (i1,j1) to (i2,j2)
    if i2 < 0 or i2 >= H or j2 < 0 or j2 >= W:
        return
    sq2 = squares[i2][j2]
    if sq2 == -1:
        return
    if sq2 == None:
        squares[i2][j2] = warps  # sq2 = warps <- doesn't work
        d.append([i2, j2])
        if i2 == Dh and j2 == Dw:
            print(warps)
            exit()

while (len(d)>0):
    while (len(d)>0):
        src = d.popleft()
        for st in steps:
            visit(src[0], src[1], src[0]+st[0], src[1]+st[1])
    warps += 1
    for i in range(H):
        for j in range(W):
            sq = squares[i][j]
            if sq == warps - 1:
                for di in range(-2,3):
                    for dj in range(-2,3):
                        visit(i, j, i+di, j+dj)

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
from numba import jit
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
road_map = []
for i in range(h):
    road = input()
    road_map.append(road)

@jit
def solve(h,w,ch,cw,dh,dw,road_map):

    queue = []
    heapq.heappush(queue,[0,ch-1,cw-1])

    used_map = [[-1]*w for _ in range(h)]
    layer_set = set()
    layer_set.add((ch-1,cw-1))
    loop = 0
    while used_map[dh-1][dw-1] == -1 and queue != []:
        #move walk
        while queue != []:
            dot = heapq.heappop(queue)
            if dot[1] < 0 or dot[2] < 0 or dot[1] >= h or dot[2] >= w:
                continue
            if used_map[dot[1]][dot[2]] > -1 and used_map[dot[1]][dot[2]] <= dot[0]:
                continue
            if road_map[dot[1]][dot[2]] == "#":
                continue
            used_map[dot[1]][dot[2]] = dot[0]
            layer_set.add((dot[1],dot[2]))

            if not (dot[2] - 1 < 0):
                heapq.heappush(queue,[dot[0],dot[1],dot[2]-1])
            if not (dot[2] + 1 >= w):
                heapq.heappush(queue,[dot[0],dot[1],dot[2]+1])
            if not (dot[1]+1 >= h):
                heapq.heappush(queue,[dot[0],dot[1]+1,dot[2]])
            if not (dot[1]-1 < 0):
                heapq.heappush(queue,[dot[0],dot[1]-1,dot[2]])

        temp = []
        for s in layer_set:
            for x in range(-2,3,1):
                for y in range(-2,3,1):
                    if not(s[0]+ x < 0 or s[1]+y < 0 or s[0]+x >= h or s[1]+y >= w):
                        if used_map[s[0]+x][s[1]+y] == -1 and road_map[s[0]+x][s[1]+y] == ".":
                            temp = [s[0]+x,s[1]+y]
                            heapq.heappush(queue,[loop+1,temp[0],temp[1]])
            
        loop+=1

    print(used_map[dh-1][dw-1])

solve(h,w,ch,cw,dh,dw,road_map)

Submission status: Time Limit Exceeded

Solution code:
import heapq
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
road_map = []
for i in range(h):
    road = input()
    road_map.append(road)
queue = []
heapq.heappush(queue,[0,ch-1,cw-1])
used_map = [[-1]*w for _ in range(h)]

layer_set = set()
layer_set.add((ch-1,cw-1))
loop = 0
while used_map[dh-1][dw-1] == -1 and queue != []:
    #move walk
    while queue != []:
        dot = heapq.heappop(queue)
        if dot[1] < 0 or dot[2] < 0 or dot[1] >= h or dot[2] >= w:
            continue
        if used_map[dot[1]][dot[2]] > -1 and used_map[dot[1]][dot[2]] <= dot[0]:
            continue
        if road_map[dot[1]][dot[2]] == "#":
            continue
        used_map[dot[1]][dot[2]] = dot[0]
        layer_set.add((dot[1],dot[2]))

        if not (dot[2] - 1 < 0):
            heapq.heappush(queue,[dot[0],dot[1],dot[2]-1])
        if not (dot[2] + 1 >= w):
            heapq.heappush(queue,[dot[0],dot[1],dot[2]+1])
        if not (dot[1]+1 >= h):
            heapq.heappush(queue,[dot[0],dot[1]+1,dot[2]])
        if not (dot[1]-1 < 0):
            heapq.heappush(queue,[dot[0],dot[1]-1,dot[2]])

    temp = []
    for s in layer_set:
        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if not(s[0]+ x < 0 or s[1]+y < 0 or s[0]+x >= h or s[1]+y >= w):
                    if used_map[s[0]+x][s[1]+y] == -1 and road_map[s[0]+x][s[1]+y] == ".":
                        temp = [s[0]+x,s[1]+y]
                        heapq.heappush(queue,[loop+1,temp[0],temp[1]])
        
    loop+=1
    
print(used_map[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
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)]
visited=[[-1]*W for _ in range(H)]
visited[ch-1][cw-1]=0
h=deque([(ch-1,cw-1)])
c=0
while 1:
  done=[]
  while h:
    cx,cy=h.popleft()
    done.append((cx,cy))
    for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
      nx,ny = cx+dx,cy+dy
      if 0<=nx<H and 0<=ny<W and S[nx][ny]=='.' and visited[nx][ny]==-1:
        h.append((nx,ny))
        visited[nx][ny]=c
  for cx,cy in done:
    for dx in range(-2,3):
      for dy in range(-2,3):
        nx,ny = cx+dx,cy+dy
        if 0<=nx<H and 0<=ny<W and S[nx][ny]=='.' and visited[nx][ny]==-1:
          h.append((nx,ny))
          visited[nx][ny]=c+1
  if not h or visited[dh-1][dw-1]!=-1:
    break
  c+=1
print(visited[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
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
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
t = [list(input()) for _ in range(h)]
d = deque([(Ch, Cw)])
d2 = deque()
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = range(-2, 3)

while True:
  # 移動A
  while len(d) != 0:
    Th, Tw = d.popleft()
    d2.append((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  while len(d2) != 0:
    Th, Tw = d2.popleft()
    for i in b :
      for j in b :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
          visited[Th][Tw] = 1
  if len(d) == 0:
    print('-1')
    exit()

Submission status: Time Limit Exceeded

Solution code:
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
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
t = [list(input()) for _ in range(h)]
d = deque([(Ch, Cw)])
d2 = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = range(-2, 3)

while True:
  # 移動A
  while len(d) != 0:
    Th, Tw = d.popleft()
    d2.append((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  while len(d2) != 0:
    Th, Tw = d2.popleft()
    for i in b :
      for j in b :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
          visited[Th][Tw] = 1
  if len(d) == 0:
    print('-1')
    exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

int1 = lambda x: int(x) - 1

H, W = map(int, input().split())
Ch, Cw = map(int1, input().split())
Dh, Dw = map(int1, input().split())
S = [[0 if s == '.' else -1 for s in input()] for _ in range(H)]

d = deque([(Ch, Cw)])
cur = 0
while True:
    visited = set()
    while d:
        h, w = d.pop()
        visited.add((h, w))
        S[h][w] = cur
        if (h, w) == (Dh, Dw):
            print(cur)
            exit()
        for dh, dw in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            if 0 <= h + dh < H and 0 <= w + dw < W and S[h + dh][w + dw] == 0:
                d.append((h + dh, w + dw))

    for h, w in visited:
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                if 0 <= h + dh < H and 0 <= w + dw < W and S[h + dh][w + dw] == 0:
                    d.append((h + dh, w + dw))
    if not d:
        print(-1)
        exit()
    cur += 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

int1 = lambda x: int(x) - 1

H, W = map(int, input().split())
Ch, Cw = map(int1, input().split())
Dh, Dw = map(int1, input().split())
S = [[0 if s == '.' else -1 for s in input()] for _ in range(H)]

d = deque([(Ch, Cw)])
cur = 1
while True:
    visited = set()
    while d:
        h, w = d.pop()
        visited.add((h, w))
        S[h][w] = cur
        if (h, w) == (Dh, Dw):
            print(cur - 1)
            exit()
        for dh, dw in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            if 0 <= h + dh < H and 0 <= w + dw < W and S[h + dh][w + dw] == 0:
                d.append((h + dh, w + dw))

    for h, w in visited:
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                if 0 <= h + dh < H and 0 <= w + dw < W and S[h + dh][w + dw] == 0:
                    d.append((h + dh, w + dw))
    if not d:
        print(-1)
        exit()
    cur += 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
A = [[i for i in input()] for _ in range(H)]
h = deque()
h.append((Ch - 1, Cw - 1))
c = 0
while True :
  done =deque()
  while h :
    cy, cx = h.popleft()
    done.append((cy, cx))
    A[cy][cx] = c
    for dy, dx in ((0, 1), (0, -1), (1, 0), (-1, 0)) :
      ny, nx = cy + dy, cx + dx
      if 0 <= ny < H and 0 <= nx < W and A[ny][nx] == '.':
        h.append((ny, nx))
        A[ny][nx] = c

  h = deque()
  for cy, cx in done :
    for dy in range(-2, 3) :
      for dx in range(-2, 3) :
        ny, nx = cy + dy, cx + dx
        if 0 <= ny < H and 0 <= nx < W and A[ny][nx] == '.':
          h.append((ny, nx))
  if not h :
    break
  c += 1  
if A[Dh - 1][Dw - 1] != ".":
    print(A[Dh - 1][Dw - 1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
A = [[i for i in input()] for _ in range(H)]

h = [(Ch - 1, Cw - 1)]
c = 0
while True :
  done = []
  while h :
    cy, cx = h.pop()
    done.append((cy, cx))
    A[cy][cx] = c
    for dy, dx in ((0, 1), (0, -1), (1, 0), (-1, 0)) :
      ny, nx = cy + dy, cx + dx
      if 0 <= ny < H and 0 <= nx < W and A[ny][nx] == '.':
        h.append((ny, nx))
        A[ny][nx] = c

  h = []
  for cy, cx in done :
    for dy in range(-2, 3) :
      for dx in range(-2, 3) :
        ny, nx = cy + dy, cx + dx
        if 0 <= ny < H and 0 <= nx < W and A[ny][nx] == '.':
          h.append((ny, nx))
  if not h :
    break
  c += 1  
if A[Dh - 1][Dw - 1] != ".":
    print(A[Dh - 1][Dw - 1])
else:
    print(-1)