Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

1

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

Note that he cannot walk diagonally.

Sample Input 2

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

Sample Output 2

-1

He cannot move from there.

Sample Input 3

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

Sample Output 3

0

No use of magic is needed.

Sample Input 4

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

Sample Output 4

2



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


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh, Dw = map(int, input().split())
Dh -= 1
Dw -= 1
S = [list(input()) for i in range(H)]
S[Ch][Cw] = "#"

ans = 0
warp_after = [[Ch, Cw]]
warp_before = []
queue1 = [[1,0],[-1,0],[0,1],[0,-1]]
queue2 = [
        [-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]
    ]

def nowRange(now):
    r = []
    for i in queue1:
        j = now[0] + i[0]
        k = now[1] + i[1]
        if H > j >= 0 and W > k >= 0:
            if S[j][k] == "#":
                pass
            elif j == Dh and k == Dw:
                print(ans)
                exit()
            elif S[j][k] == ".":
                S[j][k] = "#"
                r = r + [[j,k]]
    return r


def stepRange(trout):
    r = []
    for i in trout:
        r = r + nowRange(i)
    if len(r) == 0:
        return []
    else:
        return r + stepRange(r)


def nowWarp(now):
    r = []
    for i in queue2:
        j = now[0] + i[0]
        k = now[1] + i[1]
        if H > j >= 0 and W > k >= 0:
            if S[j][k] == "#":
                pass
            elif j == Dh and k == Dw:
                print(ans)
                exit()
            elif S[j][k] == ".":
                S[j][k] = "#"
                r = r + [[j,k]]
            
    return r


def warpRange(trout):
    r = []
    for i in trout:
        r = r + nowWarp(i)
    if len(r) == 0:
        print(-1)
        exit()
    else:
        return r


while True:
    warp_before = stepRange(warp_after) + warp_after
    ans += 1
    warp_after = warpRange(warp_before)

Submission status: Time Limit Exceeded

Solution code:
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 = [list(input()) for i in range(H)]
S[Ch][Cw] = "#"

ans = 0
warp_after = [[Ch, Cw]]
warp_before = []

def nowRange(now):
    queue = [[1,0],[-1,0],[0,1],[0,-1]]
    r = []
    for i in queue:
        j = now[0] + i[0]
        k = now[1] + i[1]
        if H > j >= 0 and W > k >= 0:
            if S[j][k] == "#":
                pass
            elif j == Dh and k == Dw:
                print(ans)
                exit()
            elif S[j][k] == ".":
                S[j][k] = "#"
                r = r + [[j,k]]
    return r


def stepRange(trout):
    r = []
    for i in trout:
        r = r + nowRange(i)
    if len(r) == 0:
        return []
    else:
        return r + stepRange(r)


def nowWarp(now):
    queue = [
        [-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]
    ]
    r = []
    for i in queue:
        j = now[0] + i[0]
        k = now[1] + i[1]
        if H > j >= 0 and W > k >= 0:
            if S[j][k] == "#":
                pass
            elif j == Dh and k == Dw:
                print(ans)
                exit()
            elif S[j][k] == ".":
                S[j][k] = "#"
                r = r + [[j,k]]
            
    return r


def warpRange(trout):
    r = []
    for i in trout:
        r = r + nowWarp(i)
    if len(r) == 0:
        print(-1)
        exit()
    else:
        return r


while True:
    warp_before = stepRange(warp_after) + warp_after
    ans += 1
    warp_after = warpRange(warp_before)

Submission status: Time Limit Exceeded

Solution code:
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 = [list(input()) for i in range(H)]
S[Ch][Cw] = "#"

ans = 0
warp_after = [[Ch, Cw]]
warp_before = []

def nowRange(now):
    queue = [[1,0],[-1,0],[0,1],[0,-1]]
    r = []
    for i in queue:
        j = now[0]+i[0]
        k = now[1]+i[1]
        if j >= 0 and j < H and k >= 0 and k < W:
            if j == Dh and k == Dw:
                print(ans)
                exit()
            elif S[j][k] == ".":
                S[j][k] = "#"
                r = r + [[j,k]]
    return r


def stepRange(trout):
    r = []
    for i in trout:
        r = r + nowRange(i)
    if len(r) == 0:
        return []
    else:
        return r + stepRange(r)


def nowWarp(now):
    queue = [
        [-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]
    ]
    r = []
    for i in queue:
        j = now[0]+i[0]
        k = now[1]+i[1]
        if j >= 0 and j < H and k >= 0 and k < W:
            if j == Dh and k == Dw:
                print(ans)
                exit()
            elif S[j][k] == ".":
                S[j][k] = "#"
                r = r + [[j,k]]
    return r


def warpRange(trout):
    r = []
    for i in trout:
        r = r + nowWarp(i)
    if len(r) == 0:
        print(-1)
        exit()
    else:
        return r


while True:
    warp_before = stepRange(warp_after) + warp_after
    ans += 1
    warp_after = warpRange(warp_before)

Submission status: Time Limit Exceeded

Solution code:
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 = [list(input()) for i in range(H)]
S[Ch][Cw] = "#"

ans = 0
warp_after = [[Ch, Cw]]
warp_before = []

def nowRange(now):
    queue = [[1,0],[-1,0],[0,1],[0,-1]]
    r = []
    for i in queue:
        j = now[0]+i[0]
        k = now[1]+i[1]
        if j >= 0 and j < H and k >= 0 and k < W:
            if j == Dh and k == Dw:
                print(ans)
                exit()
            elif S[j][k] == ".":
                S[j][k] = "#"
                r = r + [[j,k]]
    return r


def stepRange(trout):
    r = []
    for i in trout:
        r = r + nowRange(i)
    if len(r) == 0:
        return []
    else:
        return r + stepRange(r)


def nowWarp(now):
    queue = [
        [-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]
    ]
    r = []
    for i in queue:
        j = now[0]+i[0]
        k = now[1]+i[1]
        if j >= 0 and j < H and k >= 0 and k < W:
            if j == Dh and k == Dw:
                print(ans)
                exit()
            elif S[j][k] == ".":
                S[j][k] = "#"
                r = r + [[j,k]]
    return r


def warpRange(trout):
    r = []
    for i in trout:
        r = r + nowWarp(i)
    if len(r) == 0:
        print(-1)
        exit()
    else:
        return r


flag = True
while flag:
    warp_before = stepRange(warp_after) + warp_after
    ans += 1
    warp_after = warpRange(warp_before)
    if len(warp_after) == 0:
        flag = False
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq

H, W = map(int, input().split())
sy, sx = map(lambda x: int(x) - 1, input().split())
ty, tx = map(lambda x: int(x) - 1, input().split())
s, t = sy * W + sx, ty * W + tx
graph = [input() for _ in range(H)]

INF = 1 << 30
dist = np.full(H * W, INF, np.int64)
que = []

def push(v, d):
    if(dist[v] <= d):
        return
    dist[v] = d
    heapq.heappush(que, (d, v))

def move(ny, nx, d):
    if ny < 0 or ny >= H or nx < 0 or nx >= W:
        return
    if graph[ny][nx] == '.':
        push(ny * W + nx, d)

push(s, 0)

while que:
    d, v = heapq.heappop(que)
    if d > dist[v]:
        continue
    if v == t:
        break
    y, x = divmod(v, W)
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            move(y + dy, x + dx, d + (abs(dy) + abs(dx) > 1))

if dist[t] == INF:
    print(-1)
else:
    print(dist[t])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify,heappush,heappop

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 i in range(H)]
cnt = [[10**10 for i in range(W)] for j in range(H)]

task_list = []
heapify(task_list)
heappush(task_list,[0,sx,sy])
S[sy][sx]="."

for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            cnt[i][j]=-1

count = 0
while len(task_list)>0:
    t,x,y = heappop(task_list)
    if x==gx and y==gy:
        print(t)
        exit()
    
    if x<0 or W<=x or y<0 or H<=y:
        continue

    if S[y][x] != ".":
        continue

    S[y][x]=str(t)#確定最低値
    cnt[y][x]=t#暫定最低値

    for i in range(-2,3):
        for j in range(-2,3):
            if abs(i)+abs(j) < 2:
                if not(x+i<0 or W<=x+i or y+j<0 or H<=y+j):
                    if S[y+j][x+i]=="." and cnt[y+j][x+i] > t:
                        heappush(task_list,[t,x+i,y+j])
                        cnt[y+j][x+i]=t
            if not(x+i<0 or W<=x+i or y+j<0 or H<=y+j):
                if S[y+j][x+i]=="." and cnt[y+j][x+i] > t+1:
                    heappush(task_list,[t+1,x+i,y+j])
                    cnt[y+j][x+i]=t+1

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify,heappush,heappop

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 i in range(H)]
cnt = [[10**10 for i in range(W)] for j in range(H)]

task_list = []
heapify(task_list)
heappush(task_list,[0,sx,sy])
S[sy][sx]="."

for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            cnt[i][j]=-1

count = 0
while len(task_list)>0:
    count +=1
    t,x,y = heappop(task_list)
    if x==gx and y==gy:
        print(t)
        exit()
    
    if x<0 or W<=x or y<0 or H<=y:
        continue

    if S[y][x] != ".":
        continue

    S[y][x]=str(t)#確定最低値
    cnt[y][x]=t#暫定最低値

    for i in range(-2,3):
        for j in range(-2,3):
            if abs(i)+abs(j) < 2:
                if not(x+i<0 or W<=x+i or y+j<0 or H<=y+j):
                    if S[y+j][x+i]=="." and cnt[y+j][x+i] > t:
                        heappush(task_list,[t,x+i,y+j])
                        cnt[y+j][x+i]=t+1
            if not(x+i<0 or W<=x+i or y+j<0 or H<=y+j):
                if S[y+j][x+i]=="." and cnt[y+j][x+i] > t+1:
                    heappush(task_list,[t+1,x+i,y+j])
                    cnt[y+j][x+i]=t+1

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify,heappush,heappop

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 i in range(H)]
cnt = [[10**10 for i in range(W)] for j in range(H)]

task_list = []
heapify(task_list)
heappush(task_list,[0,sx,sy])
S[sy][sx]="."

count = 0
while len(task_list)>0:
    count +=1
    t,x,y = heappop(task_list)
    if x==gx and y==gy:
        print(t)
        exit()
    
    if x<0 or W<=x or y<0 or H<=y:
        continue

    if S[y][x] != ".":
        continue

    S[y][x]=str(t)#確定最低値
    cnt[y][x]=t#暫定最低値

    for i in range(-2,3):
        for j in range(-2,3):
            if abs(i)+abs(j) < 2:
                if not(x+i<0 or W<=x+i or y+j<0 or H<=y+j):
                    if S[y+j][x+i]=="." and cnt[y+j][x+i] > t:
                        heappush(task_list,[t,x+i,y+j])
                        cnt[y+j][x+i]=t+1
            if not(x+i<0 or W<=x+i or y+j<0 or H<=y+j):
                if S[y+j][x+i]=="." and cnt[y+j][x+i] > t+1:
                    heappush(task_list,[t+1,x+i,y+j])
                    cnt[y+j][x+i]=t+1

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify,heappush,heappop

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 i in range(H)]
cnt = [[10**10 for i in range(W)] for j in range(H)]

task_list = []
heapify(task_list)
heappush(task_list,[0,sx,sy])
S[sy][sx]="."

while len(task_list)>0:
    t,x,y = heappop(task_list)
    if x==gx and y==gy:
        print(t)
        exit()
    
    if x<0 or W<=x or y<0 or H<=y:
        continue

    if S[y][x] != ".":
        continue

    S[y][x]=str(t)#確定最低値
    cnt[y][x]=t#暫定最低値
    heappush(task_list,[t,x+1,y])
    heappush(task_list,[t,x-1,y])
    heappush(task_list,[t,x,y+1])
    heappush(task_list,[t,x,y-1])
    for i in range(-2,3):
        for j in range(-2,3):
            if abs(i)+abs(j) < 2:
                continue
            if not(x+i<0 or W<=x+i or y+j<0 or H<=y+j):
                if S[y+j][x+i]=="." and cnt[y+j][x+i] > t+1:
                    heappush(task_list,[t+1,x+i,y+j])
                    cnt[y+j][x+i]=t+1

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify,heappush,heappop

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 i in range(H)]
cnt = [[10**10 for i in range(W)] for j in range(H)]

task_list = []
heapify(task_list)
heappush(task_list,[0,sx,sy])
S[sy][sx]="."

while len(task_list)>0:
    t,x,y = heappop(task_list)
    if x==gx and y==gy:
        print(t)
        exit()
    
    if x<0 or W<=x or y<0 or H<=y:
        continue

    if S[y][x] != ".":
        continue

    S[y][x]=str(t)#確定最低値
    cnt[y][x]=t#暫定最低値
    heappush(task_list,[t,x+1,y])
    heappush(task_list,[t,x-1,y])
    heappush(task_list,[t,x,y+1])
    heappush(task_list,[t,x,y-1])
    for i in range(-2,3):
        for j in range(-2,3):
            if abs(i)+abs(j) < 2:
                continue
            if x+i<0 or W<=x+i or y+j<0 or H<=y+j:
                continue
            if S[y+j][x+i]=="." and cnt[y+j][x+i]:
                heappush(task_list,[t+1,x+i,y+j])
                cnt[y+j][x+i]=t+1

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify,heappush,heappop

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 i in range(H)]

task_list = []
heapify(task_list)
heappush(task_list,[0,sx,sy])
S[sy][sx]="."

while len(task_list)>0:
    t,x,y = heappop(task_list)
    if x==gx and y==gy:
        print(t)
        exit()
    
    if x<0 or W<=x or y<0 or H<=y:
        continue

    if S[y][x] != ".":
        continue

    S[y][x]=str(t)
    heappush(task_list,[t,x+1,y])
    heappush(task_list,[t,x-1,y])
    heappush(task_list,[t,x,y+1])
    heappush(task_list,[t,x,y-1])
    for i in range(-2,3):
        for j in range(-2,3):
            if abs(i)+abs(j) < 2:
                continue
            if x+i<0 or W<=x+i or y+j<0 or H<=y+j:
                continue
            if S[y+j][x+i]==".":
                heappush(task_list,[t+1,x+i,y+j])

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify,heappush,heappop

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 i in range(H)]

task_list = []
heapify(task_list)
heappush(task_list,[0,sx,sy])
S[sy][sx]="."

while len(task_list)>0:
    t,x,y = heappop(task_list)
    if x==gx and y==gy:
        print(t)
        exit()
    
    if x<0 or W<=x or y<0 or H<=y:
        continue

    if S[y][x] != ".":
        continue

    S[y][x]=str(t)
    heappush(task_list,[t,x+1,y])
    heappush(task_list,[t,x-1,y])
    heappush(task_list,[t,x,y+1])
    heappush(task_list,[t,x,y-1])
    for i in range(-2,3):
        for j in range(-2,3):
            if abs(i)+abs(j) < 2:
                continue
            heappush(task_list,[t+1,x+i,y+j])

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import pprint
h,w = map(int,input().split())
sh,sw = map(int,input().split())
gh,gw = map(int,input().split())
C = [list(input()) for _ in range(h)]
dist = [[-1] * w for _ in range(h)] 
sh-=1
sw-=1
gh-=1
gw-=1

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, 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]]

def solve(s_pos):
    queue = []
    queue.append(s_pos)
    dist[s_pos[0]][s_pos[1]] = 0

    candidates = []
    while len(queue) > 0:
        y, x = queue.pop(0)
        candidates.append([y,x])
        for p, q in move:
            vh = y + p
            vw = x + q
            if 0 <= vh < h and 0 <= vw < w:
                if C[vh][vw] != "#" and dist[vh][vw] == -1:
                    dist[vh][vw] = dist[y][x]
                    queue.append([vh,vw])
        if len(queue) == 0:
            while len(candidates) > 0:
                y2, x2 = candidates.pop(0)
                for r, s in magic:
                    vh2 = y2 + r
                    vw2 = x2 + s
                    if 0 <= vh2 < h and 0 <= vw2 < w:
                        nd = dist[y2][x2] + 1
                        if C[vh2][vw2] != "#" and dist[vh2][vw2] == -1:
                            dist[vh2][vw2] = nd
                            queue.append([vh2, vw2])

solve([sh,sw])
print(dist[gh][gw])

Submission status: Time Limit Exceeded

Solution code:
import sys
import pprint
h,w = map(int,input().split())
sh,sw = map(int,input().split())
gh,gw = map(int,input().split())
C = [list(input()) for _ in range(h)]
dist = [[-1] * w for _ in range(h)] 
sh-=1
sw-=1
gh-=1
gw-=1

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, 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]]

def solve(s_pos):
    queue = []
    queue.append(s_pos)
    dist[s_pos[0]][s_pos[1]] = 0
    
    candidates = []
    while len(queue) > 0:
        y, x = queue.pop(0)
        candidates.append([y,x])
        for p, q in move:
            vh = y + p
            vw = x + q
            if 0 <= vh < h and 0 <= vw < w:
                if C[vh][vw] != "#" and dist[vh][vw] == -1:
                    dist[vh][vw] = dist[y][x]
                    queue.append([vh,vw])
        if len(queue) == 0:
            while len(candidates) > 0:
                y2, x2 = candidates.pop(0)
                for r, s in magic:
                    vh2 = y2 + r
                    vw2 = x2 + s
                    if 0 <= vh2 < h and 0 <= vw2 < w:
                        if C[vh2][vw2] != "#" and dist[vh2][vw2] == -1:
                            dist[vh2][vw2] = dist[y2][x2] + 1
                            queue.append([vh2, vw2])

solve([sh,sw])
print(dist[gh][gw])

Submission status: Time Limit Exceeded

Solution code:
import sys

INF = 10 ** 18
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict


def li():
    return [int(x) for x in input().split()]


from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

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


def bfs():
    costmap = defaultdict(lambda: -1)
    costmap[Cw, Ch] = 0
    que = deque([])
    que.append((Cw, Ch))

    while que:
        # print(que)
        # 左から取り出す
        x, y = que.popleft()
        # 通常移動パターン
        for i in range(len(v)):
            nx = x + v[i][0]
            ny = y + v[i][1]
            # バリデーション
            if nx <= 0 or nx > W or ny <= 0 or ny > H:
                continue
            if S[ny - 1][nx - 1] != '.':
                continue
            # 初探索 or コストが下がる場合
            if costmap[nx, ny] == -1 or costmap[x, y] < costmap[nx, ny]:
                # コストゼロは左から
                que.appendleft((nx, ny))
                costmap[nx, ny] = costmap[x, y]
        # 特殊移動パターン
        for i in range(x - 2, x + 3):
            for j in range(y - 2, y + 3):
                nx, ny = i, j
                # バリデーション
                if nx <= 0 or nx > W or ny <= 0 or ny > H:
                    continue
                if S[ny - 1][nx - 1] != '.':
                    continue
                # 初探索 or コストが下がる場合
                if costmap[nx, ny] == -1 or costmap[x, y] + 1 < costmap[nx, ny]:
                    # コスト1は右から
                    que.append((nx, ny))
                    costmap[nx, ny] = costmap[x, y] + 1
    return costmap


costmap = bfs()
# print(costmap)
print(costmap[Dw, Dh])

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())
S = [list(input()) for x in range(H)]

dx=[1,0,-1,0]
dy=[0,1,0,-1]

def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch-1][Cw-1] = 0
    que = deque([])
    que.append((Cw, Ch))

    while que:
        x, y = que.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 < nx <= W and 0 < ny <= H and S[ny - 1][nx - 1] == '.' and (costmap[ny - 1][nx - 1] == -1 or costmap[y - 1][x - 1] < costmap[ny - 1][nx - 1]):
                que.appendleft((nx, ny))
                costmap[ny-1][nx-1] = costmap[y-1][x-1]
        for i in range(x-2, x+3):
            for j in range(y-2, y+3):
                nx, ny = i, j
                if 0 < nx <= W and 0 < ny <= H and S[ny - 1][nx - 1] == '.' and (costmap[ny - 1][nx - 1] == -1 or costmap[y - 1][x - 1] < costmap[ny - 1][nx - 1]):
                    que.append((nx, ny))
                    costmap[ny-1][nx-1] = costmap[y-1][x-1] + 1
    return costmap

costmap = bfs()
print(costmap[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
INF = 10**18
def li():
    return [int(x) for x in input().split()]
from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

dx=[1,0,-1,0]
dy=[0,1,0,-1]

def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch-1][Cw-1] = 0
    que = deque([])
    que.append((Cw, Ch))

    while que:
        x, y = que.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 < nx <= W and 0 < ny <= H and S[ny - 1][nx - 1] == '.' and (costmap[ny - 1][nx - 1] == -1 or costmap[y - 1][x - 1] < costmap[ny - 1][nx - 1]):
                que.appendleft((nx, ny))
                costmap[ny-1][nx-1] = costmap[y-1][x-1]
        for i in range(x-2, x+3):
            for j in range(y-2, y+3):
                nx, ny = i, j
                if 0 < nx <= W and 0 < ny <= H and S[ny - 1][nx - 1] == '.' and (costmap[ny - 1][nx - 1] == -1 or costmap[y - 1][x - 1] < costmap[ny - 1][nx - 1]):
                    que.append((nx, ny))
                    costmap[ny-1][nx-1] = costmap[y-1][x-1] + 1
    return costmap

costmap = bfs()
print(costmap[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
INF = 10**18
def li():
    return [int(x) for x in input().split()]
from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

dx=[1,0,-1,0]
dy=[0,1,0,-1]

def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch-1][Cw-1] = 0
    que = deque([])
    que.append((Cw, Ch))

    while que:
        # print(que)
        # 左から取り出す
        x, y = que.popleft()
        # 通常移動パターン
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # バリデーション、初探索 or コストが下がる場合
            if 0 < nx <= W and 0 < ny <= H and S[ny - 1][nx - 1] == '.' and (costmap[ny - 1][nx - 1] == -1 or costmap[y - 1][x - 1] < costmap[ny - 1][nx - 1]):
                # コストゼロは左から
                que.appendleft((nx, ny))
                costmap[ny-1][nx-1] = costmap[y-1][x-1]
        # 特殊移動パターン
        for i in range(x-2, x+3):
            for j in range(y-2, y+3):
                nx, ny = i, j
                # バリデーション、初探索 or コストが下がる場合
                if 0 < nx <= W and 0 < ny <= H and S[ny - 1][nx - 1] == '.' and (costmap[ny - 1][nx - 1] == -1 or costmap[y - 1][x - 1] < costmap[ny - 1][nx - 1]):
                    # コスト1は右から
                    que.append((nx, ny))
                    costmap[ny-1][nx-1] = costmap[y-1][x-1] + 1
    return costmap

costmap = bfs()
# print(costmap)
print(costmap[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 10**18
sys.setrecursionlimit(10**6)
from collections import defaultdict
def li():
    return [int(x) for x in input().split()]
from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

dx=[1,0,-1,0]
dy=[0,1,0,-1]

def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch-1][Cw-1] = 0
    que = deque([])
    que.append((Cw, Ch))

    while que:
        # print(que)
        # 左から取り出す
        x, y = que.popleft()
        # 通常移動パターン
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # バリデーション、初探索 or コストが下がる場合
            if 0 < nx <= W and 0 < ny <= H and S[ny - 1][nx - 1] == '.' and (costmap[ny - 1][nx - 1] == -1 or costmap[y - 1][x - 1] < costmap[ny - 1][nx - 1]):
                # コストゼロは左から
                que.appendleft((nx, ny))
                costmap[ny-1][nx-1] = costmap[y-1][x-1]
        # 特殊移動パターン
        for i in range(x-2, x+3):
            for j in range(y-2, y+3):
                nx, ny = i, j
                # バリデーション、初探索 or コストが下がる場合
                if 0 < nx <= W and 0 < ny <= H and S[ny - 1][nx - 1] == '.' and (costmap[ny - 1][nx - 1] == -1 or costmap[y - 1][x - 1] < costmap[ny - 1][nx - 1]):
                    # コスト1は右から
                    que.append((nx, ny))
                    costmap[ny-1][nx-1] = costmap[y-1][x-1] + 1
    return costmap

costmap = bfs()
# print(costmap)
print(costmap[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 10**18
sys.setrecursionlimit(10**6)
from collections import defaultdict
def li():
    return [int(x) for x in input().split()]
from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

dx=[1,0,-1,0]
dy=[0,1,0,-1]

def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch-1][Cw-1] = 0
    que = deque([])
    que.append((Cw, Ch))

    while que:
        # print(que)
        # 左から取り出す
        x, y = que.popleft()
        # 通常移動パターン
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # バリデーション
            if nx <= 0 or nx > W or ny <= 0 or ny > H:
                continue
            if S[ny-1][nx-1] != '.':
                continue
            # 初探索 or コストが下がる場合
            if costmap[ny-1][nx-1] == -1 or costmap[y-1][x-1] < costmap[ny-1][nx-1]:
                # コストゼロは左から
                que.appendleft((nx, ny))
                costmap[ny-1][nx-1] = costmap[y-1][x-1]
        # 特殊移動パターン
        for i in range(x-2, x+3):
            for j in range(y-2, y+3):
                nx, ny = i, j
                # バリデーション
                if nx <= 0 or nx > W or ny <= 0 or ny > H:
                    continue
                if S[ny-1][nx-1] != '.':
                    continue
                # 初探索 or コストが下がる場合
                if costmap[ny-1][nx-1] == -1 or costmap[y-1][x-1] < costmap[ny-1][nx-1]:
                    # コスト1は右から
                    que.append((nx, ny))
                    costmap[ny-1][nx-1] = costmap[y-1][x-1] + 1
    return costmap

costmap = bfs()
# print(costmap)
print(costmap[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 10**18
sys.setrecursionlimit(10**6)
from collections import defaultdict
def li():
    return [int(x) for x in input().split()]
from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

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

def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch-1][Cw-1] = 0
    que = deque([])
    que.append((Cw, Ch))

    while que:
        # print(que)
        # 左から取り出す
        x, y = que.popleft()
        # 通常移動パターン
        for i in range(len(v)):
            nx = x + v[i][0]
            ny = y + v[i][1]
            # バリデーション
            if nx <= 0 or nx > W or ny <= 0 or ny > H:
                continue
            if S[ny-1][nx-1] != '.':
                continue
            # 初探索 or コストが下がる場合
            if costmap[ny-1][nx-1] == -1 or costmap[y-1][x-1] < costmap[ny-1][nx-1]:
                # コストゼロは左から
                que.appendleft((nx, ny))
                costmap[ny-1][nx-1] = costmap[y-1][x-1]
        # 特殊移動パターン
        for i in range(x-2, x+3):
            for j in range(y-2, y+3):
                nx, ny = i, j
                # バリデーション
                if nx <= 0 or nx > W or ny <= 0 or ny > H:
                    continue
                if S[ny-1][nx-1] != '.':
                    continue
                # 初探索 or コストが下がる場合
                if costmap[ny-1][nx-1] == -1 or costmap[y-1][x-1] < costmap[ny-1][nx-1]:
                    # コスト1は右から
                    que.append((nx, ny))
                    costmap[ny-1][nx-1] = costmap[y-1][x-1] + 1
    return costmap

costmap = bfs()
# print(costmap)
print(costmap[Dh-1][Dw-1])