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:
def solve(now_x, now_y):
    for next_y in range(-2, 3):
        for next_x in range(-2, 3):
            x, y = now_x + next_x, now_y + next_y
            if 0 <= x < w and 0 <= y < h:
                if c[y][x] != "#" and c[y][x] != "=" and c[y][x] != "!":
                    c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                    d2.append([x, y])


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())
c = [input() for _ in range(h)]
cw -= 1
ch -= 1
dw -= 1
dh -= 1
c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
d1 = deque([[cw, ch]])
d2 = deque([])

cnt = 0
while True:
    for _ in range(100000):
        for _ in range(len(d1)):
            now_x, now_y = d1.popleft()
            for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                x, y = now_x + next_x, now_y + next_y
                if 0 <= x < w and 0 <= y < h:
                    if x == dw and y == dh:
                        print(cnt)
                        exit()
                    if c[y][x] == "#":
                        solve(now_x, now_y)
                    if c[y][x] != "#" and c[y][x] != "=":
                        c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                        d1.append([x, y])

    else:
        cnt += 1
        if [dw, dh] in d2:
            print(cnt)
            exit()
        if not d2:
            print(-1)
            exit()
        d1 = d2.copy()
        d2.clear()

Submission status: Time Limit Exceeded

Solution code:
h, w = map( int, input().split() )
c_h, c_w = map( int, input().split() )
c = ( c_h - 1 ) * w + ( c_w - 1 )
d_h, d_w = map( int, input().split() )
d = ( d_h - 1 ) * w + ( d_w - 1 )
s = []
for _ in range( h ):
    s_h = str( input() )
    # s.append( s_h )
    for s_h_w in s_h:
        s.append( s_h_w )

move_a = []
for i in range( h * w ):
    move_a_i = []
    if i % w > 0:
        if s[ i - 1 ] != "#":
            move_a_i.append( i - 1 )
    if i // w > 0:
        if s[ i - w ] != "#":
            move_a_i.append( i - w )
    if i % w < w - 1:
        if s[ i + 1 ] != "#":
            move_a_i.append( i + 1 )
    if i // w < h - 1:
        if s[ i + w ] != "#":
            move_a_i.append( i + w )
    move_a.append( move_a_i )

move_b = []
for i in range( h * w ):
    move_b_i = []
    if i % w > 1:
        if s[ i - 2 ] != "#":
            move_b_i.append( i - 2 )
    if i % w > 0 and i // w > 0:
        if s[ i - 1 - w ] != "#":
            move_b_i.append( i - 1 - w )
    if i % w > 1 and i // w > 1:
        if s[ i - 2 - 2 * w ] != "#":
            move_b_i.append( i - 2 - 2 * w )
    if i // w > 1:
        if s[ i - 2 * w ] != "#":
            move_b_i.append( i - 2 * w )
    if i // w > 0 and i % w < w - 1:
        if s[ i - w + 1 ] != "#":
            move_b_i.append( i - w + 1 )
    if i // w > 1 and i % w < w - 2:
        if s[ i - 2 * w + 2 ] != "#":
            move_b_i.append( i - 2 * w + 2 )
    if i % w < w - 2:
        if s[ i + 2  ] != "#":
            move_b_i.append( i + 2 )
    if i % w < w - 1 and i // w < h - 1:
        if s[ i + 1 + w ] != "#":
            move_b_i.append( i + 1 + w )
    if i % w < w - 2 and i // w < h - 2:
        if s[ i + 2 + 2 * w  ] != "#":
            move_b_i.append( i + 2 + 2 * w )
    if i // w < h - 2:
        if s[ i + 2 * w  ] != "#":
            move_b_i.append( i + 2 * w )
    if i % w > 0 and i // w < h - 1:
        if s[ i + w - 1 ] != "#":
            move_b_i.append( i + w - 1 )
    if i % w > 1 and i // w < h - 2:
        if s[ i + 2 * w - 2  ] != "#":
            move_b_i.append( i + 2 * w - 2 )

    if i % w > 2 and i // w > 0:
        if s[ i - w - 2  ] != "#":
            move_b_i.append( i - w - 2 )
    if i % w > 1 and i // w > 1:
        if s[ i - 2 * w - 1  ] != "#":
            move_b_i.append( i - 2 * w - 1 )
    if i % w < w - 1 and i // w > 2:
        if s[ i - 2 * w + 1  ] != "#":
            move_b_i.append( i - 2 * w + 1 )
    if i % w < w - 2 and i // w > 1:
        if s[ i - w + 2 ] != "#":
            move_b_i.append( i - w + 2 )
    if i % w < w - 2 and i // w < h - 1:
        if s[ i + w + 2 ] != "#":
            move_b_i.append( i + w + 2 )
    if i % w < w - 1 and i // w < h - 2:
        if s[ i + 2 * w + 1 ] != "#":
            move_b_i.append( i + 2 * w + 1 )
    if i % w > 0 and i // w < h - 2:
        if s[ i + 2 * w - 1 ] != "#":
            move_b_i.append( i + 2 * w - 1 )
    if i % w > 1 and i // w < h - 1:
        if s[ i + w - 2 ] != "#":
            move_b_i.append( i + w - 2 )
    move_b.append( move_b_i )

from heapq import heappush, heappop
INF = 10 ** 10
VISITED = 1
NOT_VISITED = 0
      
cost = [ INF ] * ( h * w )
cost[ c ] = 0
visit = [ NOT_VISITED ] * ( h * w )
visit[ c ] = VISITED
queue = [ ( cost[ c ], c ) ]
while len( queue ) > 0:
    c, v = heappop( queue )
    visit[ v ] = VISITED
    for u in move_a[ v ]:
        if visit[ u ] == VISITED:
            continue
        if cost[ u ] > cost[ v ]:
            cost[ u ] = cost[ v ]
            heappush( queue, ( cost[ u ], u ) )
    for t in move_b[ v ]:
        if visit[ t ] == VISITED:
            continue
        if cost[ t ] > cost[ v ] + 1:
            cost[ t ] = cost[ v ] + 1
            heappush( queue, ( cost[ t ], t ) )

if cost[ d ] == INF:
    print( -1 )
else:
    print( cost[ d ] )

Submission status: Time Limit Exceeded

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

sys.setrecursionlimit(1000)

def yn(b):
    print("Yes" if b==1 else "No")
    return
def aaa(g,memo,www,c):
    ww = www[g]
    memo[g]=c
    c2 = (c+1)
    for i in range(len(ww)):
        w=ww[i]
        if w==1 and i!=g:
            if memo[i]==-1 or memo[i] > c2:
                aaa(i,memo,www,c2)

def tansaku(y,x,mp,done,grp,wrp,w,h,gm,xxx):
    wlkh=[y,y,y-1,y+1]
    wlkw=[x-1,x+1,x,x]
    nun=y*w+x
    grp.add(nun)
    gm[nun]=xxx
    for zzz in range(4):
        zh=wlkh[zzz]
        zw=wlkw[zzz]
        if zh < 0:
            continue
        if zh >= h:
            continue
        if zw < 0:
            continue
        if zw >= w:
            continue
        if mp[zh][zw] == "." and done[zh][zw]==0:
            done[zh][zw]=1
            tansaku(zh,zw,mp,done,grp,wrp,w,h,gm,xxx)
    for i in range(y-2,y+3):
        for j in range(x-2,x+3):
            if i < 0:
                continue
            if i >= h:
                continue
            if j < 0:
                continue
            if j >= w:
                continue
            if mp[i][j]==".":
                wrp.add(i*w+j)

def resolve():
    readline=sys.stdin.readline

    h,w=map(int, readline().rstrip().split())
    ch,cw=map(int, readline().rstrip().split())
    dh,dw=map(int, readline().rstrip().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    mp=[]

    cN=ch*w+cw
    dN=dh*w+dw

    done=[[0 for i in range(w)] for j in range(h)]
    gm=[-1] * ((h*w)+3)

    road=0
    for i in range(h):
        ss=readline().rstrip()
        road+=ss.count(".")
        mp.append(ss)

    gs = []
    ws=[]
    xxx=-1
    for y in range(h):
        for x in range(w):
            masu=y*w+x
            if mp[y][x] == "." and done[y][x]==0:
                grp=set()
                wrp=set()
                xxx+=1
                tansaku(y,x,mp,done,grp,wrp,w,h,gm,xxx)
                gs.append(grp)
                ws.append(wrp)
            else:
                done[y][x]=1
    cnt=len(gs)
    www=[[0 for i in range(cnt)] for j in range(cnt)]
    for i in range(cnt):
        gp = gs[i]
        wp = ws[i]
        for pp in wp:
            j=gm[pp]
            www[i][j]=1
            www[j][i]=1
    memo=[-1]*cnt
    aaa(gm[cN],memo,www,0)
    print(memo[gm[dN]])
    #n,m,k=map(int, readline().rstrip().split())
    #arr=list(map(int, readline().rstrip().split()))
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque

H, W = map(int, input().split())
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S[0] -= 1
S[1] -= 1
G[0] -= 1
G[1] -= 1
c = [input() for i in range(H)]
dist = [[-1]*W for _ in range(H)]

for i in range(H):
    for g in range(W):
        if c[i][g] == "#":
            dist[i][g] = -2

checkList = set()
que = deque()
que.append(S)
dist[S[0]][S[1]] = 0

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

cost = 0
count = 0

while True:
    count += 1
    if count >= 10**7:
        print("あああああ")
        break
    if len(que) == 0:
        cost += 1
        que = set()
        for h, w in checkList:
            for i in range(-2, 3):
                for g in range(-2, 3):
                    nh = h+i
                    nw = w+g
                    if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                        continue
                    else:
                        if dist[nh][nw] == -1:
                            que.add((nh, nw))
        que = deque(que)
        checkList = set()
        if len(que) == 0:
            print(-1)
            exit()
    else:
        h, w = que.popleft()
        if h == G[0] and w == G[1]:
            print(cost)
            exit()
        for i in range(4):
            nh = h+directions[i][0]
            nw = w+directions[i][1]
            if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                continue
            if dist[nh][nw] == -1:
                que.append((nh, nw))
                dist[nh][nw] = cost
            elif dist[nh][nw] == -2:
                checkList.add((h, w))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
cy, cx = map(int, input().split())
dy, dx = map(int, input().split())
cy -= 1
cx -= 1
dy -= 1
dx -= 1
d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
S = [list(input().strip()) for _ in range(H)]

worps = [[float('inf')]*W for _ in range(H)]
q = deque([[cy, cx]])

worps[cy][cx] = 0
while q:
    y, x = q.popleft()
    worp = worps[y][x]

    for h, w in d:
        ny, nx = y+h, x+w
        if 0 <= ny and ny < H and 0 <= nx and nx < W:
            if S[ny][nx] == "." and worp < worps[ny][nx]:
                worps[ny][nx] = worp
                q.appendleft([ny, nx])

    worp += 1
    for h in range(-2+y, 3+y):
        for w in range(-2+x, 3+x):
            if 0 <= h and h < H and 0 <= w and w < W and S[h][w] == "." and worp < worps[h][w]:
                worps[h][w] = worp
                q.appendleft([h, w])

ans = worps[dy][dx]
if ans != float('inf'):
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys, math, re
from functools import lru_cache
from collections import deque
import numpy as np
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    H, W = mi()
    Ch, Cw = mi()
    Dh, Dw = mi()
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    S = [input() for i in range(H)]
    

    d = deque([(Ch, Cw)])
    visited = np.array([[math.inf]*W for i in range(H)])
    visited[Ch][Cw] = 0

    check = np.array([[False]*W for i in range(H)])

    while d:
        now_h, now_w = d.pop()
        check[now_h][now_w] = True

        # 行けるとこリスト
        nexts = []
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == j == 0:
                    continue
                if 0 <= now_h+i < H and 0 <= now_w+j < W and S[now_h+i][now_w+j] == '.':
                        nexts.append((now_h+i, now_w+j))


        for next in nexts:
            next_h, next_w = next

            if abs(now_h-next_h)+abs(now_w-next_w) == 1:
                visited[next_h][next_w] = min(visited[next_h][next_w], visited[now_h][now_w])
                if not check[next_h][next_w]:
                    d.append(next)
            else:
                visited[next_h][next_w] = min(visited[next_h][next_w], visited[now_h][now_w]+1)
                if not check[next_h][next_w]:
                    d.appendleft(next)

    ans = visited[Dh][Dw]
    if ans != math.inf:
        print(int(ans))
    else:
        print(-1)
        

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
def bfs(maze, visited,Ch,Cw,Dh,Dw):
  queue = deque([[Ch,Cw]])
  visited[Ch][Cw] = 0
  while queue:
    y,x = queue.popleft()
 
    for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
      new_y,new_x = y+j,x+k
      if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == ".":
        if visited[new_y][new_x] == "x" or  visited[new_y][new_x] > visited[y][x]:
          visited[new_y][new_x] = visited[y][x]
          queue.append([new_y,new_x])
      elif 0 <= new_y+j < H and 0 <= new_x+k < W and maze[new_y][new_x] == "#"and maze[new_y+j][new_x+k] == ".":
        if visited[new_y+j][new_x+k] == "x" or  visited[new_y+j][new_x+k] > visited[y][x]+1:
          visited[new_y+j][new_x+k] = visited[y][x] +1
          queue.append([new_y+j,new_x+k])
    for l,m in ([1,1],[1,-1],[-1,-1],[-1,1],[1,2],[2,1],[2,2],[1,-2],[2,-1],[2,-2],[-1,-1],[-2,-1],[-2,-2],[-1,-2],[-1,2],[-2,1],[-2,2]):
      ex_y,ex_x = y + l, x + m
      if 0 <= ex_y < H and 0 <= ex_x < W and maze[ex_y][ex_x] == ".":
        if visited[ex_y][ex_x] == "x" or  visited[ex_y][ex_x] > visited[y][x]+1:
          visited[ex_y][ex_x] = visited[y][x] +1
          queue.append([ex_y,ex_x])
 
  if visited[Dh][Dw] == "x":
    return -1
  else:
    return visited[Dh][Dw]
        
        
                                      
      
  
H, W = map(int,input().split())
Ch,Cw =  map(int,input().split())
Dh,Dw = map(int,input().split())
Ch,Cw,Dh,Dw = Ch-1,Cw-1,Dh-1,Dw-1
 
maze = [input() for i in range(H)]
visited = [["x"]*W for j in range(H)]
 
print(bfs(maze, visited,Ch,Cw,Dh,Dw))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def main():
    #ダイクストラ法
    import heapq
    def dijkstra_heap(s):
        #始点sから各頂点への最短距離
        d = [10**18] * h*w
        used = [True] * h*w #True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        for e in edge[s]:
            heapq.heappush(edgelist,e)
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            #まだ使われてない頂点の中から最小の距離のものを探す
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist,[e[0]+d[v],e[1]])
        return d


    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=[input() for _ in range(h)]
    edge=[[] for _ in range(h*w)]
    for i in range(h):
        for j in range(w):
            if s[i][j]=="#":
                continue
            idx=i*w+j
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=i+dx
                    ny=j+dy
                    if 0<=nx<h and 0<=ny<w:
                        idx1=nx*w+ny
                        if dx==0 and dy==0:
                            continue
                        if (dx,dy) in [(-1,0),(0,-1),(1,0),(0,1)]:
                            edge[idx].append([0,idx1])
                        else:
                            edge[idx].append([1,idx1])
    s=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(s)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve(now_x, now_y):
    for next_y in range(-2, 3):
        for next_x in range(-2, 3):
            x, y = now_x + next_x, now_y + next_y
            if 0 <= x < w and 0 <= y < h:
                if c[y][x] != "#" and c[y][x] != "=" and c[y][x] != "!":
                    c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                    d2.append([x, y])


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())
c = [input() for _ in range(h)]
cw -= 1
ch -= 1
dw -= 1
dh -= 1
c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
d1 = deque([[cw, ch]])
d2 = deque([])

cnt = 0
while True:
    while True:
        for _ in range(len(d1)):
            now_x, now_y = d1.popleft()
            for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                x, y = now_x + next_x, now_y + next_y
                if 0 <= x < w and 0 <= y < h:
                    if x == dw and y == dh:
                        print(cnt)
                        exit()
                    if c[y][x] == "#":
                        solve(now_x, now_y)
                    if c[y][x] != "#" and c[y][x] != "=":
                        c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                        d1.append([x, y])

    else:
        cnt += 1
        if [dw, dh] in d2:
            print(cnt)
            exit()
        if not d2:
            print(-1)
            exit()
        d1 = d2.copy()
        d2.clear()

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 = [[-1]*(w+4)]
s.append([-1]*(w+4))
for i in range(h):
  s.append(list(input()))
  for j in range(w):
    if s[i+2][j] == '#':
      s[i+2][j] = -1
    else:
      s[i+2][j] = 10**6
  s[i+2].insert(0,-1)
  s[i+2].insert(0,-1)
  s[i+2].append(-1)
  s[i+2].append(-1)
s.append([-1]*(w+4))
s.append([-1]*(w+4))
s[ch+1][cw+1] = 0

stack = []
stack.append([ch+1,cw+1])
while True:
  if len(stack)==0:
    break
  st = stack.pop()
  sh = st[0]
  sw = st[1]
  if s[sh-1][sw]>s[sh][sw]:
    s[sh-1][sw] = s[sh][sw]
    stack.append([sh-1,sw])
  if s[sh][sw-1]>s[sh][sw]:
    s[sh][sw-1] = s[sh][sw]
    stack.append([sh,sw-1])
  if s[sh+1][sw]>s[sh][sw]:
    s[sh+1][sw] = s[sh][sw]
    stack.append([sh+1,sw])
  if s[sh][sw+1]>s[sh][sw]:
    s[sh][sw+1] = s[sh][sw]
    stack.append([sh,sw+1])
  shh = st[0]-2
  sww = st[1]-2
  for i in range(5):
    for j in range(5):
      if s[shh+i][sww+j] > s[sh][sw]+1:
        s[shh+i][sww+j] = s[sh][sw]+1
        stack.insert(0,[shh+i,sww+j])
      
if s[dh+1][dw+1]==10**6:
  print(-1)
else:
  print(s[dh+1][dw+1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
cy, cx = map(int, input().split())
dy, dx = map(int, input().split())
cy -= 1
cx -= 1
dy -= 1
dx -= 1

S = [list(input().strip()) for _ in range(H)]

worps = [[float('inf')]*W for _ in range(H)]
q = deque([[cy, cx]])

worps[cy][cx] = 0
while q:
    y, x = q.popleft()
    worp = worps[y][x]

    for h, w in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        ny, nx = y+h, x+w
        if 0 <= ny and ny < H and 0 <= nx and nx < W:
            if S[ny][nx] == "." and worp < worps[ny][nx]:
                worps[ny][nx] = worp
                q.appendleft([ny, nx])

    worp += 1
    for h in range(-2+y, 3+y):
        for w in range(-2+x, 3+x):
            if 0 <= h and h < H and 0 <= w and w < W and S[h][w] == "." and worp < worps[h][w]:
                worps[h][w] = worp
                q.appendleft([h, w])

ans = worps[dy][dx]
if ans != float('inf'):
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
h, w = map(int, input().split())
sy, sx = map(lambda x : int(x) + 1, input().split())
gy, gx = map(lambda x : int(x) + 1, input().split())
grid = [['#'] * (w + 4) for _ in range(2)]
for y in range(h):
    grid.append(['#', '#'] + [c for c in input()] + ['#', '#'])
grid.append(['#'] * (w + 4))
grid.append(['#'] * (w + 4))

q = [(0, sy, sx)]
visited = set()

ans = 0
while q:
    n, y, x = heappop(q)
    if (y, x) in visited:
        continue
    if y == gy and x == gx:
        ans = n
        q.append((0, 0, 0)) # dummy
        break
    visited.add((y, x))
    for dy in range(-2, 3):
        yy = y + dy 
        for dx in range(-2, 3):
            xx = x + dx
            if grid[yy][xx] == '.' and (not (yy, xx) in visited):
                if abs(dx) + abs(dy) == 1:
                    heappush(q, (n, yy, xx))
                else:
                    heappush(q, (n+1, yy, xx))

print(ans if q else -1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

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

visited = [[0 for j in range(W)] for i in range(H)]
seen = [[0 for j in range(W)] for i in range(H)]
done = []

def bfs(u):
    stack = deque([u])
    seen[u[0]][u[1]] = 1

    while len(stack) > 0:
        v = stack.popleft()
        done.append(v)
        visited[v[0]][v[1]] = 1
        ###
        w1 = (v[0] + 1, v[1])
        w2 = (v[0] , v[1] + 1)
        w3 = (v[0] - 1, v[1])
        w4 = (v[0] , v[1] -1)
        ###

        ws = [w1,w2,w3,w4]

        for w in ws:
            if w[0] >= 0 and w[0] < H and w[1] >= 0 and w[1] < W:
                if S[w[0]][w[1]] == ".":
                    if seen[w[0]][w[1]] == 0:
                        stack.append(w)
                        seen[w[0]][w[1]] = 1

bfs((Ch-1,Cw-1))

count = 0


while True:
    if visited[Dh-1][Dw-1] == 1:
        print(count)
        sys.exit()
    else:
        count += 1
        pp = deque([])
        for d in done:
            i = d[0]
            j = d[1]
            for k in range(-2,3):
                for l in range(-2,3):
                    if i+k >= 0 and i+k < H and j+l >= 0 and j+l < W:
                        if S[i+k][j+l] == ".":
                            if visited[i+k][j+l] == 0:
                                pp.append((i+k,j+l))

        if len(pp) == 0:
            print(-1)
            break

        for ppp in pp:
            bfs(ppp)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

def main():
    H, W = mapint()
    ch, cw = mapint()
    dh, dw = mapint()
    maze = [list(input()) for _ in range(H)]
    
    dirc = ((-1, 0), (1, 0), (0, -1), (0, 1))
    magic = ((-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))
    from collections import deque
    Q = deque([(ch-1, cw-1)])
    
    dist = [[10**18]*W for _ in range(H)]
    dist[ch-1][cw-1] = 0
    while Q:
        y, x = Q.popleft()
        for dy, dx in dirc:
            ny, nx = y+dy, x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if maze[ny][nx]=='#':
                continue
            if dist[ny][nx]>dist[y][x]:
                dist[ny][nx] = dist[y][x]
                Q.append((ny, nx))
        
        for dy, dx in magic:
            ny, nx = y+dy, x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if maze[ny][nx]=='#':
                continue
            if dist[ny][nx]>dist[y][x]+1:
                dist[ny][nx] = dist[y][x]+1
                Q.appendleft((ny, nx))
    if dist[dh-1][dw-1]>=10**17:
        print(-1)
    else:
        print(dist[dh-1][dw-1])
main()

Submission status: Time Limit Exceeded

Solution code:
import queue

def bfs(x, y):
    if M[x][y] == c:
        return False
    else:
        M[x][y] = c
    q = queue.Queue()
    q.put([x,y])
    while not q.empty():
        now = q.get()
        nowx = now[0]
        nowy = now[1]
        if nowx ==  D1 - 1 and nowy == D2 -1:
            return True
        if 0 < nowy and m[nowx][nowy -1] == '.' and M[nowx][nowy -1] == -1:
            M[nowx][nowy -1] = c
            q.put([nowx,nowy-1])
        if W-1 > nowy and m[nowx][nowy +1] == '.' and M[nowx][nowy +1] == -1:
            M[nowx][nowy +1] = c
            q.put([nowx,nowy+1])
        if 0 < nowx and m[nowx - 1][nowy] == '.'and M[nowx - 1][nowy] == -1:
            M[nowx - 1][nowy] = c
            q.put([nowx - 1,nowy])
        if H - 1 > nowx and m[nowx + 1][nowy] == '.'and M[nowx + 1][nowy] == -1:
            M[nowx + 1][nowy] = c
            q.put([nowx + 1,nowy])
    return False



def jump():
    for i in range (H):
        for j in range (W):
            if M[i][j] == c:
                for k in range(max(0,i-2),min(H,i+3)):
                    for l in range(max(0,j-2),min(W,j+3)):
                        if M[k][l] == -1 and m[k][l] == '.':
                            Q.put([k,l])




H,W = map(int,input().split())
C1,C2 =map(int,input().split())
D1,D2 = map(int,input().split())

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



M = [[-1 for i in range (W)] for j in range (H)]
c = 0
Q = queue.Queue()

Q.put([C1-1,C2-1])
flag = False
f2 = False
while True:
    if Q.empty():
        print(-1)
        f2 = True
        break
    while not Q.empty():
        x,y = Q.get()
        if bfs(x,y) == True:
            flag = True
            break
    if flag == True:
        break
    else:
        jump()
        c += 1

if not f2:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
smat=[]
smat.append([False]*(W+4))
smat.append([False]*(W+4))
for _ in range(H):
  line=[False,False]+[x=="." for x in input()]+[False,False]
  smat.append(line)
smat.append([False]*(W+4))
smat.append([False]*(W+4))
#print(smat)

vlist=[]
#ここで点の集合をvlistに入れておく
for i in range(2,H+2):
  for j in range(2,W+2):
    if smat[i][j]:
      vlist.append((i,j))

graph=defaultdict(list)
#graph[i]: iから出る道の[重み,行先]の辞書
for i in range(2,H+2):
  for j in range(2,W+2):
    if not smat[i][j]:
      continue
    
    if smat[i-1][j]:
      graph[(i,j)].append([(i-1,j),0])
    if smat[i+1][j]:
      graph[(i,j)].append([(i+1,j),0])
    if smat[i][j-1]:
      graph[(i,j)].append([(i,j-1),0])
    if smat[i][j+1]:
      graph[(i,j)].append([(i,j+1),0])
    
    if smat[i-1][j-1]:
      graph[(i,j)].append([(i-1,j-1),1])
    if smat[i-1][j+1]:
      graph[(i,j)].append([(i-1,j+1),1])
    if smat[i+1][j-1]:
      graph[(i,j)].append([(i+1,j-1),1])
    if smat[i+1][j+1]:
      graph[(i,j)].append([(i+1,j+1),1])

    for k in range(-2,3):
      if smat[i-2][j+k]:
        graph[(i,j)].append([(i-2,j+k),1])
      if smat[i+2][j+k]:
        graph[(i,j)].append([(i+2,j+k),1])
        
    for k in range(-1,2):
      if smat[i+k][j-2]:
        graph[(i,j)].append([(i+k,j-2),1])
      if smat[i+k][j+2]:
        graph[(i,j)].append([(i+k,j+2),1])

#print(dist)
#print(prev)

dist={}
queue=[(Ch+1,Cw+1)]
d=0
while queue:
  new_queue=set()

  while queue:
    u=queue.pop()
    dist[u]=d
    if u==(Dh+1,Dw+1):
      print(d)
      sys.exit(0)
    
    for v,w in graph[u]:
      if v in dist:
        continue
      if w==0:
        queue.append(v)
      else:
        new_queue.add(v)

  queue=list(new_queue)
  d+=1
#print(dist)

print(-1)

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=tf-8
#

"""
"""

from collections import defaultdict
import bisect
from itertools import product
import heapq

import sys
input = sys.stdin.readline

def solve(h,w,ch,cw,dh,dw,s):
    graph = defaultdict(list)
    for i,j in product(range(h),range(w)):
        if s[i][j] == ".":
            if i > 0 and s[i-1][j] == ".":
                graph[(i,j)].append((0,(i-1,j)))
                graph[(i-1,j)].append((0,(i,j)))
            if j > 0 and s[i][j-1] == ".":
                graph[(i,j)].append((0,(i,j-1)))
                graph[(i,j-1)].append((0,(i,j)))
            for k, l in product(range(max(0,i-2),i),range(max(0,j-2),j)):
                if s[k][l] == ".":
                    graph[(k,l)].append((1,(i,j)))
                    graph[(i,j)].append((1,(k,l)))
            for k, l in product(range(i+1,min(i+3,h)),range(max(0,j-2),j)):
                if s[k][l] == ".":
                    graph[(k,l)].append((1,(i,j)))
                    graph[(i,j)].append((1,(k,l)))
            if i > 1 and s[i-2][j] == ".":
                    graph[(i-2,j)].append((1,(i,j)))
                    graph[(i,j)].append((1,(i-2,j)))
            if j > 1 and s[i][j-2] == ".":
                    graph[(i,j-2)].append((1,(i,j)))
                    graph[(i,j)].append((1,(i,j-2)))
    d = [[10**7]*w for _ in range(h)]
    d[ch][cw] = 0
    Q = []
    heapq.heappush(Q,(0,(ch,cw)))
    seen = set([])
    while Q:
        dis, pos1 = heapq.heappop(Q)
        i, j = pos1
        for dd, pos2 in graph[pos1]:
            k, l = pos2
            alt = d[i][j] + dd
            if d[k][l] > alt:
                d[k][l] = alt
                heapq.heappush(Q,(alt,pos2))
    ans = d[dh][dw]
    if ans < 10**7:
        print(ans)
    else:
        print(-1)


            

def main():
    h, w = list(map(int,input().split()))
    ch, cw = list(map(int,input().split()))
    dh, dw = list(map(int,input().split()))
    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1
    s = []
    for _ in range(h):
        s.append(list(input().rstrip()))
    solve(h,w,ch,cw,dh,dw,s)


if __name__ == "__main__":
    main()