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

Ch,Cw=Ch-1,Cw-1
Dh,Dw=Dh-1,Dw-1
from heapq import heappop,heappush
todo=[[0,Ch,Cw]]
d=[[-1]*w for _ in range(h)]
d[Ch][Cw]=0
toho=[[0,1],[0,-1],[1,0],[-1,0]]
wiz=[[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]
while todo:
  cnt,nh,nw=heappop(todo)
  if d[nh][nw]<cnt:continue
  if [nh,nw]==[Dh,Dw]:
    print(cnt)
    exit()
  for dh,dw in toho:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='#':
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt:
        d[nh+dh][nw+dw]=cnt
        heappush(todo,[cnt,nh+dh,nw+dw])
  for dh,dw in wiz:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='#':
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt+1:
        d[nh+dh][nw+dw]=cnt+1
        heappush(todo,[cnt+1,nh+dh,nw+dw])
print(d[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
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()))
    grid = [list(input()) for _ in range(h)]
    q = deque([c])
    max_val = 10 ** 10
    dist = [[max_val for _ in range(w)] for _ in range(h)]
    dist[c[0]][c[1]] = 0
    next_d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    while q:
        now_x, now_y = q.pop()
        for dx, dy in next_d:
            nx = now_x + dx
            ny = now_y + dy
            if not (0 <= nx < h and 0 <= ny < w):
                continue
            elif grid[nx][ny] == "#":
                continue
            if dist[nx][ny] > dist[now_x][now_y]:
                dist[nx][ny] = dist[now_x][now_y]
                if [nx, ny] == d:
                    continue
                q.appendleft([nx, ny])
        for dx, dy in [[0, 1], [0, 2], [1, 0], [1, 2], [1, 1], [2, 2], [2, 0], [2, 1]]:
            for cx, cy in [[1, 1], [1, -1], [-1, -1], [-1, 1]]:
                nx = now_x + dx * cx
                ny = now_y + dy * cy
                if not (0 <= nx < h and 0 <= ny < w):
                    continue
                elif grid[nx][ny] == "#":
                    continue
                if dist[nx][ny] > dist[now_x][now_y] + 1:
                    dist[nx][ny] = dist[now_x][now_y] + 1
                    if [nx, ny] == d:
                        continue
                    q.append([nx, ny])
    print(dist[d[0]][d[1]] if dist[d[0]][d[1]] != max_val else -1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w = LI()
ch, cw = LI()
dh, dw = LI()
s = [input() for _ in range(h)]

dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
d = [[10**10] * w for _ in range(h)]
d[ch-1][cw-1] = 0
H = []
heappush(H, (0, cw-1, ch-1))
while H:
    D, x, y = heappop(H)
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if s[ny][nx] == '.' and d[ny][nx] > D:
                d[ny][nx] = D
                heappush(H, (D, nx, ny))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx, ny = x + i, y + j
            if 0 <= nx < w and 0 <= ny < h:
                if s[ny][nx] == '.' and d[ny][nx] > D + 1:
                    d[ny][nx] = D + 1
                    heappush(H, (D + 1, nx, ny))
if d[dh-1][dw-1] == 10**10:
    print(-1)
else:
    print(d[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
b = read().split()

sh -= 1; sw -= 1; gh -= 1; gw -= 1

#print(b)

from collections import deque

def nbd(nh,nw,cost,dv):
    if 0 <= nh < h and 0 <= nw < w and b[nh][nw]==".":
        dv += cost
        if dv < res[nh][nw]:
            res[nh][nw] = dv
            if cost: q.append((dv,nh,nw))
            else: q.appendleft((dv,nh,nw))
    return 


INF = 1<<30
res = [[INF]*w for _ in range(h)] #startからの最短距離
res[sh][sw] = 0
q = deque([(0,sh,sw)]) #(そこまでの距離、点)
while q:
    dv,vh,vw = q.popleft()
    if res[vh][vw] < dv: continue
    if vh==gh and vw==gw: break
    nbd(vh-1,vw,0,dv)
    nbd(vh,vw-1,0,dv)
    nbd(vh+1,vw,0,dv)
    nbd(vh,vw+1,0,dv)

    nbd(vh-1,vw-1,1,dv)
    nbd(vh-1,vw+1,1,dv)
    nbd(vh+1,vw-1,1,dv)
    nbd(vh+1,vw+1,1,dv)

    for i in range(-2,3):
        nbd(vh-2,vw+i,1,dv)
        nbd(vh+2,vw+i,1,dv)

    for i in range(-1,2):
        nbd(vh+i,vw-2,1,dv)
        nbd(vh+i,vw+2,1,dv)
    
    #print(res)
        
ans = res[gh][gw]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    CH, CW = [int(x) - 1 for x in input().split()]
    DH, DW = [int(x) - 1 for x in input().split()]
    S = [input().strip() for _ in range(H)]

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

    visited = [[float("inf")] * W for _ in range(H)]

    q = collections.deque()
    visited[CH][CW] = 0
    q.append((CH, CW))
    while q:
        cx, cy = q.popleft()
        cc = visited[cx][cy]

        # 隣接
        for nx, ny in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            nnx = cx + nx
            nny = cy + ny
            if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                if S[nnx][nny] == "." and visited[nnx][nny] > cc:
                    q.append((nnx, nny))
                    visited[nnx][nny] = cc

        # ワープ
        for nx, ny in warp:
            nnx = cx + nx
            nny = cy + ny
            if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                if S[nnx][nny] == "." and visited[nnx][nny] > cc:
                    q.append((nnx, nny))
                    visited[nnx][nny] = cc + 1

    if visited[DH][DW] == float("inf"):
        print(-1)
    else:
        print(visited[DH][DW])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import heapq
INF = 10**9

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
        return self.dist

h, w = map(int, input().split())
ch, cw = map(int, input().split())
ch -= 1; cw -= 1
dh, dw = map(int, input().split())
dh -= 1; dw -= 1
field = []
is_blank = True
for _ in range(h):
    line = input().rstrip()
    field.append(line)
    if "#" in line:
        is_blank = False
if is_blank:
    print(0)
    exit()

edge = [[] for _ in range(h * w)]
for i in range(h):
    for j in range(w):
        frm = i * w + j
        for dx in range(-2, 3):
            nx = i + dx
            if nx < 0 or nx > h - 1:
                continue
            for dy in range(-2, 3):
                if dx == 0 and dy == 0:
                    continue
                ny = j + dy
                if ny < 0 or ny > w - 1:
                    continue
                if field[nx][ny] == "#":
                    continue
                dist = abs(dx) + abs(dy)
                if dist == 1:
                    edge[frm].append((nx*w + ny, 0))
                else:
                    edge[frm].append((nx*w + ny, 1))
        
DIJK = Dijkstra(edge)
dist = DIJK.calc(ch * w + cw)
if dist[dh * w + dw] == INF:
    print(-1)
else:
    print(dist[dh * w + dw])

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())
road_map = []
count_road = 0
for i in range(h):
    road = input()
    road_map.append(road)
    count_road = road.count(".")

queue = [[ch-1,cw-1,0]]
used_map = [[-1]*w for _ in range(h)]

while queue != []:
    dot = queue.pop(0)
    if dot[0] < 0 or dot[1] < 0 or dot[0] >= h or dot[1] >= w:
        continue
    if used_map[dot[0]][dot[1]] > -1 and used_map[dot[0]][dot[1]] <= dot[2]:
        continue
    if road_map[dot[0]][dot[1]] == "#":
        continue
    used_map[dot[0]][dot[1]] = dot[2]

    queue.append([dot[0],dot[1]-1,dot[2]])
    queue.append([dot[0],dot[1]+1,dot[2]])
    queue.append([dot[0]+1,dot[1],dot[2]])
    queue.append([dot[0]+1,dot[1],dot[2]])

    for x in range(-2,3,1):
        for y in range(-2,3,1):
            queue.append([dot[0]+x,dot[1]+y,dot[2]+1])
    
print(used_map[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
h,w=map(int,input().split())
c=[int(i)-1 for i in input().split()]
d=[int(i)-1 for i in input().split()]
s=[input() for i in range(h)]
inf=100000000
dp=[[-1 if s[i][j]=="#" else inf for j in range(w)] for i in range(h)]
dp[c[0]][c[1]]=0
def bfs(i,j):
    global h,w,s,dp
    if i>0:
        if dp[i-1][j]!=-1:
            if dp[i-1][j]>dp[i][j]:
                dp[i-1][j]=dp[i][j]
                bfs(i-1,j)
    if j>0:
        if dp[i][j-1]!=-1:
            if dp[i][j-1]>dp[i][j]:
                dp[i][j-1]=dp[i][j]
                bfs(i,j-1)
    if i<h-1:
        if dp[i+1][j]!=-1:
            if dp[i+1][j]>dp[i][j]:
                dp[i+1][j]=dp[i][j]
                bfs(i+1,j)
    if j<w-1:
        if dp[i][j+1]!=-1:
            if dp[i][j+1]>dp[i][j]:
                dp[i][j+1]=dp[i][j]
                bfs(i,j+1)
    for k in range(-2,3):
        for l in range(-2,3):
            if 0<=i+k<h and 0<=j+l<w:
                if dp[i+k][j+l]!=-1:
                    if dp[i+k][j+l]>dp[i][j]+1:
                        dp[i+k][j+l]=dp[i][j]+1
                        bfs(i+k,j+l)

bfs(c[0],c[1])
print(dp[d[0]][d[1]] if dp[d[0]][d[1]]!=inf else -1)

Submission status: Time Limit Exceeded

Solution code:
R, C = map(int,input().split(" "))

at = list(map(lambda x : int(x)-1, input().split(" ")))
des = list(map(lambda x: int(x)-1, input().split(" ")))

board = []
for _ in range(R):
    board.append(list(input().strip()))


visited = [[-1]*C for _ in range(R)]
visited[at[0]][at[1]] = 0

def tele(i, j ):
    moves = []
    for di in range(-2,3):
        for dj in range(-2,3):
            if i+di >= R or i+di < 0 or j+dj >= C or j+dj < 0 :
                continue
            if visited[i+di][j+dj] != -1  or board[i+di][j+dj] == "#" :
                continue
            moves.append((i+di, j+dj))
    return moves 

dirs = [(1, 0), (-1, 0), (0, -1), (0, 1)]
def walk(i,j ):
    moves = []
    for di,dj in dirs:
        if i+di >= R or i+di < 0 or j+dj >= C or j+dj < 0:
            continue
        if visited[i+di][j+dj] != -1 or board[i+di][j+dj] == "#":
            continue
        moves.append((i+di, j+dj))
    return moves 

from collections import deque
movable = deque() 
movable.append( (at[0],at[1]) )

magic = 0
while movable:
    next_movable = deque()
    temp = set()
    while movable :
        i,j = movable.popleft()
        
        visited[i][j] = magic
        temp.add((i,j))
        for ni, nj in walk(i, j):
            if visited[ni][nj] != -1:
                continue
            visited[ni][nj] = magic
            movable.append((ni,nj))

    magic += 1
    for m in temp:
        for move in tele(m[0],m[1]):
            if visited[move[0]][move[1]] != -1 :
                continue
            visited[move[0]][move[1]] = magic
            next_movable.append(move)

    movable = next_movable
    
    
print(visited[des[0]][des[1]])

Submission status: Time Limit Exceeded

Solution code:

from collections import deque

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
X = [input() for _ in range(H)]

inf = 10 ** 9
dist = [[inf] * W for _ in range(H)]
dist[C_h - 1][C_w - 1] = 0
q = deque()
q.append((C_h - 1, C_w - 1))


def bfs_1():
    while q:
        u, v = q.popleft()
        for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            if (0 <= u + i < H and 0 <= v + j < W
                    and X[u + i][v + j] == "."
                    and dist[u + i][v + j] > dist[u][v]):
                dist[u + i][v + j] = dist[u][v]
                q.append((u + i, v + j))


def bfs_2():
    for u in range(H):
        for v in range(W):
            for i in range(-2, 3):
                for j in range(-2, 3):
                    if (0 <= u + i < H and 0 <= v + j < W
                            and X[u + i][v + j] == "."
                            and dist[u + i][v + j] > dist[u][v] + 1):
                        dist[u + i][v + j] = dist[u][v] + 1
                        q.append((u + i, v + j))


while q:
    bfs_1()
    bfs_2()

if dist[D_h - 1][D_w - 1] < inf:
    print(dist[D_h - 1][D_w - 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())
S = [input() for i in range(H)]

from collections import deque

dist = [[100000000 for i in range(W)] for j in range(H)]
dist[Ch-1][Cw-1] = 0

que = deque()
que.append((Ch-1, Cw-1))

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

while que:
    vh, vw = que.popleft()
    for step in walk:
        vh_next = vh+step[0]
        vw_next = vw+step[1]
        if vh_next in range(H) and vw_next in range(W) and S[vh_next][vw_next] == '.' and dist[vh_next][vw_next] > dist[vh][vw]:
            dist[vh_next][vw_next] = dist[vh][vw]
            que.append((vh_next, vw_next))
    for step in warp:
        vh_next = vh+step[0]
        vw_next = vw+step[1]
        if vh_next in range(H) and vw_next in range(W) and S[vh_next][vw_next] == '.' and dist[vh_next][vw_next] > dist[vh][vw]+1:
            dist[vh_next][vw_next] = dist[vh][vw]+1
            que.append((vh_next, vw_next))

#for d in dist:
#    print(d)

if dist[Dh-1][Dw-1] < 100000000:
    print(dist[Dh-1][Dw-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import*
INF=10**18
h,w=map(int,input().split())
sh,sw=map(int,input().split())
gh,gw=map(int,input().split())
s=[input() for _ in range(h)]
q=deque([(sh-1,sw-1)])
d=[[INF]*w for _ in range(h)]
d[sh-1][sw-1]=0
dx=[1,0,-1,0]
dy=[0,-1,0,1]
wx=[-2,-1,0,1,2]
wy=[-2,-1,0,1,2]
while q:
  x,y=q.popleft()
  for i in range(4):
    nx=x+dx[i]
    ny=y+dy[i]
    if not(0<=nx<h and 0<=ny<w):continue
    if s[nx][ny]=='.' and d[nx][ny]!=d[x][y]:
      d[nx][ny]=d[x][y]
      q.append((nx,ny))
  for i in range(5):
    for j in range(5):
      nx=x+wx[i]
      ny=y+wy[j]
      if not(0<=nx<h and 0<=ny<w):continue
      if s[nx][ny]=='.' and d[nx][ny]>d[x][y]:
        d[nx][ny]=d[x][y]+1
        q.append((nx,ny))
print(d[gh-1][gw-1] if d[gh-1][gw-1]!=INF else -1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from sys import stdin, stdout
 
def input():
    return stdin.readline().strip()

H, W = input().split()
H = int(H)
W = int(W)

Cx, Cy = input().split()
Cx = int(Cx)
Cy = int(Cy)

Dx, Dy = input().split()
Dx = int(Dx)
Dy = int(Dy)

matrix = []

for _ in range(H):
    row = list(input())
    matrix += [row]

from collections import deque

def bfs(x, y, label):
    worklist = deque([(x, y)])
    while len(worklist):
        (x, y) = worklist.popleft()
        matrix[x][y] = label
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            new_x, new_y = x+dx, y+dy
            if 0 <= new_x < H and 0 <= new_y < W and matrix[new_x][new_y] == '.':
                worklist.append((new_x, new_y))
    
# for row in matrix:
#     print(''.join(map(str, row)))

curr_label = 0
for x in range(0, H):
    for y in range(0, W):
        if matrix[x][y] == '.':
            bfs(x, y, curr_label)
            curr_label += 1

# for row in matrix:
#     print(''.join(map(str, row)))

neighbours = []

for _ in range(0, curr_label):
    neighbours += [set()]

for x in range(H):
    for y in range(W):
        u = matrix[x][y]
        if u == '#': continue
        for dx in [-2, -1, 0, 1, 2]:
            for dy in [-2, -1, 0, 1, 2]:
                new_x = x + dx
                new_y = y + dy

                if 0 <= new_x < H and 0 <= new_y < W and matrix[new_x][new_y] != '#':
                    v = matrix[new_x][new_y]
                    if u == v: continue

                    neighbours[u].add(v)
                    neighbours[v].add(u)

Cx -= 1
Cy -= 1

Dx -= 1
Dy -= 1

source = matrix[Cx][Cy]
target = matrix[Dx][Dy]

import sys

if source == '#' or target == '#':
    print(-1)
    sys.exit(0)

visited = set([source])
frontier = set([source])

if target in frontier:
    print(0)
    sys.exit(0)

# print(neighbours, source, target)

count = 1
while len(frontier):
    next_frontier = set()
    for u in frontier:
        for v in neighbours[u]:
            if v not in visited:
                visited.add(v)
                next_frontier.add(v)
    if target in next_frontier:
        print(count)
        count += 1
        sys.exit(0)

    count += 1
    frontier = next_frontier

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    CH, CW = [int(x) - 1 for x in input().split()]
    DH, DW = [int(x) - 1 for x in input().split()]
    S = [input().strip() for _ in range(H)]

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

    visited = [[float("inf")] * W for _ in range(H)]

    q = collections.deque()
    visited[CH][CW] = 0
    q.append((CH, CW))
    while q:
        cx, cy = q.pop()
        cc = visited[cx][cy]

        # 隣接
        for nx, ny in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            nnx = cx + nx
            nny = cy + ny
            if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                if S[nnx][nny] == "." and visited[nnx][nny] > cc:
                    q.append((nnx, nny))
                    visited[nnx][nny] = cc

        # ワープ
        for nx, ny in warp:
            nnx = cx + nx
            nny = cy + ny
            if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                if S[nnx][nny] == "." and visited[nnx][nny] > cc:
                    q.append((nnx, nny))
                    visited[nnx][nny] = cc + 1

    if visited[DH][DW] == float("inf"):
        print(-1)
    else:
        print(visited[DH][DW])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

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

grid = []
for _ in range(H):
	grid.append(list(c == "." for c in input().strip()))

m = H * W + 1
smallests = [[m] * W for _ in range(H)]

queue = [(0, Cw, Ch)]
smallests[Ch][Cw] = 0

def calc():
	while queue:
		d, x, y = heappop(queue)
		if d == smallests[y][x]:
			for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
				tx = x + dx
				ty = y + dy
				if tx >= 0 and tx < W and ty >= 0 and ty < H:
					if grid[ty][tx] and d < smallests[ty][tx]:
						smallests[ty][tx] = d
						heappush(queue, (d, tx, ty))
			d += 1
			for tx in range(max(0, x - 2), min(W, x + 3)):
				for ty in range(max(0, y - 2), min(H, y + 3)):
					if grid[ty][tx] and d < smallests[ty][tx]:
						smallests[ty][tx] = d
						heappush(queue, (d, tx, ty))
	return smallests[Dh][Dw]

result = calc()
if result == m:
	print(-1)
else:
	print(result)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import heapq
INF = 10**9

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.dist = [INF] * len(adj)
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest, cost in self.adj[src]:
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
        return self.dist

h, w = map(int, input().split())
ch, cw = map(int, input().split())
ch -= 1; cw -= 1
dh, dw = map(int, input().split())
dh -= 1; dw -= 1
field = []
for _ in range(h):
    field.append(input().rstrip())

edge = [[] for _ in range(h * w)]
for i in range(h):
    for j in range(w):
        frm = i * w + j
        for dx in range(-2, 3):
            nx = i + dx
            if nx < 0 or nx > h - 1:
                continue
            for dy in range(-2, 3):
                if dx == 0 and dy == 0:
                    continue
                ny = j + dy
                if ny < 0 or ny > w - 1:
                    continue
                if field[nx][ny] == "#":
                    continue
                dist = abs(dx) + abs(dy)
                if dist == 1:
                    edge[frm].append((nx*w + ny, 0))
                else:
                    edge[frm].append((nx*w + ny, 1))
        
DIJK = Dijkstra(edge)
dist = DIJK.calc(ch * w + cw)
if dist[dh * w + dw] == INF:
    print(-1)
else:
    print(dist[dh * w + dw])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def grid_wall(grid, h, w, wall='#'):
    G = [[wall]*(w+2) for _ in range(h+2)]
    for hi in range(h):
        G[hi+1][1:w+1] = grid[hi]
    return G

from copy import deepcopy

def solve():
    H, W = MI()
    ch, cw = MI()
    dh, dw = MI()
    G = LLS(H)
    GW = grid_wall(G, H, W)
    GW[dh][dw] = 'G'
    # print(GW)

    # q = deque([(0, ch, cw)])

    # heappush(hq, (1, 1, 1))
    # heappush(hq, (0, 1, 10))
    # print(hq, type(hq))
    # print(heappop(hq))
    # print(heappop(hq))
    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    used = deepcopy(GW)
    used[ch][cw] = '#'

    hq = [(0, ch, cw, deepcopy(used))]
    heapify(hq)

    while hq:
    # for _ in range(10):
        mp, h, w, u = heappop(hq)
        if GW[h][w] == 'G':
            print(mp)
            # print(u)
            return

        for dh, dw in move:
            nh, nw = h+dh, w+dw
            if u[nh][nw] == '#':
                continue
            u[nh][nw] = '#'
            heappush(hq, (mp, nh, nw, deepcopy(u)))

        for dh in range(-2, 3):
            for dw in range(-2, 3):
                nh, nw = dh+h, dw+w
                if not 0 <= nh <= H or not 0 <= nw <= W:
                    continue
                if u[nh][nw] == '#' or u[nh][nw] == 'W':
                    continue
                u[nh][nw] = 'W'
                heappush(hq, (mp+1, nh, nw, deepcopy(u)))


    print(-1)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict
from heapq import *

INF = 10**9

def dijkstra(s, edges):
    dist = [INF] * len(edges)
    dist[s], h = 0, []
    heappush(h, (0, s))
    while (len(h)):
        dv, v = heappop(h)
        if dv > dist[v]:
            continue
        for u, cost in edges[v]:
            tmp = dv+cost
            if tmp < dist[u]:
                dist[u] = tmp
                heappush(h, (tmp, u))
    return dist

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 = [input() for i in range(H)]
es = [[] for i in range(H*W)]
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 0 <= k < H and 0 <= l < W and S[k][l] == '.':
                    if abs(i-k) + abs(j-l) == 1:
                        es[i*W+j].append((k*W+l, 0))
                    else:
                        es[i*W+j].append((k*W+l, 1))
d = dijkstra(Ch*W+Cw, es)[Dh*W+Dw]
ans = -1 if d == INF else d
print(ans)

Submission status: Time Limit Exceeded

Solution code:
R, C = map(int,input().split(" "))

at = list(map(lambda x : int(x)-1, input().split(" ")))
des = list(map(lambda x: int(x)-1, input().split(" ")))

board = []
for _ in range(R):
    board.append(list(input().strip()))


visited = [[-1]*C for _ in range(R)]

def tele(i, j ):
    moves = []
    for di in range(-2,3):
        for dj in range(-2,3):
            if i+di >= R or i+di < 0 or j+dj >= C or j+dj < 0 :
                continue
            if visited[i+di][j+dj] != -1  or board[i+di][j+dj] == "#" :
                continue
            moves.append((i+di, j+dj))
    return moves 

dirs = [(1, 0), (-1, 0), (0, -1), (0, 1)]
def walk(i,j ):
    moves = []
    for di,dj in dirs:
        if i+di >= R or i+di < 0 or j+dj >= C or j+dj < 0:
            continue
        if visited[i+di][j+dj] != -1 or board[i+di][j+dj] == "#":
            continue
        moves.append((i+di, j+dj))
    return moves 

from collections import deque
movable = deque() 
movable.append( (at[0],at[1]) )

magic = 0
while movable:
    next_movable = deque()
    temp = set()
    while movable :
        i,j = movable.popleft()
        if visited[i][j] != -1 :
            continue
        visited[i][j] = magic
        temp.add((i,j))
        for ni, nj in walk(i, j):
            if visited[ni][nj] != -1:
                continue
            movable.append((ni,nj))

    
    for m in temp:
        for move in tele(m[0],m[1]):
            next_movable.append(move)

    movable = next_movable
    magic += 1
    
print(visited[des[0]][des[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())
s=[list(input()) for _ in range(h)]

Ch,Cw=Ch-1,Cw-1
Dh,Dw=Dh-1,Dw-1
todo=[[0,Ch,Cw]]
d=[[-1]*w for _ in range(h)]
d[Ch][Cw]=0
toho=[[0,1],[0,-1],[1,0],[-1,0]]
wiz=[[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]
while todo:
  cnt,nh,nw=todo.pop()
  if d[nh][nw]<cnt:continue
  for dh,dw in toho:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='#':
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt:
        d[nh+dh][nw+dw]=cnt
        todo.append([cnt,nh+dh,nw+dw])
  for dh,dw in wiz:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='#':
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt+1:
        d[nh+dh][nw+dw]=cnt+1
        todo.append([cnt+1,nh+dh,nw+dw])
print(d[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
ch,cw = map(int, input().split())
ch,cw = ch-1, cw-1
dh,dw = map(int, input().split())
dh,dw = dh-1,dw-1
s = [list(map(lambda x: x==".", input())) for i in range(h)]

inf = 2**32-1
count = [[inf]*w for i in range(h)]

from collections import deque
que = deque()
que.append((ch,cw,0))

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

while que:
    x,y,c = que.pop()
    if count[x][y] <= c:
        continue
    count[x][y] = c
    kabe = False
    for dx,dy in dxdy:
        nx, ny = x+dx, y+dy
        if not (0<=nx<h and 0<=ny<w):
            continue
        if s[nx][ny]:
            que.appendleft((nx,ny,c))
        else:
            kabe = True
    if not kabe:
        continue
    nc = c+1
    for kx in range(-2,3):
        for ky in range(-2,3):
            nx = x+kx
            ny = y+ky
            if 0<=nx<h and 0<=ny<w and s[nx][ny] and count[nx][ny] > nc:
                que.append((nx,ny,nc))

ans = count[dh][dw]
if ans == inf:
    ans = -1
print(ans)