Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

1

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

Note that he cannot walk diagonally.

Sample Input 2

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

Sample Output 2

-1

He cannot move from there.

Sample Input 3

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

Sample Output 3

0

No use of magic is needed.

Sample Input 4

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

Sample Output 4

2



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


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np
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
table = []
for i in range(h):
    table.append(input())

def check(h_tmp, w_tmp, steps):
    if h_tmp < 0 or w_tmp < 0 or h_tmp >= h or w_tmp >= w:
        return False
    elif visit[h_tmp][w_tmp] <= steps:
        return False
    elif table[h_tmp][w_tmp] == '#':
        return False
    else:
        return True

q = deque()
q.append((ch, cw, 0, 0))
ans = 1000000
visit = np.full((h, w), 1000000)

while not len(q) == 0:
    now = q.popleft()
    visit[now[0]][now[1]] = min(visit[now[0]][now[1]], now[3])
    if now[0] == dh and now[1] == dw:
        ans = visit[now[0]][now[1]]
        break

    if check(now[0]+1, now[1], now[3]):
        q.appendleft((now[0]+1, now[1], now[2] + 1, now[3]))
    if check(now[0], now[1]+1, now[3]):
        q.appendleft((now[0], now[1]+1, now[2] + 1, now[3]))
    if check(now[0]-1, now[1], now[3]):
        q.appendleft((now[0]-1, now[1], now[2] + 1, now[3]))
    if check(now[0], now[1]-1, now[3]):
        q.appendleft((now[0], now[1]-1, now[2] + 1, now[3]))

    if check(now[0]+1, now[1]+1, now[3]+1):
        q.append((now[0]+1, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]+1, now[3]+1):
        q.append((now[0]-1, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]+1, now[1]-1, now[3]+1):
        q.append((now[0]+1, now[1]-1, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]-1, now[3]+1):
        q.append((now[0]-1, now[1]-1, now[2] + 1, now[3]+1))

    if check(now[0]+2, now[1], now[3]+1):
        q.append((now[0]+2, now[1], now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]+1, now[3]+1):
        q.append((now[0]+2, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]+2, now[3]+1):
        q.append((now[0]+2, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]-1, now[3]+1):
        q.append((now[0]+2, now[1]-1, now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]-2, now[3]+1):
        q.append((now[0]+2, now[1]-2, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1], now[3]+1):
        q.append((now[0]-2, now[1], now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]+1, now[3]+1):
        q.append((now[0]-2, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]+2, now[3]+1):
        q.append((now[0]-2, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]-1, now[3]+1):
        q.append((now[0]-2, now[1]-1, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]-2, now[3]+1):
        q.append((now[0]-2, now[1]-2, now[2] + 1, now[3]+1))

    if check(now[0], now[1]+2, now[3]+1):
        q.append((now[0], now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]+2, now[3]+1):
        q.append((now[0]-1, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]+1, now[1]+2, now[3]+1):
        q.append((now[0]+1, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0], now[1]-2, now[3]+1):
        q.append((now[0], now[1]-2, now[2] + 1, now[3]+1))
    if check(now[0]+1, now[1]-2, now[3]+1):
        q.append((now[0]+1, now[1]-2, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]-2, now[3]+1):
        q.append((now[0]-1, now[1]-2, now[2] + 1, now[3]+1))
if not ans == 1000000:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

import heapq

INF = 10 ** 10

class Edge():
    def __init__(self, end, cost):
        self.end = end
        self.cost = cost

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heapq.heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for e in G[v]:
            if dist[e.end] > dist[v] + e.cost:
                dist[e.end] = dist[v] + e.cost
                heapq.heappush(h, (dist[e.end], e.end))
    return dist


H, W = map(int, input().split())
N = H * W
ch, cw = map(lambda x:int(x)-1, input().split())
gh, gw = map(lambda x:int(x)-1, input().split())

s = []
es = [[] for i in range(N)]

for h in range(H):
   s.append(input().rstrip('\n'))

for h in range(H):
    for w in range(W):
        if s[h][w] != '.':
            continue
        for dh in (-2, -1, 0, 1, 2):
            for dw in (-2, -1, 0, 1, 2):
                if dh == 0 and dw == 0:
                    continue
                nh = h + dh
                nw = w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W and s[nh][nw] == '.':
                    a = h*W+w
                    b = nh*W+nw
                    if (dh, dw) in [(-1,0),(1,0),(0,-1),(0,1)]:
                        es[a].append(Edge(b, 0))
                    else:
                        es[a].append(Edge(b, 1))

dist = dijkstra(N, es, ch*W+cw)
if dist[gh*W+gw] == INF:
    print(-1)
else:
    print(dist[gh*W+gw])

Submission status: Time Limit Exceeded

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

import heapq

INF = 10 ** 10

class Edge():
    def __init__(self, start, end, cost):
        self.start = start
        self.end = end
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.start, self.end, self.cost)

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heapq.heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for e in G[v]:
            if dist[e.end] > dist[v] + e.cost:
                dist[e.end] = dist[v] + e.cost
                heapq.heappush(h, (dist[e.end], e.end))
    return dist


H, W = map(int, input().split())
N = H * W
ch, cw = map(lambda x:int(x)-1, input().split())
gh, gw = map(lambda x:int(x)-1, input().split())

s = []
es = [[] for i in range(N)]

for h in range(H):
   s.append(input().rstrip('\n'))

for h in range(H):
    for w in range(W):
        if s[h][w] != '.':
            continue
        for dh in (-2, -1, 0, 1, 2):
            for dw in (-2, -1, 0, 1, 2):
                if dh == 0 and dw == 0:
                    continue
                nh = h + dh
                nw = w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W and s[nh][nw] == '.':
                    a = h*W+w
                    b = nh*W+nw
                    if (dh, dw) in [(-1,0),(1,0),(0,-1),(0,1)]:
                        es[a].append(Edge(a, b, 0))
                    else:
                        es[a].append(Edge(a, b, 1))

dist = dijkstra(N, es, ch*W+cw)
if dist[gh*W+gw] == INF:
    print(-1)
else:
    print(dist[gh*W+gw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())

#input maze information
s = ["#"*(W+4)]
s.append("#"*(W+4))
for i in range(H):
    s.append("##"+input()+"##")
s.append("#"*(W+4))
s.append("#"*(W+4))

ans = [[-1]*(W+4) for _ in range(H+4)]
for i in range(H+4):
    for j in range(W+4):
        if s[i][j] == "#":
            ans[i][j] = -2 #壁があるところは−２と重みをつけておく

ch += 1;cw += 1
dh += 1;dw += 1
ans[ch][cw]=0

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

list1=deque([[ch,cw]])
list2=deque([])

while len(list1)>0:
    x,y = list1.popleft()
    list2.append([x,y])
    for p,q in move:
        v1,v2 = x+p,y+q
        if ans[v1][v2] == -1:
            list1.append([v1,v2])
            ans[v1][v2] = ans[x][y]
    if len(list1)==0:
        while len(list2) > 0:
            x2,y2 = list2.popleft()
            for v1,v2 in magic:
                i,j = x2+v1,y2+v2
                if ans [i][j] == -1:
                    ans[i][j] = ans[x2][y2]+1
                    list1.append([i,j])
print(ans[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    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
    Smatrix = []
    for _ in range(H):
        s = list(input())
        Smatrix.append(s)


    d = collections.deque([(Ch, Cw)])
    checked = set()

    count = 0
    flag = False
    while len(d) > 0:
        beforechecked = set()
        while len(d) > 0:
            nowh, noww = d.popleft()
            checked.add((nowh, noww))
            beforechecked.add((nowh, noww))
            if (nowh, noww) == (Dh, Dw):
                print(count)
                flag = True
                sys.exit()
            hwlist = [(nowh+1, noww), (nowh, noww+1), (nowh-1, noww), (nowh, noww-1)]
            for h, w in hwlist:
                if (h, w) in checked:
                    continue
                if 0 <= h < H and 0 <= w < W and Smatrix[h][w] == '.':
                    d.append((h, w))
        count += 1
        for bh, bw in beforechecked:
            for hdef in range(5):
                for wdef in range(5):
                    h, w = bh - 2 + hdef, bw - 2 + wdef
                    if (h, w) in checked:
                        continue
                    if 0 <= h < H and 0 <= w < W and Smatrix[h][w] == '.':
                        d.append((h, w))
    print(-1)




if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())

#input maze information
s = ["#"*(W+4)]
s.append("#"*(W+4))
for i in range(H):
    s.append("##"+input()+"##")
s.append("#"*(W+4))
s.append("#"*(W+4))

ans = [[-1]*(W+4) for _ in range(H+4)]
for i in range(H+4):
    for j in range(W+4):
        if s[i][j] == "#":
            ans[i][j] = -2 #壁があるところは−２と重みをつけておく

ch += 1
cw += 1
dh += 1
dw += 1
ans[ch][cw]=0

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

list1=deque([[ch,cw]])
list2=deque([])

while len(list1)>0:
    x,y = list1.popleft()
    list2.append([x,y])
    for p,q in move:
        v1,v2 = x+p,y+q
        if ans[v1][v2] == -1:
            list1.append([v1,v2])
            ans[v1][v2] = ans[x][y]
    if len(list1)==0:
        while len(list2) > 0:
            x2,y2 = list2.popleft()
            for v1,v2 in magic:
                i,j = x2+v1,y2+v2
                if ans [i][j] == -1:
                    ans[i][j] = ans[x2][y2]+1
                    list1.append([i,j])
print(ans[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    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
    Smatrix = []
    allpoints = set()
    for _ in range(H):
        s = list(input())
        Smatrix.append(s)

    for h in range(H):
        for w in range(W):
            if Smatrix[h][w] == '.':
                allpoints.add((h, w))

    def checkaround(h, w):
        now = neomatrix[h][w]
        if now == 0:
            now = point + 1
        point += 1
        side = [w-1, w+1]
        updown = [h-1, h+1]
        for s in side:
            for u in updown:
                if 0 <= s < W and 0 <= u < H:
                    if Smatrix[s][u] == '.':
                        neomatrix[s][u] = now

    d = collections.deque([(Ch, Cw)])
    checked = set()

    count = 0
    flag = False
    while len(d) > 0:
        beforechecked = set()
        while len(d) > 0:
            nowh, noww = d.popleft()
            checked.add((nowh, noww))
            beforechecked.add((nowh, noww))
            if (nowh, noww) == (Dh, Dw):
                print(count)
                flag = True
                sys.exit()
            hwlist = [(nowh+1, noww), (nowh, noww+1), (nowh-1, noww), (nowh, noww-1)]
            for h, w in hwlist:
                if (h, w) in checked:
                    continue
                if 0 <= h < H and 0 <= w < W and Smatrix[h][w] == '.':
                    d.append((h, w))
        count += 1
        for bh, bw in beforechecked:
            for hdef in range(5):
                for wdef in range(5):
                    h, w = bh - 2 + hdef, bw - 2 + wdef
                    if (h, w) in checked:
                        continue
                    if 0 <= h < H and 0 <= w < W and Smatrix[h][w] == '.':
                        d.append((h, w))
    print(-1)




if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
S=[[x=='#' for x in list(input())] for _ in range(H)]
d={(CH-1,CW-1):0}
q=[(CH-1,CW-1,0)]
def check(h,w,c,o):
    if h < 0 or h >= H or w < 0 or w >= W:
        return
    key=(h,w)
    if key in d:
        if d[key]<=c:
            return
    if S[h][w]:
        return
    if o:
        q.append((h,w,c))
        d[key]=c
    else:
        q.insert(0,(h,w,c+1))
        d[key]=c+1
while q:
    h,w,c=q.pop()
    # walk
    check(h-1,w-0,c,True)
    check(h-0,w-1,c,True)
    check(h+1,w+0,c,True)
    check(h+0,w+1,c,True)
    # warp
    check(h-1,w-1,c,False)
    check(h+1,w+1,c,False)
    for i in [-2,+2]:
        for j in range(-2,3):
            check(h+i,w+j,c,False)
            check(h+j,w+i,c,False)
key=(DH-1,DW-1)
if key in d:
    print(d[key])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs():
    h,w=map(int,input().split())
    sy,sx=map(int,input().split())
    gy,gx=map(int,input().split())
    sy-=1;sx-=1;gy-=1;gx-=1
    s=[list(input()) for _ in range(h)]
    dict={".":10000000,"#":-1}
    s=[[dict[s[y][x]] for x in range(w)]for y in range(h)]
    s[sy][sx]=0
    que=deque([[sy,sx]])
    temp=[(1,0),(0,1),(-1,0),(0,-1),(2,2),(2,1),(2,0),(2,-1),(2,-2),(1,2),(1,1),(1,-1),(1,-2),(0,2),(0,-2),(-1,2),(-1,1),(-1,-1),(-1,-2),(-2,2),(-2,1),(-2,0),(-2,-1),(-2,-2)]
    while que:
        y,x=que.popleft()
        for i,j in temp:
            if 0<=y+i<h and 0<=x+j<w and s[y+i][x+j]>=0:
                nexty,nextx=y+i,x+j
                dist=s[nexty][nextx]
                if abs(i)+abs(j)<=1 and dist>s[y][x]:
                    s[nexty][nextx]=s[y][x]
                    que.append([nexty,nextx])
                elif dist>s[y][x]+1:
                    s[nexty][nextx]=s[y][x]+1
                    que.append([nexty,nextx])

    if s[gy][gx]==10000000:
        print(-1)
    else:
        print(s[gy][gx])

bfs()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
S=[[x=='#' for x in list(input())] for _ in range(H)]
d={(CH-1,CW-1):0}
q=deque([(CH-1,CW-1,0)])
def check(h,w,c,o):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    key=(h,w)
    if key in d:
        if d[key]<=c:
            return False
    if S[h][w]:
        return False
    if o:
        q.append((h,w,c))
        d[key]=c
    else:
        q.appendleft((h,w,c+1))
        d[key]=c+1
    return True
dh=DH-1
dw=DW-1
key=(dh,dw)
while q:
    h,w,c=q.pop()
    if h==dh and w==dw:
        print(d[key])
        exit(0)
    # walk
    check(h-1,w-0,c,True)
    check(h-0,w-1,c,True)
    check(h+1,w+0,c,True)
    check(h+0,w+1,c,True)
    # warp
    check(h-1,w-1,c,False)
    check(h+1,w+1,c,False)
    for i in [-2,+2]:
        for j in range(-2,3):
            check(h+i,w+j,c,False)
            check(h+j,w+i,c,False)

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())

#input maze information
s = ["#"*(W+4)]
s.append("#"*(W+4))
for i in range(H):
    s.append("##"+input()+"##")
s.append("#"*(W+4))
s.append("#"*(W+4))

ans = [[-1]*(W+4) for _ in range(H+4)]
for i in range(H+4):
    for j in range(W+4):
        if s[i][j] == "#":
            ans[i][j] = -2 #壁があるところは−２と重みをつけておく

ch += 1
cw += 1
dh += 1
dw += 1
ans[ch][cw]=0

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

list1=deque([])
list2=deque([])
list1.append([ch,cw])

while len(list1)>0:
    x,y = list1.popleft()
    list2.append([x,y])
    for p,q in move:
        v1,v2 = x+p,y+q
        if ans[v1][v2] == -1:
            list1.append([v1,v2])
            ans[v1][v2] = ans[x][y]
    if len(list1)==0:
        while len(list2) > 0:
            x2,y2 = list2.popleft()
            for v1,v2 in magic:
                i,j = x2+v1,y2+v2
                if ans [i][j] == -1:
                    ans[i][j] = ans[x2][y2]+1
                    list1.append([i,j])
print(ans[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
# import queue
from collections import deque
import numpy as np
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
table = []
for i in range(h):
    table.append(input())
# print(table)

def check(h_tmp, w_tmp, steps):
    if h_tmp < 0 or w_tmp < 0 or h_tmp >= h or w_tmp >= w:
        return False
    elif visit[h_tmp][w_tmp] <= steps:
        return False
    elif table[h_tmp][w_tmp] == '#':
        return False
    else:
        return True


# q = queue.Queue()
q = deque()
q.append((ch, cw, 0, 0))
ans = 1000000000
visit = np.full((h, w), 1000000000)
# visit = [[1000000000] * w for _ in range(h)]
# print(visit)
while not len(q) == 0:
    now = q.popleft()
    visit[now[0]][now[1]] = min(visit[now[0]][now[1]], now[3])
    # print(q.qsize())
    # print(now)
    if now[0] == dh and now[1] == dw:
        # print(now[0], now[1])
        ans = visit[now[0]][now[1]]
        # ans = min(ans, now[3])
        # continue
        break
    # print(now[0], now[1])

    if check(now[0]+1, now[1], now[3]):
        q.appendleft((now[0]+1, now[1], now[2] + 1, now[3]))
    if check(now[0], now[1]+1, now[3]):
        q.appendleft((now[0], now[1]+1, now[2] + 1, now[3]))
    if check(now[0]-1, now[1], now[3]):
        q.appendleft((now[0]-1, now[1], now[2] + 1, now[3]))
    if check(now[0], now[1]-1, now[3]):
        q.appendleft((now[0], now[1]-1, now[2] + 1, now[3]))

    if check(now[0]+1, now[1]+1, now[3]+1):
        q.append((now[0]+1, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]+1, now[3]+1):
        q.append((now[0]-1, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]+1, now[1]-1, now[3]+1):
        q.append((now[0]+1, now[1]-1, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]-1, now[3]+1):
        q.append((now[0]-1, now[1]-1, now[2] + 1, now[3]+1))

    if check(now[0]+2, now[1], now[3]+1):
        q.append((now[0]+2, now[1], now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]+1, now[3]+1):
        q.append((now[0]+2, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]+2, now[3]+1):
        q.append((now[0]+2, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]-1, now[3]+1):
        q.append((now[0]+2, now[1]-1, now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]-2, now[3]+1):
        q.append((now[0]+2, now[1]-2, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1], now[3]+1):
        q.append((now[0]-2, now[1], now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]+1, now[3]+1):
        q.append((now[0]-2, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]+2, now[3]+1):
        q.append((now[0]-2, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]-1, now[3]+1):
        q.append((now[0]-2, now[1]-1, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]-2, now[3]+1):
        q.append((now[0]-2, now[1]-2, now[2] + 1, now[3]+1))

    if check(now[0], now[1]+2, now[3]+1):
        q.append((now[0], now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]+2, now[3]+1):
        q.append((now[0]-1, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]+1, now[1]+2, now[3]+1):
        q.append((now[0]+1, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0], now[1]-2, now[3]+1):
        q.append((now[0], now[1]-2, now[2] + 1, now[3]+1))
    if check(now[0]+1, now[1]-2, now[3]+1):
        q.append((now[0]+1, now[1]-2, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]-2, now[3]+1):
        q.append((now[0]-1, now[1]-2, now[2] + 1, now[3]+1))
if not ans == 1000000000:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
# import queue
from collections import deque
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
table = []
for i in range(h):
    table.append(input())
# print(table)

def check(h_tmp, w_tmp, steps):
    if h_tmp < 0 or w_tmp < 0 or h_tmp >= h or w_tmp >= w:
        return False
    elif visit[h_tmp][w_tmp] <= steps:
        return False
    elif table[h_tmp][w_tmp] == '#':
        return False
    else:
        return True


# q = queue.Queue()
q = deque()
q.append((ch, cw, 0, 0))
ans = 1000000000
visit = [[1000000000] * w for _ in range(h)]
# print(visit)
while not len(q) == 0:
    now = q.popleft()
    visit[now[0]][now[1]] = min(visit[now[0]][now[1]], now[3])
    # print(q.qsize())
    # print(now)
    if now[0] == dh and now[1] == dw:
        # print(now[0], now[1])
        ans = visit[now[0]][now[1]]
        # ans = min(ans, now[3])
        # continue
        break
    # print(now[0], now[1])

    if check(now[0]+1, now[1], now[3]):
        q.appendleft((now[0]+1, now[1], now[2] + 1, now[3]))
    if check(now[0], now[1]+1, now[3]):
        q.appendleft((now[0], now[1]+1, now[2] + 1, now[3]))
    if check(now[0]-1, now[1], now[3]):
        q.appendleft((now[0]-1, now[1], now[2] + 1, now[3]))
    if check(now[0], now[1]-1, now[3]):
        q.appendleft((now[0], now[1]-1, now[2] + 1, now[3]))

    if check(now[0]+1, now[1]+1, now[3]+1):
        q.append((now[0]+1, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]+1, now[3]+1):
        q.append((now[0]-1, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]+1, now[1]-1, now[3]+1):
        q.append((now[0]+1, now[1]-1, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]-1, now[3]+1):
        q.append((now[0]-1, now[1]-1, now[2] + 1, now[3]+1))

    if check(now[0]+2, now[1], now[3]+1):
        q.append((now[0]+2, now[1], now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]+1, now[3]+1):
        q.append((now[0]+2, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]+2, now[3]+1):
        q.append((now[0]+2, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]-1, now[3]+1):
        q.append((now[0]+2, now[1]-1, now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]-2, now[3]+1):
        q.append((now[0]+2, now[1]-2, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1], now[3]+1):
        q.append((now[0]-2, now[1], now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]+1, now[3]+1):
        q.append((now[0]-2, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]+2, now[3]+1):
        q.append((now[0]-2, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]-1, now[3]+1):
        q.append((now[0]-2, now[1]-1, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]-2, now[3]+1):
        q.append((now[0]-2, now[1]-2, now[2] + 1, now[3]+1))

    if check(now[0], now[1]+2, now[3]+1):
        q.append((now[0], now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]+2, now[3]+1):
        q.append((now[0]-1, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]+1, now[1]+2, now[3]+1):
        q.append((now[0]+1, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0], now[1]-2, now[3]+1):
        q.append((now[0], now[1]-2, now[2] + 1, now[3]+1))
    if check(now[0]+1, now[1]-2, now[3]+1):
        q.append((now[0]+1, now[1]-2, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]-2, now[3]+1):
        q.append((now[0]-1, now[1]-2, now[2] + 1, now[3]+1))
if not ans == 1000000000:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
S=[[x=='#' for x in list(input())] for _ in range(H)]
d={(CH-1,CW-1):0}
q=deque([(CH-1,CW-1,0)])
def check(h,w,c,o):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    key=(h,w)
    if key in d:
        if d[key]<=c:
            return False
    if S[h][w]:
        return False
    if o:
        q.append((h,w,c))
        d[key]=c
    else:
        q.appendleft((h,w,c+1))
        d[key]=c+1
    return True
while q:
    h,w,c=q.pop()
    # walk
    check(h-1,w-0,c,True)
    check(h-0,w-1,c,True)
    check(h+1,w+0,c,True)
    check(h+0,w+1,c,True)
    # warp
    check(h-1,w-1,c,False)
    check(h+1,w+1,c,False)
    for i in [-2,+2]:
        for j in range(-2,3):
            check(h+i,w+j,c,False)
            check(h+j,w+i,c,False)
key=(DH-1,DW-1)
if key in d:
    print(d[key])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
# import queue
from collections import deque
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
table = []
for i in range(h):
    table.append(input())
# print(table)

def check(h_tmp, w_tmp, steps):
    if h_tmp < 0 or w_tmp < 0 or h_tmp >= h or w_tmp >= w:
        return False
    elif visit[h_tmp][w_tmp] <= steps:
        return False
    elif table[h_tmp][w_tmp] == '#':
        return False
    else:
        return True


# q = queue.Queue()
q = deque()
q.append((ch, cw, 0, 0))
ans = 1000000000
visit = [[1000000000 for _ in range(w)] for __ in range(h)]
# print(visit)
while not len(q) == 0:
    now = q.popleft()
    visit[now[0]][now[1]] = min(visit[now[0]][now[1]], now[3])
    # print(q.qsize())
    # print(now)
    if now[0] == dh and now[1] == dw:
        # print(now[0], now[1])
        ans = visit[now[0]][now[1]]
        # ans = min(ans, now[3])
        # continue
        break
    # print(now[0], now[1])

    if check(now[0]+1, now[1], now[3]):
        q.appendleft((now[0]+1, now[1], now[2] + 1, now[3]))
    if check(now[0], now[1]+1, now[3]):
        q.appendleft((now[0], now[1]+1, now[2] + 1, now[3]))
    if check(now[0]-1, now[1], now[3]):
        q.appendleft((now[0]-1, now[1], now[2] + 1, now[3]))
    if check(now[0], now[1]-1, now[3]):
        q.appendleft((now[0], now[1]-1, now[2] + 1, now[3]))

    if check(now[0]+1, now[1]+1, now[3]+1):
        q.append((now[0]+1, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]+1, now[3]+1):
        q.append((now[0]-1, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]+1, now[1]-1, now[3]+1):
        q.append((now[0]+1, now[1]-1, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]-1, now[3]+1):
        q.append((now[0]-1, now[1]-1, now[2] + 1, now[3]+1))

    if check(now[0]+2, now[1], now[3]+1):
        q.append((now[0]+2, now[1], now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]+1, now[3]+1):
        q.append((now[0]+2, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]+2, now[3]+1):
        q.append((now[0]+2, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]-1, now[3]+1):
        q.append((now[0]+2, now[1]-1, now[2] + 1, now[3]+1))
    if check(now[0]+2, now[1]-2, now[3]+1):
        q.append((now[0]+2, now[1]-2, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1], now[3]+1):
        q.append((now[0]-2, now[1], now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]+1, now[3]+1):
        q.append((now[0]-2, now[1]+1, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]+2, now[3]+1):
        q.append((now[0]-2, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]-1, now[3]+1):
        q.append((now[0]-2, now[1]-1, now[2] + 1, now[3]+1))
    if check(now[0]-2, now[1]-2, now[3]+1):
        q.append((now[0]-2, now[1]-2, now[2] + 1, now[3]+1))

    if check(now[0], now[1]+2, now[3]+1):
        q.append((now[0], now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]+2, now[3]+1):
        q.append((now[0]-1, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0]+1, now[1]+2, now[3]+1):
        q.append((now[0]+1, now[1]+2, now[2] + 1, now[3]+1))
    if check(now[0], now[1]-2, now[3]+1):
        q.append((now[0], now[1]-2, now[2] + 1, now[3]+1))
    if check(now[0]+1, now[1]-2, now[3]+1):
        q.append((now[0]+1, now[1]-2, now[2] + 1, now[3]+1))
    if check(now[0]-1, now[1]-2, now[3]+1):
        q.append((now[0]-1, now[1]-2, now[2] + 1, now[3]+1))
if not ans == 1000000000:
    print(ans)
else:
    print(-1)