Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

1

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

Note that he cannot walk diagonally.

Sample Input 2

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

Sample Output 2

-1

He cannot move from there.

Sample Input 3

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

Sample Output 3

0

No use of magic is needed.

Sample Input 4

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

Sample Output 4

2



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


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import collections
def bfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    q2 = collections.deque()
    q2.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dx2 = [(-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 len(q) != 0 and len(q2) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == ".":
                    if dist[h2][w2] == -1:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                        q2.append((h2, w2))
                    elif d < dist[h2][w2]:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                        q2.append((h2, w2))
        h, w = q2.popleft()
        d = dist[h][w]
        for x, y in dx2:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == "." and (dist[h2][w2] == -1 or d + 1 < dist[h2][w2]):
                    dist[h2][w2] = d + 1
                    q.append((h2, w2))
                    q2.append((h2, w2))
    return dist[gy][gx]

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
grid = [input() for _ in range(H)]
print(bfs(Ch-1, Cw-1, Dh-1, Dw-1))

Submission status: Time Limit Exceeded

Solution code:
import heapq
INF = 10 ** 9

H, W = map(int, input().split())
Ch, Cw = map(lambda x:int(x)-1, input().split())
Dh, Dw = map(lambda x:int(x)-1, input().split())
S = [list(map(lambda x: INF if x == "." else -1, [c for c in input()])) for _ in range(H)]


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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
H, W = map(int, input().split())
sh, sw = map(int, input().split())
sh -= 1
sw -= 1
gh, gw = map(int, input().split())
gh -= 1
gw -= 1

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

d = deque()
kabe = deque()
d.append([sh, sw])
looked = [[0 for i in range(W)]for j in range(H)]
looked[sh][sw] = 1
ans = 0
dx_dy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
kabe.append([sh, sw])
while d:
    x = d.pop()
    lookx = x[0]
    looky = x[1]
    for i in dx_dy:
        a = lookx+i[0]
        b = looky+i[1]
        if not(0 <= a < H) or not(0 <= b < W) or looked[a][b] == 1:
            continue
        if C[a][b] == "#":
            kabe.append([lookx, looky])
            continue
        if a == gh and b == gw:
            print(ans)
            sys.exit()
        d.append([a, b])
        looked[a][b] = 1

    if len(d) == 0:
        ans += 1
        ok = 0
        for _ in range(len(kabe)):
            kx, ky = kabe.pop()
            wapuxm = max(kx-2, 0)
            wapuxM = min(kx+2, H-1)
            wapuym = max(ky-2, 0)
            wapuyM = min(ky+2, W-1)
            for ki in range(wapuxm, wapuxM+1):
                for kj in range(wapuym, wapuyM+1):
                    if C[ki][kj] == "#" or looked[ki][kj] == 1:
                        continue
                    if C[ki][kj] == ".":
                        d.append([ki, kj])
                        looked[ki][kj] = 1
                        ok = 1
                    if ki == gh and kj == gw:
                        print(ans)
                        sys.exit()
        if ok == 0:
            print(-1)
            sys.exit()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import numpy as np
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [input() for _ in range(H)]


move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[-1] * W for _ in range(H)]


def bfs(i, j, d):
    visited[i][j] = d
    que = deque([(i, j, d)])

    while que:
        ci, cj, d = que.popleft()

        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj] != -1:
                continue
            if S[ni][nj] == '.':
                visited[ni][nj] = d
                que.append((ni, nj, d))


d = 0
for i in range(H):
    for j in range(W):
        if visited[i][j] == -1 and S[i][j] == '.':
            visited[i][j] = d
            bfs(i, j, d)
            d += 1

# print(visited)

G = [[] for _ in range(d+1)]
for ci in range(H):
    for cj in range(W):
        for di in range(-2, 3):
            for dj in range(-2, 3):
                ni, nj = ci+di, cj+dj
                if not (0 <= ni < H and 0 <= nj < W)  \
                        or visited[ci][cj] == -1 or visited[ni][nj] == -1:
                    continue
                if visited[ci][cj] != visited[ni][nj]:
                    u = visited[ci][cj]
                    v = visited[ni][nj]
                    G[u].append(v)
                    G[v].append(u)
startd = visited[Ch-1][Cw-1]
goald = visited[Dh-1][Dw-1]


def dijkstra(start):
    INF = 10 ** 15
    dist = [INF] * 10**7
    dist[start] = 0
    q = [(0, start)]
    while q:
        d, v = heappop(q)
        if dist[v] < d:
            continue
        for w in G[v]:
            d1 = d+1
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1, w))
    return dist


d1 = np.array(dijkstra(startd))
# print(d1)
if d1[goald] == 10**15:
    print(-1)
else:
    print(d1[goald])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
import itertools
import sys

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
M = [input() for _ in range(H)]

seen = np.array([[0]*W for _ in range(H)])
que = deque()
que.append((Ch - 1, Cw - 1))

def DFS(que):
    while que:
        X, Y = que.popleft()
        seen[X][Y] = 1
        D = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        for dx, dy in D:
            if 0<= X + dx < H and 0 <= Y + dy < W:
                if M[X + dx][Y + dy] == "." and seen[X + dx][Y + dy] == 0:
                    que.append((X + dx, Y + dy))

ans = 0 
while que:
    x, y = que[-1]
    DFS(que)
    if seen[Dh-1][Dw-1]!=0:
        print(ans)
        sys.exit()
    add = []
    for i in range(H):
        for j in range(W):
            if seen[i][j]==1:
                seen[i][j]=2
#                 for dx in range(-2, 3):
#                     for dy in range(-2, 3):
                for dx, dy in itertools.permutations(range(-2, 3), 2):
                    if 0<= i + dx < H and 0 <= j + dy < W:
                        if M[i+dx][j+dy] == '.' and seen[i+dx][j+dy] == 0 and (i+dx, j+dy) not in que : 
                            que.append((i+dx, j+dy))
    ans += 1
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def resolve():
    H,W = map(int,input().split())
    Sy,Sx = [int(i)-1 for i in input().split()]
    Gy,Gx = [int(i)-1 for i in input().split()]

    MP = [input() for i in range(H)]
    q =[]
    score=[[10**10]*W  for i in range(H)]
    score[Sy][Sx] = 0
    heapq.heappush(q,(0,Sx,Sy))
    visited = [[False for j in range(W)] for i in range(H)]

    while q:
        cs,x,y = heapq.heappop(q) 

        if visited[y][x]:
            continue
        visited[y][x]=True


        if y!=0 and MP[y-1][x]=='.' and score[y][x]<score[y-1][x]:

            score[y-1][x]=score[y][x]
            heapq.heappush(q,(cs,x,y-1))
        if y!=H-1 and MP[y+1][x]=='.' and score[y][x]<score[y+1][x]:


            score[y+1][x]=score[y][x]
            heapq.heappush(q,(cs,x,y+1))
  
        if x!=0 and MP[y][x-1]=='.' and score[y][x]<score[y][x-1]:

            score[y][x-1]=score[y][x]
            heapq.heappush(q,(cs,x-1,y))
        if x!=W-1 and MP[y][x+1]=='.' and score[y][x]<score[y][x+1]:

            score[y][x+1]=score[y][x]
            heapq.heappush(q,(cs,x+1,y))


        for i in range(max(0,y-2),min(H,y+3)):
            for j in range(max(0,x-2),min(W,x+3)):

                if MP[i][j]=='#':
                    continue
                if score[i][j]>score[y][x]+1:
                    score[i][j]=score[y][x]+1
                    heapq.heappush(q,(cs+1,j,i))

    if score[Gy][Gx]==10**10:
        print(-1)
    else:
        print(score[Gy][Gx])
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
from heapq import _heapify_max, _heappop_max
import heapq

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)

"""
method:
    heapify(x): ヒープに変換
    heappush(heap, item): itemをheapにpush
    heappop(heap): heapから最小値を取得 空の場合はIndexError
note:
    max heapにする場合は、prefix: _ とsuffix: _maxをつければ良い
"""

def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    inf = 10**7
    dp = [[inf]*w for _ in range(h)]
    s = [input() for _ in range(h)]
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    dxy = list(zip(dx, dy))
    
    rx = (2, 1, 0, -1, -2)
    ry = (2, 1, 0, -1, -2)
    
    dp[ch-1][cw-1] = 0
    
    q = []
    heappush(q, (0, ch-1, cw-1))

    while q:
        cnt = 0
        cost, px, py = heappop(q)
        if dp[px][py] < cost:
            continue
        for xi, yj in dxy:
            x = px + xi
            y = py + yj
            if x >= h or x < 0 or y >= w or y < 0 or s[x][y] == "#":
                continue
            cnt += 1
            if dp[x][y] > cost:
                dp[x][y] = cost
                heappush(q, (cost, x, y))
        
                
        if cnt != 4:
            cost += 1
            for di in rx:
                x = px + di
                if x >= h or x < 0:
                    continue
                sx = s[x]
                dpx = dp[x]
                for dj in ry:
                    y = py + dj
                    if y >= w or y < 0 or sx[y] == "#":
                        continue
                    if dpx[y] > cost:
                        dpx[y] = cost
                        heappush(q, (cost, x, y))
    if dp[dh-1][dw-1] == inf:
        print(-1)
    else:
        print(dp[dh-1][dw-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
S = [list(input()) for i in range(H)]
 
from collections import deque
 
q = deque([(CH-1, CW-1)])
 
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
warp = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            S[i][j] = 10**7
S[CH-1][CW-1] = 0

while q:
    h, w = q.popleft()
    for dh, dw in directions:
        if 0 <= h+dh < H and 0 <= w+dw < W and S[h+dh][w+dw] != "#":
            if S[h+dh][w+dw] > S[h][w]:
                S[h+dh][w+dw] = S[h][w]
                q.append((h+dh, w+dw))
    for wh, ww in warp:
        if 0 <= h+wh < H and 0 <= w+ww < W and S[h+wh][w+ww] != "#":
            if S[h+wh][w+ww] > S[h][w] + 1:
                S[h+wh][w+ww] = S[h][w] + 1
                q.append((h+wh, w+ww))
 
if S[DH-1][DW-1] == 10**7:
    print(-1)
else:
    print(S[DH-1][DW-1])

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(i) for i in input().split()]
Ci, Cj = [int(i)-1 for i in input().split()]
Di, Dj = [int(i)-1 for i in input().split()]
S = []
for i in range(H):
    S.append([i for i in input()])


def append_label_4(i, j, n):
    ret = 0
    labeling_list = [[i, j]]
    while labeling_list:
        i, j = labeling_list[-1]
        labeling_list = labeling_list[:-1]
        S[i][j] = n
        if i != 0 and S[i-1][j] != '#' and S[i-1][j] != n:
            labeling_list.append([i-1, j])
            S[i-1][j] = n
        if i != H-1 and S[i+1][j] != '#' and S[i+1][j] != n:
            labeling_list.append([i+1, j])
            S[i+1][j] = n
        if j != 0 and S[i][j-1] != '#' and S[i][j-1] != n:
            labeling_list.append([i, j-1])
            S[i][j-1] = n
        if j != W-1 and S[i][j+1] != '#' and S[i][j+1] != n:
            labeling_list.append([i, j+1])
            S[i][j+1] = n
        for ii in range(max(0, i-2), min(H-1, i+2)+1):
            for jj in range(max(0, j-2), min(W-1, j+2)+1):
                if S[ii][jj] == '.':
                    S[ii][jj] = n+1
                    ret = n+1
    return ret


hops = append_label_4(Ci, Cj, 0)
change = 1
while change:
    change = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == hops:
                ret = append_label_4(i, j, hops)
                if ret == hops + 1:
                    change = 1
    hops += 1

if S[Di][Dj] == '.':
    print(-1)
else:
    print(S[Di][Dj])

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    from collections import deque
    import sys
    H, W = map(int, stdin.readline().split())
    ch, cw = map(int, stdin.readline().split())
    dh, dw = map(int, stdin.readline().split())
    ch, cw, dh, dw = ch-1, cw-1, dh-1, dw-1
    S = [input() for _ in range(H)]
    d = [[0]*W for _ in range(H)]

    que = deque([[cw, ch]])
    count = 0
    while que:
        while que:
            x, y = que.popleft()
            if x == dw and y == dh:
                print(count)
                sys.exit()
                
            d[y][x] = -1
            for i in range(-2, 3):
                for j in range(-2, 3):
                    nnx, nny = x+i, y+j
                    if 0<=nnx<W and 0<=nny<H and d[nny][nnx]==0 and S[nny][nnx]!='#':
                        d[nny][nnx] = 1
        
            for dx, dy in [1, 0], [0, 1], [-1, 0], [0, -1]:
                nx, ny = x+dx, y+dy
                if 0<=nx<W and 0<=ny<H and S[ny][nx]!='#' and d[ny][nx]!=-1:
                    if nx == dw and ny == dh:
                        print(count)
                        sys.exit()
                
                    d[ny][nx] = -1
                    for i in range(-2, 3):
                        for j in range(-2, 3):
                            nnx, nny = nx+i, ny+j
                            if 0<=nnx<W and 0<=nny<H and d[nny][nnx]==0 and S[nny][nnx]!='#':
                                d[nny][nnx] = 1
                    que.append([nx, ny])
                
        for i in range(W):
            for j in range(H):
                if d[j][i] == 1:
                    d[j][i] == -1
                    que.append([i, j])
        count += 1
    print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math

def explore(C, D):
    queue = deque([[C[0]-1, C[1]-1]])
    maze_visited[C[0]-1][C[1]-1] = 0
    while queue:
        y, x = queue.popleft()
        mv_cur = maze_visited[y][x]
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            n_x, n_y = x + i, y + j
            if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                mv_n = maze_visited[n_y][n_x]
                if mv_n > mv_cur:
                    if S[n_y][n_x] == '.':
                        maze_visited[n_y][n_x] = mv_cur
                        queue.append([n_y, n_x])
        for i in range(-2, 3):
            for j in range(-2, 3):
                if abs(i) + abs(j) <= 1:
                    continue
                n_x, n_y = x + i, y + j
                if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                    mv_n = maze_visited[n_y][n_x]
                    if mv_n > mv_cur + 1:
                        if S[n_y][n_x] == '.':
                            maze_visited[n_y][n_x] = mv_cur + 1
                            queue.append([n_y, n_x])
    
H, W = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))

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

maze_visited = [[math.inf] * W for i in range(H)]

explore(C,D)

if maze_visited[D[0] - 1][D[1] - 1] == math.inf:
    print('-1')
else:
    print(maze_visited[D[0] - 1][D[1] - 1])

Submission status: Time Limit Exceeded

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

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

h,w = mp()
ch, cw = mp()
dh,dw = mp()
ch += 1
cw += 1
dh += 1
dw += 1
grid = []
grid.append(["#"]*(w+4))
grid.append(["#"]*(w+4))
ans_grid = []
for i in range(h):
    u = ["#", "#"]
    a = list(input())
    for j in range(w):
        u.append(a[j])
    u.append("#")
    u.append("#")
    grid.append(u)
grid.append(["#"]*(w+4))
grid.append(["#"]*(w+4))

for i in range(h+4):
    ans_grid.append([int(1e6+2)]*(w+4))
# print(grid)
# print(ans_grid)

from collections import deque
def bfs(x,y):
    q = deque([])
    used = set()
    q.append((x,y))
    used.add((x,y))
    ans_grid[x][y] = 0
    while q:
        here = q.popleft()
        move = [(here[0]-1, here[1]),
                (here[0], here[1]-1),
                (here[0], here[1]+1),
                (here[0]+1, here[1])]
        warp = [(here[0]-2, here[1]-2), (here[0]-2, here[1]-1), (here[0]-2, here[1]), (here[0]-2, here[1]+1), (here[0]-2, here[1]+2),
                (here[0]-1, here[1]-2), (here[0]-1, here[1]-1), (here[0]-1, here[1]+1), (here[0]-1, here[1]+2),
                (here[0], here[1]-2), (here[0], here[1]+2),
                (here[0]+1, here[1]-2), (here[0]+1, here[1]-1), (here[0]+1, here[1]+1), (here[0]+1, here[1]+2),
                (here[0]+2, here[1]-2), (here[0]+2, here[1]-1), (here[0]+2, here[1]), (here[0]+2, here[1]+1), (here[0]+2, here[1]+2)]
        for i in range(len(warp)):
            u = warp[i][0]
            v = warp[i][1]
            if grid[u][v] == "." and ans_grid[u][v] > ans_grid[here[0]][here[1]]+1:
                ans_grid[u][v] = min(ans_grid[u][v], ans_grid[here[0]][here[1]]+1)
                q.append((u,v))
                used.add((u,v))
        for i in range(len(move)):
            u = move[i][0]
            v = move[i][1]
            if (move[i] not in used or ans_grid[u][v] > ans_grid[here[0]][here[1]]) and grid[u][v] == ".":
                ans_grid[u][v] = min(ans_grid[here[0]][here[1]], ans_grid[u][v])
                q.append((u,v))
                used.add((u,v))
        # print(ans_grid[2:])



bfs(ch,cw)
ans = ans_grid[dh][dw]
# print(ans_grid)
if ans == int(1e6+2):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#
import math
import sys
import itertools
import numpy as np

h,w = map(int, input().split())

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

x = np.zeros((h,w))
#y = np.zeros((h,w))

z = [list(input()) for i in range(h)]
for i in range(h):
    for j in range(w):
        if z[i][j]== '.':
            x[i][j] = 0
        else:
            x[i][j] = -1
#print(x)
x[ch-1][cw-1]=1

def tansaku():
    nu = 0
    while 1:
        nutta=0 # 塗ったマス
        for i in range(h):
            for j in range(w):
                if x[i][j] == 1:
                    if i>0:
                        if x[i-1][j]==0:
                            nutta += 1
                            x[i-1][j]=1
                    if j>0:
                        if x[i][j-1]==0:
                            nutta += 1
                            x[i][j-1]=1
                    if i<h-1:
                        if x[i+1][j]==0:
                            nutta += 1
                            x[i+1][j]=1
                    if j<w-1:
                        if x[i][j+1]==0:
                            nutta += 1
                            x[i][j+1]=1
        if nutta==0:
            return nu
        else:
            nu += nutta

def warp():
    y = np.zeros((h,w))
    nu = 0
    for i in range(h):
        for j in range(w):
            if x[i][j] == 1:
                for p in range(max(i-2,0),min(i+3,h)):
                    for q in range(max(j-2,0),min(j+3,w)):
                        if x[p][q] == 0:
                            y[p][q]=1
                            #print("a",p,q)
                            nu += 1
    for i in range(h):
        for j in range(w):
            if y[i][j]==1:
                x[i][j]=1
                #print("b")
    return nu # これは塗った数よりは多いがnuが1なら0ではない


answer = 0
while(1):
    #print(x,ch,cw,dh,dw)
    nurioe = tansaku()
    #print(x,nurioe)
    if x[dh-1][dw-1]==1:
        print(answer)
        break
    nurioe = warp()
    answer += 1
    #print(x,nurioe)
    if nurioe == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(H, W, C, D, S):
    INF = 10**6
    dist = [[INF] * W for _ in range(H)]
    di, dj = D
    dist[di][dj] = 0
    q = deque([(di, dj, 0)])
    while q:
        i, j, d = q.popleft()
        if d > dist[i][j]: continue
        for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                if dist[ni][nj] > d:
                    dist[ni][nj] = d
                    q.append((ni, nj, d))
        for ni in range(i - 2, i + 2 + 1, 1):
            if not(0 <= ni < H): continue
            dni = dist[ni]
            sni = S[ni]
            for nj in range(j - 2, j + 2 + 1, 1):
                if 0 <= nj < W and sni[nj] == '.':
                    if dni[nj] > d + 1:
                        dni[nj] = d + 1
                        q.append((ni, nj, d + 1))

    ans = dist[C[0]][C[1]]
    print(ans if ans < INF else -1)


if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = tuple(map(lambda x: int(x) - 1, input().split()))
    D = tuple(map(lambda x: int(x) - 1, input().split()))
    S = [list(input().rstrip()) for _ in range(H)]
    main(H, W, C, D, S)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def dfs(stack):
    if not stack:
        return
    x, y, d = stack[0]
    dp[y, x] = d
    stack2 = []
    while stack:
        x, y, d = stack.pop()
        if dp[y, x] < d:
            continue
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                dp[ny, nx] = d
                stack.append((nx, ny, d))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                dp[ny, nx] = d+1
                stack2.append((nx, ny, d+1))
    dfs(stack2)

dfs([(cw-1, ch-1, 0)])
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
def solve():
    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 _ in range(H)]
    area_num = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                dfs(h,w,H,W,S,area_num)
                area_num += 1

    start_area_num = int(S[Ch][Cw])
    goal_area_num = int(S[Dh][Dw])

    G = defaultdict(set)

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

            d = ((0,-1),(0,1),(-1,0),(1,0))
            close_to_wall = False
            for dh, dw in d:
                if dh+h < 0 or dh+h >= H:
                    continue
                if dw+w < 0 or dw+w >= W:
                    continue

                if S[dh+h][dw+w] == '#':
                    close_to_wall = True
            
            if not close_to_wall:
                continue

            for dh in range(2+1):
                if h+dh < 0 or h+dh >= H:
                    continue
                for dw in range(-2,2+1):
                    if w+dw < 0 or w+dw >= W:
                        continue
                    to_area_num = S[h+dh][w+dw]
                    if to_area_num == '#':
                        continue
                    to_area_num = int(to_area_num)
                    if from_area_num != to_area_num:
                        G[to_area_num].add(from_area_num)
                        G[from_area_num].add(to_area_num)
    
    area_num_count = area_num + 1
    visited = [False] * area_num_count
    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        visited[cur_area_num] = True
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                q.append((next_area_num,warp_cnt+1))
    else:
        print(-1)

def dfs(h,w,H,W,S,area_num):
    if 0 <= h < H and 0 <= w < W and S[h][w] == '.':
        S[h][w] = str(area_num)
        dfs(h+1,w,H,W,S,area_num)
        dfs(h,w+1,H,W,S,area_num)
        dfs(h-1,w,H,W,S,area_num)
        dfs(h,w-1,H,W,S,area_num)

def mod_graph(G,including_area_num_set):
    for area_num_from in including_area_num_set:
        for area_num_to in including_area_num_set:
            G[area_num_from].add(area_num_to)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

def sol():
    #xy=[(1,0),(-1,0),(0,1),(0,-1)]
    xy=[(1,0),(-1,0),(0,1),(0,-1),(-1,-1),(-1,1),(1,1),(1,-1),(2,0),(-2,0),(0,2),(0,-2),(-2,-1),(-2,1),(2,1),(2,-1),(-1,-2),(-1,2),(1,2),(1,-2),(-2,-2),(-2,2),(2,2),(2,-2)]
    #wp=[(-1,-1),(-1,1),(1,1),(1,-1),(2,0),(-2,0),(0,2),(0,-2),(-2,-1),(-2,1),(2,1),(2,-1),(-1,-2),(-1,2),(1,2),(1,-2),(-2,-2),(-2,2),(2,2),(2,-2)]

    h,w=map(int,input().split())
    c1,c2=map(int,input().split())
    d1,d2=map(int,input().split())
    d=[list(input()) for i in range(h)]
    d[c1-1][c2-1]=0
    p=set([(c1-1,c2-1)])
    while len(p):
        a,b=p.pop()
        #for ii,x,y in enumerate(xy):
        for ii,jj in enumerate(xy):
            x,y=jj
            x+=a
            y+=b
            z=[0,1][ii>3]
            if 0<=x<h and 0<=y<w and d[x][y]!="#":
                if d[x][y]=="." or d[x][y]>d[a][b]+z:
                    d[x][y]=d[a][b]+z
                    p.add((x,y))
    #    for x,y in wp1:
    #        x+=a
    #        y+=b
    #        if 0<=x<h and 0<=y<w and d[x][y]!="#":
    #            if d[x][y]=="." or d[x][y]>d[a][b]+1:
    #                d[x][y]=d[a][b]+1
    #                p.add((x,y))
    #    print(p)
    #    print(d)

    print(-1 if (d[d1-1][d2-1]=="#" or d[d1-1][d2-1]==".") else d[d1-1][d2-1])

if __name__=="__main__":
    sol()