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
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_map_as(H, replace={'#': 1, '.': 0}, pad=None):
    '''
    文字列のmapを置換して読み込み。デフォでは#→1,.→0
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            # 内包表記はpypyでは若干遅いことに注意
            # #numpy使うだろうからこれを残しておくけど
    else:  # paddingする
        ret = [[pad] * (W + 2)]  # Wはどっかで定義しておくことに注意
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


def grid_dijkstra(grid, si: int, sj: int, INF=2**31):
    '''grid上のdijkstra法。gridはそこに入るときにかかるコスト
    si,sj は開始の座標。'''
    from heapq import heappop, heappush
    H = len(grid)
    W = len(grid[0])
    D = [[INF] * W for _ in [0] * H]  # -1がINFを意味する
    que = [(0, si, sj)]
    while que:
        c, i, j = heappop(que)
        if D[i][j] != INF:
            continue
        D[i][j] = c
        for di, dj in product([-2, -1, 0, 1, 2], repeat=2):
            ni, nj = i + di, j + dj
            if not (0 <= ni < H and 0 <= nj < W) or D[ni][nj] != INF or ni == nj == 0 or grid[ni][nj] == 1:
                continue
            if (di == 0 and abs(dj) == 1) or (dj == 0 and abs(di) == 1):  # 歩いて行ける
                nc = c
            else:  # ワープして行ける
                nc = c + 1
            heappush(que, (nc, ni, nj))
    return D


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from itertools import product, permutations, combinations

# もし歩くだけなら簡単
# ワープをどう処理する？
# もし周囲5*5を候補にするなら24*10**6 んー間に合うか微妙


H, W = ints()
si, sj = mina(*ints())
ti, tj = mina(*ints())
S = read_map_as(H)
D = grid_dijkstra(S, si, sj)
print(D[ti][tj] if D[ti][tj] != INF else -1)
# print(*D, sep='\n')

# unionfindで連結成分切り出してから、連結成分をまたぐときだけ+1するdfsかな?

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# ---------標準入力時--------------
h,w=map(int,readline().split())
ch, cw=map(int,readline().split())
dh, dw=map(int,readline().split())
m=list(map(lambda x: list(x.decode()), readlines()))
# ---------標準入力時--------------

# ---------ファイル入力時--------------
# with open('maze.txt', 'r') as f:
#     h,w=map(int,f.readline().split())
#     ch, cw=map(int,f.readline().split())
#     dh, dw=map(int,f.readline().split())
#     m=list(map(list, f.readlines()))
# ---------ファイル入力時--------------

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

def valid(i, j):
    if 0<=i<=h-1 and 0<=j<=w-1:
        return True
    else:
        return False

ad = [(-1,0), (0,-1), (1,0), (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)]

def bfs2():
    '''
    bfs1の移動の順番を変えただけ
    '''
    que=[]
    m[ch][cw]=str(0)
    que.append((ch,cw))
    
    while que!=[]:
        i, j=que.pop(0)

        # 隣接したマスへの移動
        for si, sj in ad:
            f=False
            if valid(i+si, j+sj) and m[i+si][j+sj]!='#':
                if m[i+si][j+sj]=='.':
                    m[i+si][j+sj]=m[i][j]
                    f=True
                else:
                    if int(m[i+si][j+sj])>int(m[i][j]):
                        m[i+si][j+sj]=m[i][j]
                        f=True
            if f:
                que.append((i+si, j+sj))

        for si, sj in warp:
            f=False
            if valid(i+si, j+sj) and m[i+si][j+sj]!='#':
                if m[i+si][j+sj]=='.':
                    m[i+si][j+sj]=str(int(m[i][j])+1)
                    f=True
                else:
                    if int(m[i+si][j+sj])>int(m[i][j])+1:
                        m[i+si][j+sj]=str(int(m[i][j])+1)
                        f=True
            if f:
                que.append((i+si, j+sj))
###---------------------------------------

bfs2()

if m[dh][dw] == '.':
    print(-1)
else:
    print(m[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1<<20)
h,w=[int(x) for x in input().split()]
ch,cw=[int(x) for x in input().split()]
dh,dw=[int(x) for x in input().split()]
ch-=1
cw-=1
dh-=1
dw-=1

s=[]
for _ in range(h):
    s.append(list(input()))

nxt=[[ch,cw,0]]
#再起
def rcl(y,x,now):
    
    if y==dh and x==dw:
        print(now)
        exit()
    
    if s[y][x]=='#':
        return
    
    s[y][x]='#'
    # 四方を見る
    for i in range(4):
        yy,xx=-1,0
        if i==1:yy,xx=0,1
        if i==2:yy,xx=1,0
        if i==3:yy,xx=0,-1
        
        if y+yy<0 or h<=y+yy or x+xx<0 or w<=x+xx:
            continue
        if s[y+yy][x+xx]=='#':
            continue
        
        rcl(y+yy,x+xx,now)
    #5*5
    for i in range(-2,3):
        for j in range(-2,3):
            if i==0 and j==0:
                continue
            if y+i<0 or h<=y+i or x+j<0 or w<=x+j:
                continue
            if s[y+i][x+j]=='.':
                nxt.append([y+i,x+j,now+1])
                s[y+i][x+j]=now+1

idx=0
while idx<len(nxt):
    i=nxt[idx]
    idx+=1
    if i[0]==dh and i[1]==dw:
        print(i[2])
        exit()
    rcl(i[0],i[1],i[2])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
from collections import defaultdict, deque
import sys

H, W = (int(x) for x in input().split()) 
CH, CW = (int(x)-1 for x in input().split()) 
DH, DW = (int(x)-1 for x in input().split()) 

MAZE = []

for i in range(H):
    MAZE.append(list(input()))

can_walk = ((1, 0), (0, 1), (-1, 0), (0, -1))

que = deque()
que.append((CH, CW, 0))

ret = -1

while len(que):
    h, w, cost = que[0]
    que.popleft()

    if MAZE[h][w] != '.' and MAZE[h][w] <= cost:
        continue

    MAZE[h][w] = cost

    if (h, w) == (DH, DW):
        ret = cost
        break

    for dh, dw in can_walk:
        nh = h + dh 
        nw = w + dw 
        if 0 <= nh < H and 0 <= nw < W and MAZE[nh][nw] != '#':
            que.appendleft((nh, nw, cost))

    warpcost = cost + 1
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            nh = h + dh 
            nw = w + dw 
            if 0 <= nh < H and 0 <= nw < W and MAZE[nh][nw] != '#':
#                print(h, w, dh, dw, nh, nw)
                que.append((nh, nw, warpcost))

#for i in range(H):
#    print (MAZE[i])
print(ret)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque

    INF = float('inf')

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

    t = [[INF] * W for _ in range(H)]
    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])

    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    while q:
        h, w = q.popleft()
        a = t[h][w]
        if h - 1 >= 0 and t[h - 1][w] > a:
            q.appendleft((h - 1, w))
            t[h - 1][w] = a
        if h + 1 < H and t[h + 1][w] > a:
            q.appendleft((h + 1, w))
            t[h + 1][w] = a
        if w - 1 >= 0 and t[h][w - 1] > a:
            q.appendleft((h, w - 1))
            t[h][w - 1] = a
        if w + 1 < W and t[h][w + 1] > a:
            q.appendleft((h, w + 1))
            t[h][w + 1] = a

        for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
            ti = t[i]
            for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                if ti[j] <= a + 1:
                    continue
                ti[j] = a + 1
                q.append((i, j))

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


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque

    INF = float('inf')

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

    t = [[INF] * W for _ in range(H)]
    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])

    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                t[h][w] = -1

    while q:
        h, w = q.popleft()
        a = t[h][w]
        if h - 1 >= 0 and t[h - 1][w] > a:
            q.appendleft((h - 1, w))
            t[h - 1][w] = a
        if h + 1 < H and t[h + 1][w] > a:
            q.appendleft((h + 1, w))
            t[h + 1][w] = a
        if w - 1 >= 0 and t[h][w - 1] > a:
            q.appendleft((h, w - 1))
            t[h][w - 1] = a
        if w + 1 < W and t[h][w + 1] > a:
            q.appendleft((h, w + 1))
            t[h][w + 1] = a

        for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
            for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                if t[i][j] <= a + 1:
                    continue
                t[i][j] = a + 1
                q.append((i, j))

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


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = float('inf')

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

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            t[h][w] = -1

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

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

Submission status: Time Limit Exceeded

Solution code:
# D - Wizard in Maze
import sys
from collections import deque
from typing import List, Tuple


class WarpableMaze:
    __slots__ = ["height", "width", "start", "goal", "road", "wall", "grid"]

    def __init__(
        self,
        height: int,
        width: int,
        start: Tuple[int, int],
        goal: Tuple[int, int],
        grid: List[str],
        road: str = ".",
        wall: str = "#",
    ) -> None:
        # Values of start and goal must be 0-origin.
        self.height = height + 4
        self.width = width + 4
        self.start = self._flatten_coordinate(*start)
        self.goal = self._flatten_coordinate(*goal)
        self.road = road
        self.wall = wall
        self.grid = self._flatten_grid(grid)

    def _flatten_coordinate(self, h: int, w: int) -> int:
        return self.width * (h + 2) + w + 2

    def _flatten_grid(self, grid: List[str]) -> str:
        flat_grid = self.wall * self.width * 2
        for row in grid:
            flat_grid += self.wall * 2 + row + self.wall * 2
        flat_grid += self.wall * self.width * 2
        return flat_grid

    def bfs(self) -> int:
        w = self.width
        move = (-w, w, -1, 1)
        warp = [-2 * w - 2, -2 * w - 1, -2 * w, -2 * w + 1, -2 * w + 2]
        warp.extend([-w - 2, -w - 1, -w + 1, -w + 2, -2, 2])
        warp.extend([w - 2, w - 1, w + 1, w + 2])
        warp.extend([2 * w - 2, 2 * w - 1, 2 * w, 2 * w + 1, 2 * w + 2])

        unsearched = -1
        dist = [unsearched] * (self.height * self.width)
        dist[self.start] = 0
        queue = deque([self.start])
        while queue:
            x = queue.popleft()
            if x == self.goal:
                break
            cur_dist = dist[x]

            for dx in move:
                nx = x + dx
                if self.grid[nx] == self.wall:
                    continue
                if dist[nx] == unsearched or dist[nx] > cur_dist:
                    dist[nx] = cur_dist
                    queue.appendleft(nx)

            for dx in warp:
                nx = x + dx
                if self.grid[nx] == self.wall:
                    continue
                if dist[nx] == unsearched or dist[nx] > cur_dist + 1:
                    dist[nx] = cur_dist + 1
                    queue.append(nx)

        return dist[self.goal]

    def debug(self):
        print(f"<DEBUG>\nstart={self.start}, goal={self.goal}", file=sys.stderr)
        for row in zip(*[iter(self.grid)] * self.width):
            print(*row, file=sys.stderr)


def main():
    H, W, CH, CW, DH, DW, *S = open(0).read().split()
    start, goal = (int(CH) - 1, int(CW) - 1), (int(DH) - 1, int(DW) - 1)
    maze = WarpableMaze(int(H), int(W), start, goal, S)
    # maze.debug()
    print(maze.bfs())


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def read_map_as(H, replace={'#': 1, '.': 0}, pad=None):
    '''
    文字列のmapを置換して読み込み。デフォでは#→1,.→0
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            # 内包表記はpypyでは若干遅いことに注意
            # #numpy使うだろうからこれを残しておくけど
    else:  # paddingする
        ret = [[pad] * (W + 2)]  # Wはどっかで定義しておくことに注意
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


def grid_dijkstra(grid, si: int, sj: int):
    '''grid上のdijkstra法。gridはそこに入るときにかかるコスト
    si,sj は開始の座標。'''
    from heapq import heappop, heappush
    H = len(grid)
    W = len(grid[0])
    # INF = 1000_000_000
    D = [[INF] * W for _ in [0] * H]  # -1がINFを意味する
    que = [(0, si, sj)]
    D[si][sj] = 0
    while que:
        c, i, j = heappop(que)
        D[i][j] = min(D[i][j], c)
        for di, dj in product([-2, -1, 0, 1, 2], repeat=2):
            ni, nj = i + di, j + dj
            if not (0 <= ni < H and 0 <= nj < W) or D[ni][nj] != INF or ni == nj == 0 or grid[ni][nj] == 1:
                continue
            if (di == 0 and abs(dj) == 1) or (dj == 0 and abs(di) == 1):  # 歩いて行ける
                nc = c
            else:  # ワープして行ける
                nc = c + 1
            heappush(que, (nc, ni, nj))
    return D


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from itertools import product, permutations, combinations

# もし歩くだけなら簡単
# ワープをどう処理する？
# もし周囲5*5を候補にするなら24*10**6 んー間に合うか微妙


H, W = ints()
si, sj = mina(*ints())
ti, tj = mina(*ints())
S = read_map_as(H)
D = grid_dijkstra(S, si, sj)
print(D[ti][tj] if D[ti][tj] != INF else -1)
# print(*D, sep='\n')

# unionfindで連結成分切り出してから、連結成分をまたぐときだけ+1するdfsかな?

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def read_map_as(H, replace={'#': 1, '.': 0}, pad=None):
    '''
    文字列のmapを置換して読み込み。デフォでは#→1,.→0
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            # 内包表記はpypyでは若干遅いことに注意
            # #numpy使うだろうからこれを残しておくけど
    else:  # paddingする
        ret = [[pad] * (W + 2)]  # Wはどっかで定義しておくことに注意
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


def grid_dijkstra(grid, si: int, sj: int):
    '''grid上のdijkstra法。gridはそこに入るときにかかるコスト
    si,sj は開始の座標。'''
    from heapq import heappop, heappush
    H = len(grid)
    W = len(grid[0])
    D = [[-1] * W for _ in [0] * H]  # -1がINFを意味する
    que = [(0, si, sj)]
    D[si][sj] = 0
    while que:
        c, i, j = heappop(que)
        D[i][j] = min(D[i][j], c, key=lambda x: 1000000000 if x == -1 else x)
        for di, dj in product([-2, -1, 0, 1, 2], repeat=2):
            ni, nj = i + di, j + dj
            if not (0 <= ni < H and 0 <= nj < W) or D[ni][nj] != -1 or ni == nj == 0 or grid[ni][nj] == 1:
                continue
            if (di == 0 and abs(dj) == 1) or (dj == 0 and abs(di) == 1):  # 歩いて行ける
                nc = c
            else:  # ワープして行ける
                nc = c + 1
            heappush(que, (nc, ni, nj))
    return D


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b

# もし歩くだけなら簡単
# ワープをどう処理する？
# もし周囲5*5を候補にするなら24*10**6 んー間に合うか微妙


H, W = ints()
si, sj = mina(*ints())
ti, tj = mina(*ints())
S = read_map_as(H)
D = grid_dijkstra(S, si, sj)
print(D[ti][tj])
# print(*D, sep='\n')

# unionfindで連結成分切り出してから、連結成分をまたぐときだけ+1するdfsかな?

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque

    INF = float('inf')

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

    t = [[INF] * W for _ in range(H)]
    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])

    while q:
        h, w = q.popleft()
        a = t[h][w]
        if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
            q.appendleft((h - 1, w))
            t[h - 1][w] = a
        if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
            q.appendleft((h + 1, w))
            t[h + 1][w] = a
        if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
            q.appendleft((h, w - 1))
            t[h][w - 1] = a
        if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
            q.appendleft((h, w + 1))
            t[h][w + 1] = a

        for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
            for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                if S[i][j] == '#':
                    continue
                if t[i][j] <= a + 1:
                    continue
                t[i][j] = a + 1
                q.append((i, j))

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


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1<<20)
h,w=[int(x) for x in input().split()]
ch,cw=[int(x) for x in input().split()]
dh,dw=[int(x) for x in input().split()]
ch-=1
cw-=1
dh-=1
dw-=1

s=[]
for _ in range(h):
    s.append(list(input()))

nxt=[[ch,cw,0]]
#再起
def rcl(y,x,now):
    
    if y==dh and x==dw:
        print(now)
        exit()
    
    if s[y][x]=='#':
        return
    
    s[y][x]='#'
    # 四方を見る
    for i in range(4):
        yy,xx=-1,0
        if i==1:yy,xx=0,1
        if i==2:yy,xx=1,0
        if i==3:yy,xx=0,-1
        
        if y+yy<0 or h<=y+yy or x+xx<0 or w<=x+xx:
            continue
        if s[y+yy][x+xx]=='#':
            continue
        
        rcl(y+yy,x+xx,now)
    #5*5
    for i in range(-2,3):
        for j in range(-2,3):
            if i==0 and j==0:
                continue
            if y+i<0 or h<=y+i or x+j<0 or w<=x+j:
                continue
            if s[y+i][x+j]=='.':
                nxt.append([y+i,x+j,now+1])
                s[y+i][x+j]=now+1


idx=0
while idx<len(nxt):
    i=nxt[idx]
    idx+=1
    if i[0]==dh and i[1]==dw:
        print(i[2])
        exit()
    rcl(i[0],i[1],i[2])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = float('inf')

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

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

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

Submission status: Time Limit Exceeded

Solution code:
h,w = list(map(int,input().split()))
sx, sy = list(map(int,input().split()))
gx, gy = list(map(int,input().split()))
maze = [list(input()) for _ in range(h)]
sx -= 1; sy -= 1; gx -= 1; gy -= 1

mx = [0,1,0,-1]
my = [1,0,-1,0]
mazemap = [[10**9]*w for _ in range(h)]
from collections import deque
q = deque()
nq = deque()
q.append([sx,sy,0])

while q or nq:
    x,y,z = q.popleft() if q else nq.popleft()
    if x == gx and y == gy:
        ans = z
        break
    fast = 0
    for i in range(4):
        nx = x + mx[i]; ny = y + my[i]
        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and mazemap[nx][ny] > z:
            q.append([nx,ny,z])
            mazemap[nx][ny] = z
            fast += 1
    if fast < 3:
        for i in range(-2,3):
            for j in range(-2,3):
                nx = x+i; ny = y+j
                if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and mazemap[nx][ny] > z+1:
                    nq.append([nx,ny,z+1])
                    mazemap[nx][ny] = z+1
else:
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = list(map(int,input().split()))
sx, sy = list(map(int,input().split()))
gx, gy = list(map(int,input().split()))
maze = [list(input()) for _ in range(h)]
sx -= 1; sy -= 1; gx -= 1; gy -= 1

mx = [0,1,0,-1]
my = [1,0,-1,0]
mazemap = [[10**9]*w for _ in range(h)]
from collections import deque
q = deque()
nq = deque()
q.append([sx,sy,0])

while q or nq:
    x,y,z = q.popleft() if q else nq.popleft()
    if x == gx and y == gy:
        ans = z
        break
    fast = 0
    for i in range(4):
        nx = x + mx[i]; ny = y + my[i]
        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and mazemap[nx][ny] > z:
            q.append([nx,ny,z])
            mazemap[nx][ny] = z
            fast += 1
    if fast < 4:
        for i in range(-2,3):
            for j in range(-2,3):
                nx = x+i; ny = y+j
                if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and mazemap[nx][ny] > z+1:
                    nq.append([nx,ny,z+1])
                    mazemap[nx][ny] = z+1
else:
    ans = -1

print(ans)

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())
base = ["#" *(w+4)]
base.append("#" * (w+4))
for n in range(h):
    base.append("##" + input() + "##")
base.append("#" * (w+4))
base.append("#" * (w+4))
ans = [[-1] * (w+4) for _ in range(h+4)]
for j in range(w+4):
    for i in range(h+4):
        if base[i][j] == "#":
            ans[i][j] = -2
ch+=1; cw+=1
dh+=1; dw+=1
ans[ch][cw] = 0
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
move2 = [
    [-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]
    ]
q = deque([[ch, cw]])
one_time = deque([])
while len(q) > 0:
    x, y = q.popleft()
    one_time.append([x, y])
    for i, j in move:
        v1, v2 = x+i, y+j
        if ans[v1][v2] == -1:
            ans[v1][v2] = ans[x][y]
            q.append([v1, v2])
    if len(q) == 0:
        while len(one_time) > 0:
            x2, y2 = one_time.popleft()
            for i, j in move2:
                v1, v2 = x2+i, y2+j
                if ans[v1][v2] == -1:
                    ans[v1][v2] = ans[x2][y2] + 1
                    q.append([v1, v2])
print(ans[dh][dw])

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())
base = ["#" *(w+4)]
base.append("#" * (w+4))
for n in range(h):
    base.append("##" + input() + "##")
base.append("#" * (w+4))
base.append("#" * (w+4))
ans = [[-1] * (w+4) for _ in range(h+4)]
for j in range(w+4):
    for i in range(h+4):
        if base[i][j] == "#":
            ans[i][j] = -2
ch+=1; cw+=1
dh+=1; dw+=1
ans[ch][cw] = 0
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
move2 = [
    [-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]
    ]
q = deque([[ch, cw]])
one_time = deque([])
while q:
    x, y = q.popleft()
    one_time.append([x, y])
    for i, j in move:
        v1, v2 = x+i, y+j
        if ans[v1][v2] == -1:
            ans[v1][v2] = ans[x][y]
            q.append([v1, v2])
    if len(q) == 0:
        while one_time:
            x2, y2 = one_time.popleft()
            for i, j in move2:
                v1, v2 = x2+i, y2+j
                if ans[v1][v2] == -1:
                    ans[v1][v2] = ans[x2][y2] + 1
                    q.append([v1, v2])
print(ans[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
h,w = list(map(int,input().split()))
sx, sy = list(map(int,input().split()))
gx, gy = list(map(int,input().split()))
maze = [list(input()) for _ in range(h)]
sx -= 1; sy -= 1; gx -= 1; gy -= 1

mx = [0,1,0,-1]
my = [1,0,-1,0]
mazemap = [[10**9]*w for _ in range(h)]
from collections import deque
q = deque()
nq = deque()
q.append([sx,sy,0])

while q or nq:
    x,y,z = q.popleft() if q else nq.popleft()
    if x == gx and y == gy:
        ans = z
        break
    for i in range(4):
        nx = x + mx[i]; ny = y + my[i]
        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and mazemap[nx][ny] > z:
            q.append([nx,ny,z])
            mazemap[nx][ny] = z
    for i in range(-2,3):
        for j in range(-2,3):
            nx = x+i; ny = y+j
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and mazemap[nx][ny] > z+1:
                nq.append([nx,ny,z+1])
                mazemap[nx][ny] = z+1
else:
    ans = -1

print(ans)