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
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main(wall, Sx, Sy, Tx, Ty):
    INF = 1 << 30
    H, W = wall.shape
    S = Sx * W + Sy
    T = Tx * W + Ty
    dist = np.full(H * W, INF, np.int64)
    deq = np.empty(H * W + 100, np.int64)
    dist[S] = 0
    deq[0], l, r = S, 0, 1
    while l < r:
        v, l = deq[l], l + 1
        vx, vy = divmod(v, W)
        # そのままあるく
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            wx, wy = vx + dx, vy + dy
            if not (0 <= wx < H):
                continue
            if not (0 <= wy < W):
                continue
            if wall[wx, wy]:
                continue
            w = wx * W + wy
            if dist[w] <= dist[v]:
                continue
            dist[w] = dist[v]
            deq[l - 1], l = w, l - 1
        # ワープする
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                wx, wy = vx + dx, vy + dy
                if not (0 <= wx < H):
                    continue
                if not (0 <= wy < W):
                    continue
                if wall[wx, wy]:
                    continue
                w = wx * W + wy
                if dist[w] <= dist[v] + 1:
                    continue
                dist[w] = dist[v] + 1
                deq[r], r = w, r + 1
    ans = dist[T]
    if ans == INF:
        ans = -1
    return ans

H, W = map(int, readline().split())
Sx, Sy = map(lambda x: int(x) - 1, readline().split())
Tx, Ty = map(lambda x: int(x) - 1, readline().split())
wall = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W] == b'#'

print(main(wall, Sx, Sy, Tx, Ty))

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

H, W = MI()
Ch, Cw = MI()
Dh, Dw = MI()
S_ = []
for i in range(H):
    s = S()
    S_.append(s)

# i行目j列目のマスに(i - 1) * W + j　- 1の数字を割り振る
star = (Ch - 1) * W + Cw - 1
goal = (Dh - 1) * W + Dw - 1
g = [[] for _ in range(H * W)]
for i in range(H * W):
    h, w = divmod(i, W)
    if S_[h][w] == '#':
        continue
    else:
        if w != 0 and S_[h][w - 1] == '.':
            g[i].append(i - 1)
        if w != W - 1 and S_[h][w + 1] == '.':
            g[i].append(i + 1)
        if h != 0 and S_[h - 1][w] == '.':
            g[i].append(i - W)
        if h != (H - 1) and S_[h + 1][w] == '.':
            g[i].append(i + W)


from collections import deque

def bfs(u, n):
    queue = deque([u])
    d = [None] * n # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    dif_list = [u]
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = 0
                queue.append(i)
                dif_list.append(i)
    return dif_list

def warp(A, B):
    dif_A = []
    for a in A:
        h, w = divmod(a, W)
        left = min(w, 2)
        right = min(W - 1 - w, 2)
        a_list = []
        for i in range(-left, right + 1):
            for j in range(-2, 3):
                a_ = a + i + (j * W)
                a_list.append(a_)

        for a_ in a_list:
            h_, w_ = divmod(a_, W)
            if 0 <= a_ <= H * W - 1 and a_ not in B and a_ not in dif_A and S_[h_][w_] == '.':
                dif_A.append(a_)

    for b in dif_A:
        for c in bfs(b, H * W):
            if c not in dif_A:
                dif_A.append(c)
    return dif_A

dif_0 = bfs(star, H * W)
dif_total = dif_0
ans = 0
if goal in dif_0:
    print(0)
    exit()
else:
    while dif_0 != []:
        dif_0 = warp(dif_0, dif_total)
        dif_total += dif_0
        ans += 1
        if goal in dif_0:
            print(ans)
            exit()
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
C0, C1 = map(int, input().split())
D0, D1 = map(int, input().split())

ARR = []

for i in range(H):
    ARR.append(input())


def calculate(h, w, c0, c1, d0, d1, arr):
    c0 = c0 - 1
    c1 = c1 - 1
    d0 = d0 - 1
    d1 = d1 - 1

    status = []
    for i in range(H):
        tmp = []
        for j in range(W):
            tmp.append(-1)
        status.append(tmp)

    q = deque()

    q.append((c0, c1, 0))

    while len(q) > 0:
        hIndex, wIndex, index = q.popleft()

        if (status[hIndex][wIndex] > 0) and (index > status[hIndex][wIndex]):
            continue

        sss = [(hIndex,wIndex - 1), (hIndex, wIndex + 1), ( hIndex - 1, wIndex), (hIndex + 1, wIndex)]


        for sH, sW in sss:
            if (sH >= 0) and (sH < h) and (sW >= 0) and (sW < w):
                if arr[sH][sW] == '.':
                    tmpIndex = index
                    if status[sH][sW] == -1:
                        status[sH][sW] = tmpIndex
                        q.insert(0, (sH, sW, tmpIndex))
                    else:
                        if status[sH][sW] > tmpIndex:
                            status[sH][sW] = tmpIndex
                            q.insert(0, (sH, sW, tmpIndex))

        for _hIndex in range(hIndex - 2, hIndex + 3):
            for _wIndex in range(wIndex - 2, wIndex + 3):
                if (_hIndex == hIndex) and (_wIndex == wIndex):
                    continue
                if (_hIndex == c0) and (_wIndex == c1):
                    continue
                if (_hIndex, _wIndex) in sss:
                    continue
                if (_hIndex >= 0 and _hIndex < h) and (_wIndex >= 0 and _wIndex < w):
                    if arr[_hIndex][_wIndex] == '.':
                        tmpIndex = index + 1
                        if status[_hIndex][_wIndex] == -1:
                            status[_hIndex][_wIndex] = tmpIndex
                            q.append((_hIndex, _wIndex, tmpIndex))
                        else:
                            if status[_hIndex][_wIndex] > tmpIndex:
                                status[_hIndex][_wIndex] = tmpIndex
                                q.append((_hIndex, _wIndex, tmpIndex))

    if status[d0][d1] >= 0:
        print(status[d0][d1])
    else:
        print(-1)


calculate(H, W, C0, C1, D0, D1, ARR)

Submission status: Time Limit Exceeded

Solution code:
inf = 10 ** 9
from collections import deque
def bfs(sx, sy):
    cost = [[inf] * w for i in range(h)]
    d = ((0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (-1, 1), (1, -1), (-1, -1))
    cost[sx - 1][sy - 1] = 0
    q = deque()
    q.append((sx - 1, sy - 1))
    
    while q:
        s, t = q.popleft()
        for dx, dy in d:
            nx = s + dx
            ny = t + dy
            
            if not(0 <= nx < h and 0 <= ny < w):continue
            if cost[nx][ny] <= cost[s][t]:continue
            if (dx + dy)%2 == 0:
                if c[nx][ny] == '.' and cost[nx][ny] > cost[s][t] + 1:
                    cost[nx][ny] = cost[s][t] + 1
                    q.append((nx, ny))

                next_d = ((dx, 0), (0, dy), (dx, dy))
                for ddx, ddy in next_d:
                    nnx = nx + ddx
                    nny = ny + ddy
                    if not(0 <= nnx < h and 0 <= nny < w):continue
                    if c[nnx][nny] == '#':continue
                    if cost[nnx][nny] <= cost[s][t] + 1:continue
                    cost[nnx][nny] = cost[s][t] + 1
                    
                    if (nnx, nny) == (dh - 1, dw - 1):continue
                    q.append((nnx, nny))
                continue
                    
            elif c[nx][ny] == '.' and (dx + dy)%2 != 0:
                cost[nx][ny] = min(cost[nx][ny], cost[s][t])
                
            elif c[nx][ny] == '#' and (dx + dy)%2 != 0:
                nx += dx
                ny += dy
                if not(0 <= nx < h and 0 <= ny < w):continue
                if c[nx][ny] == '#':continue
                if cost[nx][ny] <= cost[s][t] + 1:continue
                cost[nx][ny] = cost[s][t] + 1
                
            if (nx, ny) == (dh - 1, dw - 1):continue
            q.append((nx, ny))

    return cost
        
h, w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
c = [list(input()) for _ in range(h)]

res = bfs(ch, cw)
if res[dh - 1][dw - 1] == inf:print(-1)
else:print(res[dh - 1][dw - 1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def solvemaze(y, x, num):
    maps.append([])
    dx, dy = (-1, 0, 1, 0), (0, -1, 0, 1)
    maze[y][x] = num
    que = deque()
    que.append((y, x))
    while que:
        y_, x_ = que.popleft()
        maps[num].append((y_, x_))
        for i in range(4):
            y2 = y_ + dy[i]
            x2 = x_ + dx[i]
            if 0 <= y2 < h and 0 <= x2 < w and maze[y2][x2] == '.':
                maze[y2][x2] = num
                que.append((y2, x2))

def makeroute(s_maps, num):
    for y, x in s_maps:
        for i in range(-2, 3):
            for j in range(-2, 3):
                y2 = y + i
                x2 = x + j
                if 0 <= y2 < h and 0 <= x2 < w:
                    num2 = maze[y2][x2]
                    if not  num2 in [0, '#'] + E[num]:
                        E[num].append(num2)
                        E[num2].append(num)
    

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [[x for x in input()] for _ in range(h)]
maps = []

num = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            solvemaze(i, j, num)
            num += 1

E = [[] for _ in range(num)]
for i in range(num):
    makeroute(maps[i], i)

s = maze[Ch-1][Cw-1]
g = maze[Dh-1][Dw-1]
used = [False] * num
used[s] = True
que = deque()
que.append((0, s))
cost = [float('inf')] * num
cost[s] = 0
while que:
    c, v = que.popleft()
    for e in E[v]:
        if not used[e]:
            que.append((c+1, e))
            cost[e] = c+1
            used[e] = True

if not used[g]:
    print(-1)
else:
    print(cost[g])

Submission status: Time Limit Exceeded

Solution code:
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
from functools import lru_cache, cmp_to_key
from collections import defaultdict as dd, deque, Counter as C
from bisect import bisect_left as bl, bisect_right as br, bisect
from heapq import heapify, heappop, heappush
from math import ceil, log, floor, sqrt
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var, end="\n"): sys.stdout.write(str(var)+end)
def outa(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


def valid(a, b):
    return 0 <= a < n and 0 <= b < m


n, m = sp()
sx, sy = sp()
ex, ey = sp()
sx -= 1
sy -= 1
ex -= 1
ey -= 1
mat = [data() for i in range(n)]
inf = 10 ** 10
q = deque()
q.append([sx, sy])
x, y = [-1, 1, 0, 0], [0, 0, -1, 1]
jump = [[inf] * m for _ in range(n)]
jump[sx][sy] = 0
while q:
    sx, sy = q.popleft()
    for i in range(4):
        tx, ty = sx + x[i], sy + y[i]
        if valid(tx, ty) and mat[tx][ty] == ".":
            if jump[tx][ty] > jump[sx][sy]:
                q.append([tx, ty])
                jump[tx][ty] = jump[sx][sy]
    for i in range(-2, 3):
        for j in range(-2, 3):
            tx, ty = sx + i, sy + j
            if valid(tx, ty) and mat[tx][ty] == ".":
                if jump[tx][ty] > jump[sx][sy] + 1:
                    q.appendleft([tx, ty])
                    jump[tx][ty] = jump[sx][sy]+1
if jump[ex][ey] == 10 ** 10:
    print(-1)
    exit()
print(jump[ex][ey])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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())
dy, dx = (-1, 0, 1, 0), (0, -1, 0, 1)
maze = [[float('inf') if x == '.' else -float('inf') for x in input()] for _ in range(h)]
maze[Ch][Cw] = 0
que = deque()
que.append((0, Ch, Cw))
while que:
    c, y, x = que.popleft()
    
    if c > maze[y][x]:
        continue
    
    if y == Dh and x == Dw:
        break
    
    for i in range(4):
        y2, x2 = y + dy[i], x + dx[i]
        if 0 <= y2 < h and 0 <= x2 < w and c < maze[y2][x2]:
            maze[y2][x2] = c
            que.appendleft((c, y2, x2))
            
    for i in range(-2, 3):
        for j in range(-2, 3):
            y3, x3, c2 = y + i, x + j, c+1
            if 0 <= y3 < h and 0 <= x3 < w and c2 < maze[y3][x3]:
                maze[y3][x3] = c2
                que.append((c2, y3, x3))

ans = maze[Dh][Dw]
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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())
dy, dx = (-1, 0, 1, 0), (0, -1, 0, 1)
maze = [[float('inf') if x == '.' else -float('inf') for x in input()] for _ in range(h)]
maze[Ch][Cw] = 0
que = deque()
que.append((0, Ch, Cw))
while que:
    c, y, x = que.popleft()
    
    if y == Dh and x == Dw:
        break
    
    if c > maze[y][x]:
        continue
    
    for i in range(4):
        y2, x2 = y + dy[i], x + dx[i]
        if 0 <= y2 < h and 0 <= x2 < w and c < maze[y2][x2]:
            maze[y2][x2] = c
            que.appendleft((c, y2, x2))
            
        for j in range(-2, 3):
            for k in range(-2, 3):
                y3, x3, c2 = y + j, x + k, c+1
                if 0 <= y3 < h and 0 <= x3 < w and c2 < maze[y3][x3]:
                    maze[y3][x3] = c2
                    que.append((c2, y3, x3))

ans = maze[Dh][Dw]
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
C0, C1 = map(int, input().split())
D0, D1 = map(int, input().split())

ARR = []

for i in range(H):
    ARR.append(input())


def calculate(h, w, c0, c1, d0, d1, arr):
    c0 = c0 - 1
    c1 = c1 - 1
    d0 = d0 - 1
    d1 = d1 - 1

    status = []
    for i in range(H):
        tmp = []
        for j in range(W):
            tmp.append(-1)
        status.append(tmp)

    q = deque()

    q.append((c0, c1, 0))

    while len(q) > 0:
        hIndex, wIndex, index = q.popleft()

        if (status[hIndex][wIndex] > 0) and (index > status[hIndex][wIndex]):
            continue

        sss = [(hIndex,wIndex - 1), (hIndex, wIndex + 1), ( hIndex - 1, wIndex), (hIndex + 1, wIndex)]


        for sH, sW in sss:
            if (sH >= 0) and (sH < h) and (sW >= 0) and (sW < w):
                if arr[sH][sW] == '.':
                    tmpIndex = index
                    if status[sH][sW] == -1:
                        status[sH][sW] = tmpIndex
                        q.append((sH, sW, tmpIndex))
                    else:
                        if status[sH][sW] > tmpIndex:
                            status[sH][sW] = tmpIndex
                            q.append((sH, sW, tmpIndex))

        for _hIndex in range(hIndex - 2, hIndex + 3):
            for _wIndex in range(wIndex - 2, wIndex + 3):
                if (_hIndex == hIndex) and (_wIndex == wIndex):
                    continue
                if (_hIndex == c0) and (_wIndex == c1):
                    continue
                if (_hIndex, _wIndex) in sss:
                    continue
                if (_hIndex >= 0 and _hIndex < h) and (_wIndex >= 0 and _wIndex < w):
                    if arr[_hIndex][_wIndex] == '.':
                        tmpIndex = index + 1
                        if status[_hIndex][_wIndex] == -1:
                            status[_hIndex][_wIndex] = tmpIndex
                            q.append((_hIndex, _wIndex, tmpIndex))
                        else:
                            if status[_hIndex][_wIndex] > tmpIndex:
                                status[_hIndex][_wIndex] = tmpIndex
                                q.append((_hIndex, _wIndex, tmpIndex))

    if status[d0][d1] >= 0:
        print(status[d0][d1])
    else:
        print(-1)


calculate(H, W, C0, C1, D0, D1, ARR)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

def check_func(h, w, check, meiro):
    if (h >= 0 and w >= 0) and (h < len(meiro) and w < len(meiro[0])) and meiro[h][w] == '.' and not (h, w) in check:
        return True
    else:
        return False
def main():
    h, w = map(int, input().split())
    sh, sw = map(int, input().split())
    gh, gw = map(int, input().split())
    s_meiro = []
    for i in range(h):
        s_meiro.append(list(input()))
    check_list = np.full((h, w), -1)
    start = [sh-1, sw-1]
    goal = [gh-1, gw-1]
    now_cost = 0
    checked_point = set()
    cost_1_set = set()
    point_que = deque([start])
    cost_dict = {tuple(start): now_cost}

    move_walk = [[-1, 0], [1, 0], [0, -1,], [0, 1]]
    move_warp = []
    for i in range(-2, 3):
        for j in range(-2, 3):
            if not [i, j] in move_walk and [i, j] != [0,0]:
                move_warp.append([i, j])

    ans = -1
    while(1):
        # print('----------------')
        # print(point_que)
        # print(cost_dict)
        check_point = point_que.popleft()
        # 歩く
        for masu in move_walk:
            ph, pw = check_point[0] - masu[0], check_point[1] - masu[1]
            cost = cost_dict[tuple(check_point)]
            if (ph, pw) in cost_1_set:
                cost_1_set.discard((ph, pw))
                try:
                    point_que.remove([ph, pw])
                except:
                    pass
                point_que.appendleft([ph, pw])
                cost_dict[(ph, pw)] = cost
            if check_func(ph, pw, checked_point, s_meiro):
                checked_point.add((ph, pw))
                point_que.appendleft([ph, pw])
                cost_dict[(ph, pw)] = cost
        # 魔法で移動
        for masu in move_warp:
            ph, pw = check_point[0] - masu[0], check_point[1] - masu[1]
            cost = cost_dict[tuple(check_point)]
            if check_func(ph, pw, checked_point, s_meiro):
                cost += 1
                checked_point.add((ph, pw))
                point_que.append([ph, pw])
                cost_dict[(ph, pw)] = cost
                cost_1_set.add((ph, pw))

        

        if len(point_que) == 0:
            break
    try:
        print(cost_dict[tuple(goal)])
    except:
        print(-1)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

ch -= 1; cw -= 1; dh -= 1; dw -= 1; 

s = []
for _ in range(H):
    s.append(list(input()))
cs = [[1000000 for _ in range(W)] for _ in range(H)]

q = []
heapq.heappush(q, (0, (ch, cw)))

while q:
    c, (h, w) = heapq.heappop(q)
    if cs[h][w] <= c:
        continue
    cs[h][w] = c
    for nh, nw in [(h - 1, w), (h + 1, w), (h, w - 1), (h, w + 1)]:
        if 0 <= nh < H and 0 <= nw < W and s[nh][nw] == '.' and c < cs[nh][nw]:
            heapq.heappush(q, (c, (nh, nw)))
    for nh in range(h - 2, h + 3):
        for nw in range(w - 2, w + 3):
            if 0 <= nh < H and 0 <= nw < W and s[nh][nw] == '.' and c + 1 < cs[nh][nw]:
                heapq.heappush(q, (c + 1, (nh, nw)))

print(-1 if cs[dh][dw] == 1000000 else cs[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
INF=10**20
from heapq import heappop,heappush,heapify
def dijkstra(G,H,W,sh,sw):
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    que=[(0,sh,sw)]
    dist=[[INF]*W for i in range(H)]
    dist[sh][sw]=0
    while que:
        mincost,h,w=heappop(que)
        if(mincost>dist[h][w]):
            continue
        for di in range(4):
            nh=h+dx[di]
            nw=w+dy[di]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(G[nh][nw]=='#'):
                continue
            if(dist[h][w]<dist[nh][nw]):
                dist[nh][nw]=dist[h][w]
                heappush(que,(dist[nh][nw],nh,nw))
        for nh in range(h-2,h+3):
            for nw in range(w-2,w+3):
                if (nh>H-1 or nh<0 or nw>W-1 or nw<0):
                    continue
                if(G[nh][nw]=='#'):
                    continue
                if dist[h][w]+1<dist[nh][nw]:
                    dist[nh][nw]=dist[h][w]+1
                    heappush(que,(dist[nh][nw],nh,nw))
    return dist

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())
G=[list(input()) for i in range(H)]
dist=dijkstra(G,H,W,Ch,Cw)
ans=dist[Dh][Dw]
if ans!=INF:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import product
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
si, sj = map(lambda x: int(x)-1, input().split())
gi, gj = map(lambda x: int(x)-1, input().split())
fld = ''.join([input().rstrip()for _ in range(h)])
INF = 10**18


def to_v(i, j):
    return i*w+j


n = h*w
start = to_v(si, sj)
goal = to_v(gi, gj)


def generate_v2(v):
    i, j = divmod(v, w)
    if 0 < i:
        yield v-w
    if i < h-1:
        yield v+w
    if 0 < j:
        yield v-1
    if j < w-1:
        yield v+1


def generate_v2_b(v):
    i, j = divmod(v, w)
    it = [-2, -1, 1, 2]
    for di, dj in product(it, repeat=2):
        x, y = i+di, j+dj
        if x < 0 or h <= x or y < 0 or w <= y:
            continue
        yield x*w+y

    it = [(-2, 0), (2, 0), (0, -2), (0, 2)]
    for di, dj in it:
        x, y = i+di, j+dj
        if x < 0 or h <= x or y < 0 or w <= y:
            continue
        yield x*w+y


def bfs(init_v):
    next_v = deque([init_v])
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        for v2 in generate_v2(v):
            if fld[v2] == '#':
                continue
            if dist[v2] <= dist[v]:
                continue
            dist[v2] = dist[v]
            next_v.append(v2)

        for v2 in generate_v2_b(v):
            if fld[v2] == '#':
                continue
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)

    return dist


ans = bfs(start)[goal]
print(-1 if ans == INF else ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2
    now = ch*W + cw
    goal = dh*W + dw
    q = deque([now])
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[now] = 0
    D1 = [-W, -1, 1, W]
    D2 = []
    for dy in [-2*W, -W, 0, W, 2*W]:
        for dx in range(-2, 3):
            D2.append(dy+dx)

    while q:
        x = q.popleft()
        for d in D1:
            if S[x+d] == '.' and dist[x+d] > dist[x]:
                q.appendleft(x+d)
                dist[x+d] = dist[x]
    
        for d in D2:
            xx = x + d
            if 0 <= xx < W*H and dist[xx] > dist[x] and S[xx] == '.':
                q.append(xx)
                dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())  # 縦H X 横W マス
C = list(map(int, input().split()))  #[Ch, Cw]　　*1多いことに注意
D = list(map(int, input().split()))  #[Dh, Dw]　　*1多いことに注意
S = deque([["#"]*(W+4)])
S.append(["#"]*(W+4))
for i in range(H):
    S.append(["#","#"]+list(input())+["#","#"])
S.append(["#"]*(W+4))
S.append(["#"]*(W+4))
    
T = deque([[C[0]+1,C[1]+1]])
ans = 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]]

# 繰り返し
while T:
    K = deque([])
    while T:
        y,x = T.popleft()
        if S[y][x] =="." :
            K.append([y,x])
            S[y][x] = "#"
            for i,j in move:
                T.append([y+i,x+j])
    if [D[0]+1,D[1]+1] in K:
        print(ans)
        break
    ans += 1
    for z,w in K:
        for s_y, s_x in magic:
                if S[z+s_y][w+s_x] ==".":
                    if not S[z+s_y][w+s_x] in K and not [z+s_y,w+s_x] in T:
                        T.append([z+s_y, w+s_x])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import product
h, w = map(int, input().split())
si, sj = map(lambda x: int(x)-1, input().split())
gi, gj = map(lambda x: int(x)-1, input().split())
fld = ''.join([input()for _ in range(h)])
INF = 10**18


def to_v(i, j):
    return i*w+j


n = h*w
start = to_v(si, sj)
goal = to_v(gi, gj)


def generate_v2(v):
    i, j = divmod(v, w)
    if 0 < i:
        yield v-w
    if i < h-1:
        yield v+w
    if 0 < j:
        yield v-1
    if j < w-1:
        yield v+1


def generate_v2_b(v):
    i, j = divmod(v, w)
    it = [-2, -1, 1, 2]
    for di, dj in product(it, repeat=2):
        x, y = i+di, j+dj
        if x < 0 or h <= x or y < 0 or w <= y:
            continue
        yield x*w+y

    it = [(-2, 0), (2, 0), (0, -2), (0, 2)]
    for di, dj in it:
        x, y = i+di, j+dj
        if x < 0 or h <= x or y < 0 or w <= y:
            continue
        yield x*w+y


def bfs(init_v):
    next_v = deque([init_v])
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        for v2 in generate_v2(v):
            if fld[v2] == '#':
                continue
            if dist[v2] <= dist[v]:
                continue
            dist[v2] = dist[v]
            next_v.append(v2)

        for v2 in generate_v2_b(v):
            if fld[v2] == '#':
                continue
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)

    return dist


ans = bfs(start)[goal]
print(-1 if ans == INF else ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2
    now = ch*W + cw
    goal = dh*W + dw
    q = [now]
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[now] = 0
    D1 = [-W, -1, 1, W]
    D2 = []
    for dy in [-2*W, -W, 0, W, 2*W]:
        for dx in range(-2, 3):
            D2.append(dy+dx)

    while q:
        x = q.pop()
        for d in D1:
            if S[x+d] == '.' and dist[x+d] > dist[x]:
                q.append(x+d)
                dist[x+d] = dist[x]
    
        for d in D2:
            xx = x + d
            if 0 <= xx < W*H and dist[xx] > dist[x] and S[xx] == '.':
                q.append(xx)
                dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)