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:
import sys
from heapq import heappop, heappush

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1

    M = [[-1 for w in range(W)] for h in range(H)]
    Edge = [[[] for w in range(W)] for h in range(H)]
    for h in range(H):
        s = input().strip("\n")
        for w in range(W):
            if s[w] == "#":
                M[h][w] = -2
    for h in range(H):
        for w in range(W):
            if M[h][w] == -1:
                for dh in range(-2, 3):
                    for dw in range(-2, 3):
                        if 0<=h+dh<H and 0<=w+dw<W and M[h+dh][w+dw] == -1 and abs(dh)+abs(dw)>0:
                            if abs(dh)+abs(dw)==1:
                                Edge[h][w].append((0, h+dh, w+dw))
                            else:
                                Edge[h][w].append((1, h+dh, w+dw))


    q = []
    heappush(q, (0, ch, cw))
    while q:
        dist, h, w = heappop(q)
        if M[h][w] == -1:
            M[h][w] = dist
            for dd, nh, nw in Edge[h][w]:
                if M[nh][nw] == -1: heappush(q, (dist+dd, nh, nw))
    print(M[fh][fw])
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

H,W = map(int, input().split())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
maze = [[int(ch == '#') for ch in input().rstrip()] for _ in range(H)]

from sys import exit
from collections import deque
from itertools import product
que = deque([c])
nque = set()
cnt = 0
while nque or que:
    while que:
        h,w = que.popleft()
#         print(f'{h=},{w=}')
        if (h,w) == d:
            print(cnt)
            exit()

        for dh, dw in [[0,1], [0,-1], [1,0], [-1,0]]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and not maze[nh][nw]:
#                 print(f'no_warp: {nh=},{nw=}')
                que.append((nh,nw))

        for dh,dw in [
            [-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], 
        ]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W and not maze[nh][nw]:
#                 print(f'warp: {nh=},{nw=}')
                nque.add((nh,nw))
        
        maze[h][w] = 1
        nque.discard((h,w))
    que = deque(nque)
    nque = set()
    cnt += 1
#     print(f'{que=}, {cnt=}')
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

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

cnt = 0

def bfs():
    global cnt
    reached = [[False]*W for _ in range(H)]

    d = deque()
    d.append((Ch, Cw))
    #reached[Ch][Cw] = True
    while d:
        while d:
            h, w = d.popleft()
            dh = [-1, 0, 1, 0]
            dw = [0, -1, 0, 1]
            reached[h][w] = True
            for i in range(4):
                next_h = h + dh[i]
                next_w = w + dw[i]
                if 0 <= next_h <= H-1 and 0 <= next_w <= W-1 and maze[next_h][next_w] != "#" and not reached[next_h][next_w]:
                    d.append((next_h, next_w))
        if reached[Dh][Dw]:
            print(cnt)
            sys.exit(0)
        for i in range(H):
            for j in range(W):
                if reached[i][j] or maze[i][j] == "#":
                    continue
                for n in range(i-2, i+3):
                    for m in range(j-2, j+3):
                        if 0 <= n <= H-1 and 0 <= m <= W-1 and reached[n][m]:
                            d.append((i, j))
        if d:
            cnt += 1

bfs()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
INF = float('inf')

H, W = map(int, input().split())
ch, cw = [int(i) - 1 for i in input().split()]
dh, dw = [int(i) - 1 for i in input().split()]
S = [input() for i in range(H)]
# print(S)

B = [[INF for w in range(W)] for h in range(H)]
B[ch][cw] = 0
# print(B)

def get_B(h, w):
    if not ((0 <= h < H) and (0 <= w < W)):
        return INF
    else:
        return B[h][w]

flag = True
while flag:
    flag = False

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

        # 横
        min_v = min(get_B(h - 1, w),
                    get_B(h + 1, w),
                    get_B(h, w - 1),
                    get_B(h, w + 1))

        # ワープ
        for i, j in product(range(5), repeat=2):
            if not ((0 <= h - i + 2 < H) and (0 <= w - j + 2 < W)):
                continue
            min_v = min(min_v,
                        B[h - i + 2][w - j + 2] + 1)

        if B[h][w] > min_v:
            B[h][w] = min_v
            flag = True
            # for b in B:
            #     print(b)
            # print()

print(B[dh][dw] if B[dh][dw] != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
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 = []
for i in range(H):
  S.append(input())


from collections import deque

def bfs(sh,sw):
  queue = deque([(sh,sw)])
  d = [[None]*W for _ in range(H)]
  now = set()
  d[sh][sw]=0
  
  while queue:
    h,w = queue.popleft()
    now.add((h,w))
    for nh,nw in [(h-1,w),(h+1,w),(h,w-1),(h,w+1)]:
      if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and d[nh][nw] is None) == False: continue
      queue.append((nh,nw))
      now.add((nh,nw))
      d[nh][nw]=d[h][w]

    if queue: continue
    for h,w in now:
      for i in range(-2,3):
        for j in range(-2,3):
          if i==0 and abs(j)<=1: continue
          if j == 0 and abs(i)<=1: continue
          nh,nw = h-i,w-j
          if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and d[nh][nw] is None) == False: continue
          d[nh][nw] = d[h][w]+1
          queue.append((nh,nw))
    now = set()
    #print(queue)
  return d

d = bfs(Ch,Cw)
if d[Dh][Dw] == None: 
  print(-1)
  exit()
print(d[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
import sys
sys.setrecursionlimit(10**8)

def bfs(a,b):
    if a == dh+1 and b == dw+1:
        print(s[a,b])
        exit(0) 

    if s[a+1,b]=='.': 
        q.append([a+1,b])
        s[a+1,b]=int(s[a,b])
    else:
        wq.append([a,b])
    if s[a,b+1]=='.':
        q.append([a,b+1])
        s[a,b+1]=int(s[a,b])
    else:
        wq.append([a,b])
    if s[a-1,b]=='.':
        q.append([a-1,b])
        s[a-1,b]=int(s[a,b])
    else:
        wq.append([a,b])
    if s[a,b-1]=='.':
        q.append([a,b-1])
        s[a,b-1]=int(s[a,b])
    else:
        wq.append([a,b])
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.pop(0)
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return

def worp(a,b):
    for ii in range(-2,3):
        for jj in range(-2,3):
            if s[a+ii,b+jj]=='.':
                q.append([a+ii,b+jj])
                s[a+ii,b+jj]=int(s[a,b])+1
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.pop(0)
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return   

H,W=map(int, input().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
s=np.array([list(input()) for _ in range(H)],dtype=object)
q = deque([])
wq= []

hbmp=['#']*(W)
s=np.vstack((hbmp,hbmp,s,hbmp,hbmp))
vbmp=[['#']]*(H+4)
s=np.hstack((vbmp,vbmp,s,vbmp,vbmp))

ch,cw=ch+1,cw+1
s[ch,cw]=int(0)

bfs(ch,cw)

Submission status: Time Limit Exceeded

Solution code:

from collections import deque


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

warp_list = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
             (-1, -2), (-1, -1), (-1, 1), (-1, 2),
             (0, -2), (0, 2),
             (1, -2), (1, -1), (1, 1), (1, 2),
             (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

maze = []
warp_count = []
for _ in range(H):
    line = list([x for x in input()])
    maze.append(line)
    warp_count.append([10**9] * W)

queue = deque()
queue.appendleft((Ch, Cw, 0))

answer = 10**9
while queue:
    def maze_check(h, w, use_magic):
        if h < 0 or H <= h:
            return False
        if w < 0 or W <= w:
            return False
        if maze[h][w] == '#':
            return False
        if warp_count[h][w] <= use_magic:
            return False

        return True

    now_h, now_w, use_magic = queue.pop()
    warp_count[now_h][now_w] = use_magic

    if now_h == Dh and now_w == Dw:
        if answer > use_magic:
            answer = use_magic

        continue

    # 上下左右に移動
    do_warp = True
    if maze_check(now_h+1, now_w, use_magic):
        queue.appendleft((now_h + 1, now_w, use_magic))
        do_warp = False
    if maze_check(now_h-1, now_w, use_magic):
        queue.appendleft((now_h - 1, now_w, use_magic))
        do_warp = False
    if maze_check(now_h, now_w+1, use_magic):
        queue.appendleft((now_h, now_w + 1, use_magic))
        do_warp = False
    if maze_check(now_h, now_w-1, use_magic):
        queue.appendleft((now_h, now_w - 1, use_magic))
        do_warp = False

    if do_warp:
        for y, x in warp_list:
            warp_h = now_h + y
            warp_w = now_w + x

            if maze_check(warp_h, warp_w, use_magic+1):
                queue.appendleft((warp_h, warp_w, use_magic+1))


if answer == 10**9:
    print(-1)
else:
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
class G:
    def __init__(self, c):
        self.c = c
        self.reached = False
        self.range = 0

    
H, W = [int(i) for i in input().split()]
Ch, Cw = [int(i)-1 for i in input().split()]
Dh, Dw = [int(i)-1 for i in input().split()]
S = [['.' for j in range(W)] for i in range(H) ]
for i in range(H):
    tmp = list(input())
    for j in range(W):
        S[i][j] = G(tmp[j])

def neighbors(y, x):
    s = []
    if x != 0:
        if S[y][x-1].reached == False:
            s.append((y, x-1))
    if x != W-1:
        if S[y][x+1].reached == False:
            s.append((y, x+1))
    if y != 0:
        if S[y-1][x].reached == False:
            s.append((y-1, x))
    if y != H-1:
        if S[y+1][x].reached == False:
            s.append((y+1, x))
    return s

def jump(x, y, d):
    for i in range(max(x-2, 0), min(x+3, W)):
        for j in range(max(y-2, 0), min(y+3, H)):
            if S[j][i].reached == False and S[j][i].c == '.':
                d.append((j, i))



def DFS(S, d):
    while True:
        if len(d) == 0:
            break
        q = d.popleft()
        S[q[0]][q[1]].reached = True
        for each in neighbors(q[0], q[1]):
            S[each[0]][each[1]].reached = True
            if S[each[0]][each[1]].c == '.':
                d.append(each)


counter = 0
d = deque([])
S[Ch][Cw].reached = True
d.append((Ch, Cw))
flag = False
while True:
    DFS(S, d)
    if S[Dh][Dw].reached:
        break
    counter += 1
    for i in range(H):
        for j in range(W):
            if S[i][j].reached and S[i][j].c == '.':
                jump(j, i, d)

    if len(d) == 0:
        flag = True
        break

if flag:
    print(-1)
else:
    print(counter)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
h,w=map(int,input().split())
 
def main():
    start = tuple(x-1 for x in map(int,input().split()))
    goal = tuple(x-1 for x in map(int,input().split()))
    s = [input() for _ in range(h)]
    
    sumi = set()
    cur = 0
    ans = [[-1]*w for _ in range(h)]
    srch = deque([start])
    warp_can = set()
    while len(srch) > 0:
        while len(srch) > 0:
            c=srch.popleft()
            ans[c[0]][c[1]] = cur
            if c in sumi:
                continue
            sumi.add(c)
            warp_can |= set(getwarp(c,s,sumi))
            for x,y in getnext(c):
                if s[x][y] == "#" or (x,y) in sumi:
                    continue
                srch.append((x,y))
        srch += list(warp_can - sumi)
        cur += 1
    print(ans[goal[0]][goal[1]])
 
def getnext(c):
    if 0 < c[0]:
        yield (c[0]-1, c[1])
    if c[0]+1 < h:
        yield (c[0]+1, c[1])
    if 0 < c[1]:
        yield (c[0], c[1]-1)
    if c[1]+1 < w:
        yield (c[0], c[1]+1)
 
def getwarp(c,s,sumi):
    for x in range(-2,3):
        for y in range(-2,3):
            cx,cy=c[0]+x,c[1]+y
            if 0 <= cx < h and 0 <= cy < w:
                if s[cx][cy] == "#" or (cx,cy) in sumi:
                    continue
                yield (cx,cy)
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    mod=10**9+7
    H,W=MI()
    ch,cw=MI()
    dh,dw=MI()
    ch+=1
    cw+=1
    dh+=1
    dw+=1
    
    S=[]
    S.append(["#"]*(W+4))
    S.append(["#"]*(W+4))
    for i in range(H):
        s=["#"]*2 + list(input()) + ["#"]*2
        S.append(s)
    S.append(["#"]*(W+4))
    S.append(["#"]*(W+4))
    

    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    dx2=[-2,-2,-2,-2,-2,  -1,-1,-1,-1,   0,0,   1, 1,1,1,   2, 2,2,2,2]
    dy2=[-2,-1, 0, 1, 2,  -2,-1, 1, 2,  -2,2,  -2,-1,1,2,  -2,-1,0,1,2]
    
    import heapq
    
    inf=10**7
    hq=[]
    heapq.heapify(hq)
    used=[[inf]*(W+4) for _ in range(H+4)]
    
    heapq.heappush(hq,(0,ch,cw))
    used[ch][cw]=0
    
    ans=-1
    while len(hq)!=0:
        cost,i,j=heapq.heappop(hq)
        for k in range(4):
            ii=i+dx[k]
            jj=j+dy[k]
            if S[ii][jj]==".":
                if used[ii][jj] > cost:
                    used[ii][jj]=cost
                    heapq.heappush(hq,(cost,ii,jj))
                
        for k in range(20):
            ii=i+dx2[k]
            jj=j+dy2[k]
            if S[ii][jj]==".":
                if used[ii][jj] > cost:
                    used[ii][jj]=cost+1
                    heapq.heappush(hq,(cost+1,ii,jj))
        
        if used[dh][dw]!=inf:
            ans=used[dh][dw]
            
            
    print(ans)
    
    # for i in range(H+4):
    #     print(used[i])
            

                    
                

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1

moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
ts = [(x, y) for x in range(-2, 3)
      for y in range(-2, 3) if not (x, y) in moves and (x, y) != (0, 0)]

grid = [list(map(str, input().rstrip())) for _ in range(h)]

q = deque([(sx, sy)])
qq = deque([(sx, sy)])

grid[sx][sy] = 0

while len(q) > 0 or len(qq) > 0:
    while q:
        (cx, cy) = q.popleft()
        for m in moves:
            nx, ny = cx + m[0], cy + m[1]
            if 0 <= nx < h and 0 <= ny < w:
                if grid[nx][ny] == ".":
                    grid[nx][ny] = grid[cx][cy]
                    q.append((nx, ny))
                elif grid[nx][ny] == "#":
                    qq.append((cx, cy))
    while qq:
        (cx, cy) = qq.popleft()
        for t in ts:
            nx, ny = cx + t[0], cy + t[1]
            if 0 <= nx < h and 0 <= ny < w:
                if grid[nx][ny] == ".":
                    grid[nx][ny] = grid[cx][cy] + 1
                    q.append((nx, ny))

print(grid[gx][gy] if grid[gx][gy] != "." else -1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [W for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        # print(M[h])
    ans = 0
    q = deque([(Dh, Dw)])
    while True:
        h, w = q.pop()
        # print('({}, {}) = {}'.format(h, w, ans))
        if h == Ch and w == Cw:
            print(ans)
            return True
        if not type(M[h][w]) == int:
            M[h][w] = ans
            for dh, dw in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if 0 <= h+dh < H and 0 <= w+dw < W and M[h+dh][w+dw] == '.':
                    q.append((h+dh, w+dw))
        if len(q) == 0:
            # for h in range(H):
            #     print(M[h])
            f = False
            for h in range(H):
                for w in range(W):
                    if M[h][w] != '.':
                        continue
                    for i, j in [(-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (-2, 1), (-1, 1), (1, 1), (2, 1), (-2, 0), (2, 0), (-2, -1), (-1, -1), (1, -1), (2, -1), (-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2)]:
                        if 0 <= h+i < H and 0 <= w+j < W and M[h+i][w+j] == ans:
                            f = True
                            # print('warp to ({}, {})'.format(h, w))
                            q.append((h, w))
            if f:
                ans += 1
            else:
                print(-1)
                return True

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
# import math
# import copy
from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    H,W = map(int,input().split())
    C = list(map(int,input().split()))
    D = list(map(int,input().split()))
    S = [input().rstrip() for i in range(H)]

    deq = deque()
    deq.append([C[0]-1,C[1]-1])
    cost = [[-1 for j in range(W)] for i in range(H)]
    cost[C[0]-1][C[1]-1] = 0
    checked = []

    while deq:
        nowp = deq.popleft()
        nowc = cost[nowp[0]][nowp[1]]
        if nowp in checked:
            continue
        checked.append(nowp)
        if S[nowp[0]][nowp[1]] == '#':
            continue
        for i in range(-2,3):
            for j in range(-2,3):
                if (i == 0) & (j == 0):
                    continue
                elif [nowp[0]+i,nowp[1]+j] in checked:
                    continue
                elif (abs(i) + abs(j) == 1):
                    if (0 <= nowp[0] + i) & (nowp[0] + i < H):
                        if (0 <= nowp[1] + j) & (nowp[1] + j < W):
                            if S[nowp[0]+i][nowp[1]+j] == '.':
                                if cost[nowp[0]+i][nowp[1]+j] == -1:
                                    cost[nowp[0]+i][nowp[1]+j] = nowc
                                else:
                                    cost[nowp[0]+i][nowp[1]+j] = min(nowc,cost[nowp[0]+i][nowp[1]+j])
                                deq.append([nowp[0]+i,nowp[1]+j])
                else:
                    if cost[nowp[0]][nowp[1]] != -1:
                        if (0 <= nowp[0] + i) & (nowp[0] + i < H):
                            if (0 <= nowp[1] + j) & (nowp[1] + j < W):
                                if S[nowp[0]+i][nowp[1]+j] == '.':
                                    if cost[nowp[0]+i][nowp[1]+j] == -1:
                                        cost[nowp[0]+i][nowp[1]+j] = nowc + 1
                                    else:
                                        cost[nowp[0]+i][nowp[1]+j] = min(nowc+1,cost[nowp[0]+i][nowp[1]+j])
                                    deq.append([nowp[0]+i,nowp[1]+j])

    res = cost[D[0]-1][D[1]-1]
    print(res)



main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

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


h = []
heapq.heappush(h, (0, Ch, Cw))

while len(h) != 0:
    d, nh, nw = heapq.heappop(h)
    if nh == Dh and nw == Dw:
        print(d)
        exit()

    for dh in [-2, -1, 0, 1, 2]:
        for dw in [-2, -1, 0, 1, 2]:
            if dh == 0 and dw == 0:
                continue
            newd = d + 1
            if abs(dh) + abs(dw) == 1:
                newd = d
            newh = nh + dh
            neww = nw + dw
            if 0 <= newh < H and 0 <= neww < W:
                if S[newh][neww] == ".":
                    S[newh][neww] = newd
                    heapq.heappush(h, (newd, newh, neww))
                elif S[newh][neww] == "#":
                    continue
                else:
                    if S[newh][neww] > newd:
                        S[newh][neww] = newd
                        heapq.heappush(h, (newd, newh, neww))
print(-1)

Submission status: Time Limit Exceeded

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

H, W = map(int, input().split())
C = [int(i) for i in input().split()]
D = [int(i) for i in input().split()]
maze = [["#"]+[i for i in input()]+["#"] for j in range(H)]
maze = [["#"]*(W+2)] + maze + [["#"]*(W+2)]
dp = [[-1 for i in range(W+2)] for j in range(H+2)]

dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]
dp[C[0]][C[1]] = 0
pos = deque([[C[0], C[1], 0]])

while len(pos) > 0:

    h, w, count = pos.popleft()

    for dh, dw in dir:
        if maze[h+dh][w+dw] == "#":
            continue
        elif dp[h+dh][w+dw] == -1 or count < dp[h+dh][w+dw]:
            dp[h+dh][w+dw] = count
            pos.append([h+dh, w+dw, count])

    for next_h in range(max(0, h-2), min(H, h+2)+1):
        for next_w in range(max(0, w-2), min(W, w+2)+1):
            if next_h == h and next_w == w:
                continue
            if maze[next_h][next_w] == "#":
                continue
            elif dp[next_h][next_w] == -1 or count + 1 < dp[next_h][next_w]:
                dp[next_h][next_w] = count + 1
                pos.append([next_h, next_w, count+1])

print(dp[D[0]][D[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, -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]]

    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]

        # 隣接
        kabe_cnt = 0
        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] == ".":
                    if visited[nnx][nny] > cc:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc
                else:
                    kabe_cnt += 1

        # ワープ
        if kabe_cnt > 0:
            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 + 1:
                        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:
import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
visited = [[10**9]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0

while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1

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())
grid = [input() for i in range(h)]
done = [[0]*w for _ in range(h)]
dxdy = [[0,1],[1,0],[-1,0],[0,-1]]
def search5(i,j):#周辺にゴールがあるか
    if dw < i+2 and dw > i-2 and dh < i+2 and dh > i-2:
        return True
    else:
        return False

def ok(i,j):
    if i>-1 and j>-1 and i<h and j<w and grid[i][j]==".":
        return True
    else:
        return False
lis = []
ind = 0
def dfs(i,j):
    if(i==dh-1 and j==dw-1):
        lis.append([i,j])
        done[i][j]=1
        return True
    elif(not done[i][j]):
        lis.append([i,j])
        done[i][j]=1
        for dx,dy in dxdy:
            if(ok(i+dy,j+dx)):
                dfs(i+dy,j+dx)

    return False
vertex_set = []
res = 0
for i in range(h):
    for j in range(w):
        if(grid[i][j]=="." and done[i][j]==0):
            dfs(i,j)
            vertex_set.append(lis)
            lis = []
edge_list = [[] for _ in range(len(vertex_set))]
start = -1
end = -1
for i in range(len(vertex_set)):
    for from_ in ((vertex_set[i])):
        for j in range(len(vertex_set)):
            if i!=j:
                for to in (vertex_set[j]):
                    if abs(to[0]-from_[0])<3 and abs(to[1]-from_[1])<3:
                        edge_list[i].append([j,1])
                        edge_list[j].append([i,1])
        if from_[0]==ch-1 and from_[1]==cw-1:
            start = i
        if from_[0]==dh-1 and from_[1]==dw-1:
            end = i
from heapq import heappush, heappop
def dijkstra(s,egde):
    n = len(edge_list)
    INF = float("INF")
    dist = [INF]*n
    hq = [(0,s)]
    dist[s] = 0
    seen = [False]*n

    while hq:
        v = heappop(hq)[1]
        seen[v] = True
        for to,cost in edge_list[v]:
            if not seen[to] and dist[v]+cost < dist[to]:
                dist[to] = dist[v]+cost
                heappush(hq, (dist[to],to))
    return dist
dist = dijkstra(start,edge_list)
if dist[end]==float("INF"):
    print(-1)
else:
    print(dist[end])

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())
s = [list(input()) for _ in range(h)]
visited = [[0] * w for _ in range(h)]
ans_flag = False

queue1 = deque()
queue2 = deque()
visited[c_h - 1][c_w - 1] = 1
queue1.append([c_h - 1, c_w - 1])
ans = -1
def dfs(queue1, queue2):
    global ans_flag
    while queue1:
        y, x = queue1.pop()
        if y == d_h - 1 and x == d_w - 1:
            ans_flag = True
            return 
        for i, j in ([0, 1], [1, 0], [0, -1], [-1, 0]):
            nx = x + i
            ny = y + j
            if 0 <= nx < w and 0 <= ny < h and visited[ny][nx] == 0:
                if s[ny][nx] != "#":
                    visited[ny][nx] = 1
                    queue1.append([ny, nx])
                else:
                    queue2.append([y, x])


dfs(queue1, queue2)
while queue2:
    m = len(queue2)
    flag = False
    for a in range(m):
        y, x = queue2.pop()
        for k in range(5):
            for i, j in ([-2, -2], [-1, -2], [0, -2], [1, -2], [2, -2]):
                ny = y + j + k
                nx = x + i
                if 0 <= nx < w and 0 <= ny < h and visited[ny][nx] == 0 and s[ny][nx] != "#":
                    #print(ny, nx, y, x)
                    flag = True
                    queue1.append([ny, nx])
                    dfs(queue1, queue2)

    if flag:
        ans += 1
    else:
        break

print(ans + 1 if ans != -1 or ans_flag else ans)