Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



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


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque

H, W = [int(x) for x in stdin.readline().rstrip().split()]
Si, Sj = [int(x) for x in stdin.readline().rstrip().split()]
Gi, Gj = [int(x) for x in stdin.readline().rstrip().split()]
maze = [stdin.readline().rstrip().split() for _ in range(H)]

INF = float('inf')
check = [[INF for i in range(W)] for j in range(H)]
walk = [(1,0), (0,1), (-1,0), (0,-1)]
qu = deque([(Si-1, Sj-1, 0)])
qu_1 = deque()
check[Si-1][Sj-1] = 0

while qu:
    i, j, cost = qu.popleft()
    qu_1.append((i, j, cost))
    #歩いて移動できるところ
    for k in range(4):
        di, dj = walk[k]
        if 0 <= i+di < H and 0 <= j+dj < W:
            if maze[i+di][0][j+dj] == '#':
                continue
            if check[i+di][j+dj] <= cost:
                continue
            check[i+di][j+dj] = cost
            qu.appendleft((i+di, j+dj, cost))

    if len(qu) == 0:
        #ワープで行けるところ
        while qu_1:
            i, j, cost = qu_1.popleft()
            for di in range(-2, 3):
                for dj in range(-2, 3):
                    if 0 <= i+di < H and 0 <= j+dj < W:
                        if maze[i+di][0][j+dj] == '#':
                            continue
                        if check[i+di][j+dj] <= cost + 1:
                            continue
                        check[i+di][j+dj] = cost + 1
                        qu.append((i+di, j+dj, cost+1))

#print(check)
if check[Gi-1][Gj-1] == INF:
    print(-1)
else:
    print(check[Gi-1][Gj-1])

Submission status: Time Limit Exceeded

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

import heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                heapq.heappush(h, [dist[to], to])
    return dist

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
done = [[-1]*W for _ in range(H)]
def dfs(h, w, num):
    done[h][w] = num
    for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nh, nw = h+dh, w+dw
        if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
            continue
        if done[nh][nw] == -1:
            dfs(nh, nw, num)
num = 0
for i in range(H):
    for j in range(W):
        if done[i][j] == -1 and S[i][j] == ".":
            dfs(i, j, num)
            num += 1
G = [[] for _ in range(num)]
done2 = [[False]*num for _ in range(num)]
for h in range(H):
    for w in range(W):
        if S[h][w] != ".": continue
        fr = done[h][w]
        for ii in range(-2, 3):
            for jj in range(-2, 3):
                nh, nw = h+ii, w+jj
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                to = done[nh][nw]
                if fr != to and (not done2[fr][to]):
                    done2[fr][to] = True
                    done2[to][fr] = True
                    G[fr].append((to, 1))
                    G[to].append((fr, 1))
D = dijkstra(done[sh][sw], G)
ans = D[done[gh][gw]]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    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
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]
#for i in range(h):
#    for j in range(w):
for i in hh:
    for j in ww:
        ggg=[]
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h:
                continue
            if 0>j+jj or j+jj>=w:
                continue
            if s[i+ii][j+jj]==".":
#                g[i][j].append((i+ii,j+jj))        
                ggg.append((i+ii,j+jj))        
            else:
                wpg2[i][j]=1
        g[i][j]=ggg        
                
for i in range(h):
    for j in range(w):
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque

H, W = [int(x) for x in stdin.readline().rstrip().split()]
Si, Sj = [int(x) for x in stdin.readline().rstrip().split()]
Gi, Gj = [int(x) for x in stdin.readline().rstrip().split()]
maze = [stdin.readline().rstrip().split() for _ in range(H)]

INF = float('inf')
check = [[INF for i in range(W)] for j in range(H)]
walk = [(1,0), (0,1), (-1,0), (0,-1)]
qu = deque([(Si-1, Sj-1, 0)])
qu_1 = deque()
check[Si-1][Sj-1] = 0

while qu:
    i, j, cost = qu.popleft()
    qu_1.append((i, j, cost))
    #歩いて移動できるところ
    for k in range(4):
        di, dj = walk[k]
        if 0 <= i+di < H and 0 <= j+dj < W:
            if not maze[i+di][0][j+dj] == '#':
                if check[i+di][j+dj] > cost:
                    check[i+di][j+dj] = cost
                    qu.appendleft((i+di, j+dj, cost))

    if len(qu) == 0:
        #ワープで行けるところ
        while qu_1:
            i, j, cost = qu_1.popleft()
            for di in range(-2, 3):
                for dj in range(-2, 3):
                    if 0 <= i+di < H and 0 <= j+dj < W:
                        if not maze[i+di][0][j+dj] == '#':
                            if check[i+di][j+dj] > cost + 1:
                                check[i+di][j+dj] = cost + 1
                                qu.append((i+di, j+dj, cost+1))

#print(check)
if check[Gi-1][Gj-1] == float('inf'):
    print(-1)
else:
    print(check[Gi-1][Gj-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    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
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]
for i in range(h):
    for j in range(w):
        for ii,jj in ij:
            if 0<=i+ii<h and 0<=j+jj<w:
                if s[i+ii][j+jj]==".":
                    g[i][j].append((i+ii,j+jj))        
                else:
#                wpg.append((i,j))
                    wpg2[i][j]=1

for i in range(h):
    for j in range(w):
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
#wpg=tuple(set(wpg))

for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque

H, W = map(int, input().split())
Si, Sj = map(int, input().split())
Gi, Gj = map(int, input().split())
maze = [input().split() for _ in range(H)]

check = [[float('inf') for i in range(W)] for j in range(H)]
walk = [(0,-1), (0,1), (-1,0), (1,0)]
qu = deque([(Si-1, Sj-1, 0)])
qu_1 = deque()
check[Si-1][Sj-1] = 0

while qu:
    i, j, cost = qu.popleft()
    qu_1.append((i, j, cost))
    #歩いて移動できるところ
    for k in range(4):
        di, dj = walk[k]
        if 0 <= i+di < H and 0 <= j+dj < W:
            if not maze[i+di][0][j+dj] == '#':
                if check[i+di][j+dj] > cost:
                    check[i+di][j+dj] = cost
                    qu.appendleft((i+di, j+dj, cost))

    if len(qu) == 0:
        #ワープで行けるところ
        while qu_1:
            i, j, cost = qu_1.popleft()
            for di in range(-2, 3):
                for dj in range(-2, 3):
                    if 0 <= i+di < H and 0 <= j+dj < W:
                        if not maze[i+di][0][j+dj] == '#':
                            if check[i+di][j+dj] > cost + 1:
                                check[i+di][j+dj] = cost + 1
                                qu.append((i+di, j+dj, cost+1))

#print(check)
if check[Gi-1][Gj-1] == float('inf'):
    print(-1)
else:
    print(check[Gi-1][Gj-1])

Submission status: Time Limit Exceeded

Solution code:
import heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                heapq.heappush(h, [dist[to], to])
    return dist

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
def dfs(h, w, num):
    dic[(h, w)] = num
    for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nh, nw = h+dh, w+dw
        if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
            continue
        if not (nh, nw) in dic:
            dfs(nh, nw, num)
dic = {}
num = 0
for i in range(H):
    for j in range(W):
        if (not (i, j) in dic) and S[i][j] == ".":
            dfs(i, j, num)
            num += 1
G = [[] for _ in range(num)]
done = [[False]*num for _ in range(num)]
for h in range(H):
    for w in range(W):
        if S[h][w] != ".": continue
        fr = dic[(h, w)]
        for ii in range(-2, 3):
            for jj in range(-2, 3):
                nh, nw = h+ii, w+jj
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                to = dic[(nh, nw)]
                if fr != to and (not done[fr][to]):
                    done[fr][to] = True
                    done[to][fr] = True
                    G[fr].append((to, 1))
                    G[to].append((fr, 1))
D = dijkstra(dic[(sh, sw)], G)
ans = D[dic[(gh, gw)]]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    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
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]
for i in range(h):
    for j in range(w):
        ggg=[]
        for ii,jj in ij:
            if 0>i+ii or i+ii>=h:
                continue
            if 0>j+jj or j+jj>=w:
                continue
            if s[i+ii][j+jj]==".":
#                g[i][j].append((i+ii,j+jj))        
                ggg.append((i+ii,j+jj))        
            else:
#                wpg.append((i,j))
                wpg2[i][j]=1
        g[i][j]=ggg        
                
for i in range(h):
    for j in range(w):
        if wpg2[i][j]==1:
            wpg.append((i,j))
                
#wpg=tuple(set(wpg))

for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

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

Submission status: Time Limit Exceeded

Solution code:
def num():
    from collections import deque
    h, w = map(int, input().split())
    c0, c1 = map(int, input().split())
    d0, d1 = map(int, input().split())
    s = [["#"]*(w+4)]*2+[["#"]*2+list(input())+["#"]*2 for _ in range(h)]+[["#"]*(w+4)]*2
    q = deque([[c0+1, c1+1, 0]])
    q1 = deque()
    ans = -1
    move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)]+move]
    
    while q:
        a0, a1, a2 = q.pop()
        q1.append((a0, a1, a2))
        s[a0][a1] = '#'
        if a0 == d0+1 and a1 == d1+1:
            ans = a2
            break

        for i, j in move:
            x = a0+i
            y = a1+j
            if s[x][y] == '.':
                q.append((x, y, a2))
        if len(q) == 0:
            while q1:
                a0, a1, a2 = q1.pop()
                for i, j in warp:
                    x = a0+i
                    y = a1+j
                    if s[x][y] == '.':
                        q.append((x, y, a2+1))
    print(ans)

if __name__ == "__main__":
    num()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque

H, W = [int(x) for x in stdin.readline().rstrip().split()]
Si, Sj = [int(x) for x in stdin.readline().rstrip().split()]
Gi, Gj = [int(x) for x in stdin.readline().rstrip().split()]
maze = [stdin.readline().rstrip().split() for _ in range(H)]

check = [[float('inf') for i in range(W)] for j in range(H)]
walk = [(0,-1), (0,1), (-1,0), (1,0)]
qu = deque([(Si-1, Sj-1, 0)])
qu_1 = deque()
check[Si-1][Sj-1] = 0

while qu:
    i, j, cost = qu.popleft()
    qu_1.append((i, j, cost))
    #歩いて移動できるところ
    for k in range(4):
        di, dj = walk[k]
        if 0 <= i+di < H and 0 <= j+dj < W:
            if not maze[i+di][0][j+dj] == '#':
                if check[i+di][j+dj] > cost:
                    check[i+di][j+dj] = cost
                    qu.appendleft((i+di, j+dj, cost))

    if len(qu) == 0:
        #ワープで行けるところ
        while qu_1:
            i, j, cost = qu_1.popleft()
            for di in range(-2, 3):
                for dj in range(-2, 3):
                    if 0 <= i+di < H and 0 <= j+dj < W:
                        if not maze[i+di][0][j+dj] == '#':
                            if check[i+di][j+dj] > cost + 1:
                                check[i+di][j+dj] = cost + 1
                                qu.append((i+di, j+dj, cost+1))

#print(check)
if check[Gi-1][Gj-1] == float('inf'):
    print(-1)
else:
    print(check[Gi-1][Gj-1])

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

@lru_cache()
def num():
    from collections import deque
    h, w = map(int, input().split())
    c0, c1 = map(int, input().split())
    d0, d1 = map(int, input().split())
    s = [["#"]*(w+4)]*2+[["#"]*2+list(input())+["#"]*2 for _ in range(h)]+[["#"]*(w+4)]*2
    q = deque([[c0+1, c1+1, 0]])
    q1 = deque()
    ans = -1
    move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)]+move]
    
    while q:
        a0, a1, a2 = q.pop()
        q1.append((a0, a1, a2))
        s[a0][a1] = '#'
        if a0 == d0+1 and a1 == d1+1:
            ans = a2
            break

        for i, j in move:
            x, y = a0+i, a1+j
            if s[x][y] == '.':
                q.append((x, y, a2))
        if len(q) == 0:
            while q1:
                a0, a1, a2 = q1.pop()
                for i, j in warp:
                    x, y = a0+i, a1+j
                    if s[x][y] == '.':
                        q.append((x, y, a2+1))
    print(ans)

if __name__ == "__main__":
    num()

Submission status: Time Limit Exceeded

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

H,W = map(int , input().split())
sh,sw = map(int , input().split())
eh,ew = map(int , input().split())
mv_a_pts = [[-1,0],[1,0],[0,-1],[0,1]]
mv_b_pts = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
        (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),
        (0, -2), (0, -1), (0, 1), (0, 2),
        (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),
        (2, -2), (2, -1), (2, 0), (2, 1), (2, 2),]
maze = [input() for _ in range(H)]
warp_cnts = [[None]*(W) for j in range(H)]

def mv_a(h,w):
  mv_b_tgs.append([h,w])
  warp_cnts[h][w] = cnt
  for vh,vw in mv_a_pts:
    tgh = h + vh
    tgw = w + vw
    if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
      if warp_cnts[tgh][tgw] is None and maze[tgh][tgw] != "#":
        mv_a(tgh,tgw)

def mv_b(h,w):
  for vh,vw in mv_b_pts:
    tgh = h + vh
    tgw = w + vw
    if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
      if warp_cnts[tgh][tgw] is None and maze[tgh][tgw] != "#":
        mv_a_tgs.append([tgh,tgw])
        

mv_b_tgs=[]
mv_a_tgs = [[sh-1,sw-1]]
cnt = 0
while len(mv_a_tgs)>0:
  while len(mv_a_tgs):
    tg0,tg1 = mv_a_tgs.pop()
    mv_a(tg0,tg1)
  while len(mv_b_tgs):
    wp0,wp1 = mv_b_tgs.pop()
    mv_b(wp0,wp1)
  cnt+=1
print(-1 if warp_cnts[eh-1][ew-1] is None else warp_cnts[eh-1][ew-1])

Submission status: Time Limit Exceeded

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

H,W = map(int , input().split())
sh,sw = map(int , input().split())
eh,ew = map(int , input().split())
mv_a_pts = [[-1,0],[1,0],[0,-1],[0,1]]
mv_b_pts = []
for h in range(-2,3,1):
  for w in range(-2,3,1):
    if h != 0 or w != 0:
      mv_b_pts.append([h,w])
maze = [input() for _ in range(H)]
warp_cnts = [[None]*(W) for j in range(H)]

def mv_a(h,w):
  mv_b_tgs.append([h,w])
  warp_cnts[h][w] = cnt
  for vh,vw in mv_a_pts:
    tgh = h + vh
    tgw = w + vw
    if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
      if warp_cnts[tgh][tgw] is None and maze[tgh][tgw] != "#":
        mv_a(tgh,tgw)

def mv_b(h,w):
  for vh,vw in mv_b_pts:
    tgh = h + vh
    tgw = w + vw
    if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
      if warp_cnts[tgh][tgw] is None and maze[tgh][tgw] != "#":
        mv_a_tgs.append([tgh,tgw])
        

mv_b_tgs=[]
mv_a_tgs = [[sh-1,sw-1]]
cnt = 0
while len(mv_a_tgs)>0:
  while len(mv_a_tgs):
    tg0,tg1 = mv_a_tgs.pop()
    mv_a(tg0,tg1)
  while len(mv_b_tgs):
    wp0,wp1 = mv_b_tgs.pop()
    mv_b(wp0,wp1)
  cnt+=1
print(-1 if warp_cnts[eh-1][ew-1] is None else warp_cnts[eh-1][ew-1])

Submission status: Time Limit Exceeded

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

H,W = map(int , input().split())
sh,sw = map(int , input().split())
eh,ew = map(int , input().split())
mv_a_pts = [[-1,0],[1,0],[0,-1],[0,1]]
mv_b_pts = []
for h in range(-2,3,1):
  for w in range(-2,3,1):
    if h != 0 or w != 0:
      mv_b_pts.append([h,w])
maze = [input() for _ in range(H)]
warp_cnts = [[None]*(W) for j in range(H)]

def mv_a(h,w):
  mv_b_tgs.append([h,w])
  warp_cnts[h][w] = cnt
  for vh,vw in mv_a_pts:
    tgh = h + vh
    tgw = w + vw
    if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
      if warp_cnts[tgh][tgw] is None and maze[tgh][tgw] != "#":
        mv_a(tgh,tgw)

def mv_b(h,w):
  for vh,vw in mv_b_pts:
    tgh = h + vh
    tgw = w + vw
    if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
      if warp_cnts[tgh][tgw] is None and maze[tgh][tgw] != "#":
        mv_a_tgs.append([tgh,tgw])
        

mv_b_tgs=[]
mv_a_tgs = [[sh-1,sw-1]]
cnt = 0
while len(mv_a_tgs)>0:
  while len(mv_a_tgs):
    tg = mv_a_tgs.pop()
    mv_a(tg[0],tg[1])
  while len(mv_b_tgs):
    wp = mv_b_tgs.pop()
    mv_b(wp[0],wp[1])
  cnt+=1
print(-1 if warp_cnts[eh-1][ew-1] is None else warp_cnts[eh-1][ew-1])

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int , input().split())
sh,sw = map(int , input().split())
eh,ew = map(int , input().split())
mv_a_pts = [[-1,0],[1,0],[0,-1],[0,1]]
mv_b_pts = []
for h in range(-2,3,1):
  for w in range(-2,3,1):
    if h != 0 or w != 0:
      mv_b_pts.append([h,w])
maze = []
warp_cnts = [[None]*(W) for j in range(H)]
for i in range(H):
  maze.append(input())

def mv_a(h,w):
  mv_b_tgs.append([h,w])
  warp_cnts[h][w] = cnt
  for vh,vw in mv_a_pts:
    tgh = h + vh
    tgw = w + vw
    if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
      if warp_cnts[tgh][tgw] is None and maze[tgh][tgw] != "#":
        mv_a(tgh,tgw)

def mv_b(h,w):
  for vh,vw in mv_b_pts:
    tgh = h + vh
    tgw = w + vw
    if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
      if warp_cnts[tgh][tgw] is None and maze[tgh][tgw] != "#":
        mv_a_tgs.append([tgh,tgw])


mv_b_tgs=[]
mv_a_tgs = [[sh-1,sw-1]]
cnt = 0
while len(mv_a_tgs)>0:
  while len(mv_a_tgs):
    tg = mv_a_tgs.pop()
    mv_a(tg[0],tg[1])
  while len(mv_b_tgs):
    wp = mv_b_tgs.pop()
    mv_b(wp[0],wp[1])
  cnt+=1
print(-1 if warp_cnts[eh-1][ew-1] is None else warp_cnts[eh-1][ew-1])

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def bfs():
    d = [[inf]*w for i in range(h)]

    dy_dx0 = [[0,1],[1,0],[0,-1],[-1,0]] 
    dy_dx1 = [[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]]

    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0
 
    while que:
        p = que.popleft()
        if p[0] == gy and p[1] == gx:
            break
        for i in range(4):
            ny = p[0] + dy_dx0[i][0]
            nx = p[1] + dy_dx0[i][1]
 
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != '#' and d[ny][nx] > d[p[0]][p[1]]:
                que.appendleft((ny,nx))
                d[ny][nx] = d[p[0]][p[1]]

        for i in range(20):
            ny = p[0] + dy_dx1[i][0]
            nx = p[1] + dy_dx1[i][1]
 
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != '#' and d[ny][nx] == inf:
                que.append((ny,nx))
                d[ny][nx] = d[p[0]][p[1]] + 1 
 
    return d[gy][gx]

h, w = MAP()
sy, sx = MAP1()
gy, gx = MAP1()
s = [input() for _ in range(h)]
ans = bfs()
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
cy, cx = map(int, input().split())
dy, dx = map(int, input().split())
maze = ['#'*(W+2)]
for hh in range(H):
    maze.append('#' + input() + '#')
maze.append('#'*(W+2))

stepx = [-1, 0, 1, 0]
stepy = [0, -1, 0, 1]
visited = [[0]*(W+2) for _ in range(H+2)]
def floodfill(comp, src):
    count = 0
    while len(src) > 0:
        stak = []
        for (sy, sx) in src:
            #add to new component
            visited[sy][sx] = comp
            count += 1
            for i in range(4):
                ny, nx = sy + stepy[i], sx + stepx[i]
                if nx > 0 and nx <= W and ny > 0 and ny <= H\
                        and visited[ny][nx] == 0 and maze[ny][nx] == '.':
                    visited[ny][nx] = -1
                    stak.append((ny, nx))
        src = stak

    return count


def findnext(comp):
    count = 0
    nxt = []
    for h in range(1, H+1):
        for w in range(1, W+1):
            if visited[h][w] == comp:
                for ii in range(-2, 3):
                    nh = h + ii
                    if nh > 0 and nh <= H:
                        for jj in range(-2, 3):
                            nw = w + jj
                            if nw > 0 and nw <= W and visited[nh][nw] == 0 and maze[nh][nw] == '.':
                                visited[nh][nw] = -1
                                nxt.append((nh, nw))

    return nxt

ans = 0
total = 0
comp = 1

#floodfill source
if maze[cy][cx] == '.' and visited[cy][cx] == 0:
    count = floodfill(comp, [(cy, cx)])

# #floodfill dest
# if maze[dy][dx] == '.' and visited[dy][dx] == 0:
#     count = floodfill(comp, (dy, dx))
#     if count > 0:
#         total += count
#         comp += 1
#
#
while count > 0 and visited[dy][dx] <= 0:
    total += count
    src = findnext(comp)
    comp += 1
    if len(src) > 0:
        count = floodfill(comp, src)
    else: count = 0

print(visited[dy][dx] - 1)