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 math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self, start, goal):
        grid = self.grid
        cy, cx = start
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        warp = []
        for i in range(-2, 3):
            for j in range(-2, 3):
                if (i, j) not in move and (i != 0 or j != 0):
                    warp.append((i, j))
        # print(warp)
        h = []
        self.set(start[1], start[0], 0)
        heappush(h, (0, cx, cy))
        while h:
            cc, cx, cy = heappop(h)

            for dx, dy in move:

                nx, ny = dx + cx, dy + cy
                if self.getgrid(nx, ny) == "#":
                    continue
                if self.get(nx, ny) > cc:
                    self.set(nx, ny, cc)
                    heappush(h, (cc, nx, ny))

            for dx, dy in warp:
                nx, ny = dx + cx, dy + cy
                if nx < 0 or nx > self.w + 1 or ny < 0 or ny > self.h + 1:
                    continue
                if self.getgrid(nx, ny) == "#":
                    continue
                if self.get(nx, ny) > cc + 1:
                    self.set(nx, ny, cc + 1)
                    heappush(h, (cc + 1, nx, ny))
        # print(warp)
        # self.show()
        # self.showsomejoin(self.grid)
        ans = self.get(goal[1], goal[0])
        if ans == INF:
            print(-1)
            return
        else:
            print(ans)
            return





def solve():
    h, w = getList()
    start = getList()
    goal = getList()
    G = TwoDimGrid(h, w)
    G.search(start, goal)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

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 = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch, Cw))

dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
wps = [
    [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 0), (-1, -1), (-1, 1)],
    [(2, 2), (2, -1), (2, 0), (2, 1), (2, 0), (1, -1), (1, 1)],
    [(-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (-1, 1), (1, 1)],
    [(-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2), (-1, -1), (1, -1)]
]

while q:
    d, i, j = heappop(q)
    used.add((i, j))

    if D[i][j] > d:
        D[i][j] = d
    else:
        continue

    for k, (di, dj) in enumerate(dirs):
        _i = i + di
        _j = j + dj
        if 0 <= _i < H and 0 <= _j < W:
            if (_i, _j) in used:
                continue
            used.add((i, j))
            if S[_i][_j] == '.':
                heappush(q, (d, _i, _j))
            else:
                for di, dj in wps[k]:
                    _i = i + di
                    _j = j + dj
                    if 0 <= _i < H and 0 <= _j < W and (_i, _j) not in used and S[_i][_j] == '.':
                        heappush(q, (d+1, _i, _j))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def ok(i, j):
    return 0 <= i < H and 0 <= j < W and S[i][j] == '.'

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
C_h -= 1
C_w -= 1
D_h, D_w = map(int, input().split())
D_h -= 1
D_w -= 1
S = []
for _ in range(H):
    row = list(input())
    S.append(row)
if S[D_h][D_w] == '#':
    print(-1)
else:
    queue = [(0, (C_h, C_w))]
    seen = {(C_h, C_w)}
    while queue:
        score, cur = heapq.heappop(queue)
        if cur == (D_h, D_w):
            print(score)
            break
        i, j = cur
        for offset in (1, -1):
            i_next = i + offset
            j_next = j + offset
            if ok(i_next, j) and (score, i_next, j) not in seen:
                heapq.heappush(queue, (score, (i_next, j)))
                seen.add((score, i_next, j))
            if ok(i, j_next) and (score, i, j_next) not in seen:
                heapq.heappush(queue, (score, (i, j_next)))
                seen.add((score, i, j_next))

        for a in [-2, -1, 0, 1, 2]:
            for b in [-2, -1, 0, 1, 2]:
                if a == b == 0:
                    continue
                i_jump = i + a
                j_jump = j + b
                if ok(i_jump, j_jump) and (score + 1, i_jump, j_jump) not in seen:
                    heapq.heappush(queue, (score + 1, (i_jump, j_jump)))
                    seen.add((score + 1, i_jump, j_jump))
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import heapq

h, w = map(int, input().split())
cx, cy = map(lambda x: int(x) - 1, input().split())
dx, dy = map(lambda x: int(x) - 1, input().split())
s = [input() for _ in range(h)]
c = [[10**6] * w for _ in range(h)]


def bfs():
    d = ((1, 0), (-1, 0), (0, 1), (0, -1))
    d2 = (
        (-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),
    )
    hp = []

    heapq.heappush(hp, (0, (cx, cy)))
    c[cx][cy] = 0

    while hp:
        cp, (
            x,
            y,
        ) = heapq.heappop(hp)
        if (x, y) == (dx, dy):
            c[x][y] = cp
            break
        for i in range(4):
            nx = x + d[i][0]
            ny = y + d[i][1]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                    ny] > cp:
                heapq.heappush(hp, (cp, (nx, ny)))
                c[nx][ny] = cp
        cp += 1
        for i in range(20):
            nx = x + d2[i][0]
            ny = y + d2[i][1]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and c[nx][
                    ny] > cp:
                c[nx][ny] = cp
                heapq.heappush(hp, (cp, (nx, ny)))

    return c[dx][dy] if c[dx][dy] < 10**6 else -1


print(bfs())

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from heapq import heapify, heappush, heappop
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


def dijkstra(path, N, start):
    visited = [False] * N
    que = [(0, start)]
    heapify(que)  # 始点aから各頂点への(距離, 頂点ID)
    dist = [-1] * N  # 始点aから各頂点への距離
    dist[start] = 0  # 始点aからaへの距離は0
    while que:
        d, v = heappop(que)  # 始点から最短距離の頂点を(確定ノード)を取り出す
        visited[v] = True  # 確定フラグを立てる
        # 接続先ノードの情報を更新する
        for d, to in path[v]:
            cost = dist[v] + d
            if dist[to] < 0 or cost < dist[to]:
                dist[to] = cost
                if not visited[to]:
                    heappush(que, (cost, to))
    return dist


# MAGIC = ((-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2),
#          (-2, -1), (-1, -1), (0, -1), (1, -1), (2, -1),
#          (-2, 0), (-1, 0), (0, 0), (1, 0), (2, 0),
#          (-2, 1), (-1, 1), (0, 1), (1, 1), (2, 1),
#          (-2, -2), (-1, 2), (0, 2), (1, 2), (2, 2))

MAGIC = ((-2, -2), (-1, -2), (1, -2), (2, -2),
         (-2, -1), (-1, -1),  (1, -1), (2, -1),
         (-2, 1), (-1, 1), (1, 1), (2, 1),
         (-2, -2), (-1, 2), (1, 2), (2, 2))
H, W = zz()
c_h, c_w = zz()
d_h, d_w = zz()
board = []
N = H*W
for i in range(H):
    tmp = S()
    # N += tmp.count('.')
    board.append(tmp)

path = [[] for _ in range(N)]
for h in range(H):
    for w in range(W):
        if board[h][w] == '.':
            for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                new_h = h + dy
                new_w = w + dx
                if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                    continue
                if(board[new_h][new_w] == '.'):
                    path[h*W + w].append((0, new_h*W + new_w))
                    path[new_h*W + new_w].append((0, h*W + w))
                else:
                    #  隣は壁
                    new_h = h + dy*2
                    new_w = w + dx*2
                    if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                        continue
                    if(board[new_h][new_w] == '.'):  # 2個先は存在
                        path[h*W + w].append((1, new_h*W + new_w))
                        path[new_h*W + new_w].append((1, h*W + w))
                for dy, dx in MAGIC:
                    new_h = h + dy
                    new_w = w + dx
                    if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                        continue
                    if(board[new_h][new_w] == '.'):
                        path[h*W + w].append((1, new_h*W + new_w))
                        path[new_h*W + new_w].append((1, h*W + w))

c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1
dist = dijkstra(path, N, c_h*W + c_w)
print(dist[d_h*W+d_w])

"""

print(board)
que = deque([[c_h, c_w]])
visited = []
# bfs()
while que:
    h, w = que.popleft()
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_h = h + dy
        new_w = w + dx
        if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
            continue
        if board[new_h][new_w] == '.':  # セルが白('.')であるのと同義
            que.append((new_h, new_w))

    print(h, w)
"""

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
nx,ny=map(int,input().split())
gx,gy=map(int,input().split())
maze=[input()for i in range(h)]
from heapq import heapify, heappop, heappush
seen=set()
gx-=1;gy-=1

hq=[(0,nx-1,ny-1)]
while hq:
    c,x,y=heappop(hq)
    seen.add(w*x +y)
    if x==gx and y==gy:print(c);exit()
    if x and w*(x-1)+y not in seen and maze[x-1 ][y]!="#":
        heappush(hq,(c,x-1,y))
    if y and w*x+y-1 not in seen and maze[x][y-1]!="#":
        heappush(hq,(c,x,y-1))
    if x+1<h  and w*(x+1)+y not in seen and maze[x+1][y]!="#":
        heappush(hq,(c,x+1,y))
    if y+1<w  and w*x+y+1 not in seen and maze[x][y+1]!="#":
        heappush(hq,(c,x,y+1))
    for i in range(max(0,x-2),min(h,x+3)):
        for j in range(max(0,y-2),min(w,y+3)):
            if i==x and j==y:continue
            if maze[i][j]=="."and w*i + j not in seen:
                heappush(hq,(c+1,i,j))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w = LI()
ch, cw = LI()
dh, dw = LI()
s = [list(input()) for _ in range(h)]

dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
d = [[10**10] * w for _ in range(h)]
d[ch-1][cw-1] = 0
H = []
heappush(H, (0, cw-1, ch-1))
while H:
    D, x, y = heappop(H)
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx, ny = x + i, y + j
            if 0 <= nx < w and 0 <= ny < h:
                if abs(i) + abs(j) <= 1:
                    if s[ny][nx] == '.' and d[ny][nx] > D:
                        d[ny][nx] = D
                        heappush(H, (D, nx, ny))
                else:
                    if s[ny][nx] == '.' and d[ny][nx] > D + 1:
                        d[ny][nx] = D + 1
                        heappush(H, (D + 1, nx, ny))
if d[dh-1][dw-1] == 10**10:
    print(-1)
else:
    print(d[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int, input().split())
ch,cw=map(int, input().split())
ch-=1
cw-=1
dh,dw=map(int, input().split())
dh-=1
dw-=1
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
for i in range(h):
    for j in range(w):
        if grid[i][j]==0:
            col+=1
            stack=deque([(i,j)])
            while stack:
                nowi,nowj=stack.popleft()
                grid[nowi][nowj]=col
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))
es=[set([]) for _ in range(col)]
visited=[-1]*col
for i in range(h):
    for j in range(w):
        now=grid[i][j]
        if now!=-1: 
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if 0<=i+x<h and 0<=j+y<w:
                        nex=grid[i+x][j+y]
                        if nex!=-1 and now!=nex:
                            es[now-1].add(nex-1)
start=grid[ch][cw]-1
end=grid[dh][dw]-1
if start==end:
    print(0)
    exit()

stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=visited[now]+1
            stack.append(e)
#print(grid)
print(visited[end])

Submission status: Time Limit Exceeded

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

xy=[(1,0),(-1,0),(0,1),(0,-1)]
wp=[(-1,-1),(-1,1),(1,1),(1,-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)]
#t=[[0]*5 for i in range(5)]
#x=y=2
#for i,j in wp:
#    i+=x
#    j+=x
#    t[i][j]=7
#for i in t:
#    print(i)
#exit()

(-1,-1),(-1,1),(1,1),(1,-1)
(2,0),(-2,0),(0,2),(0,-2)
(2,0),(-2,0),(0,2),(0,-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
#d[d1-1][d2-1]="g"
p=set([(c1-1,c2-1)])
ans=-1
while len(p):
    a,b=p.pop()
    for x,y in xy:
        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]:
                d[x][y]=d[a][b]
                p.add((x,y))
    for x,y in wp:
        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(-1 if (d[d1-1][d2-1]=="#" or d[d1-1][d2-1]==".") else d[d1-1][d2-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    H,W = LMIIS()
    Ch,Cw = LMIIS()
    Ch -= 1
    Cw -= 1
    Dh,Dw = LMIIS()
    Dh -= 1
    Dw -= 1
    S = []
    for i in range(H):
        S.append(input())
    
    num_warp = []
    for i in range(H):
        num_warp.append([INF]*W)
    num_warp[Ch][Cw] = 0
    
    targets = deque([(Ch,Cw)])

    def check_and_move(y,x,n):
        if 0 <= y < H and 0 <= x < W and S[y][x] == '.' and n < num_warp[y][x]:
            num_warp[y][x] = n
            return True
        return False

    # BFS
    while targets:
        y,x = targets.pop()
        # ワープで行ける範囲 -> 歩いて行ける範囲　の順に追加
        num_currrent_warp = num_warp[y][x]
        for y2,x2 in[
                (y-2,x-2),(y-2,x-1),(y-2,x),(y-2,x+1),(y-2,x+2),
                (y-1,x-2),(y-1,x-1),(y-1,x+1),(y-2,x+2),
                (y,x-2),(y,x+2),
                (y+1,x-2),(y+1,x-1),(y+1,x+1),(y+1,x+2),
                (y+2,x-2),(y+2,x-1),(y+2,x),(y+2,x+1),(y+2,x+2)
            ]:

            if check_and_move(y2,x2,num_currrent_warp+1):
                targets.append((y2,x2))
        
        for y2,x2 in [(y-1,x),(y,x+1),(y+1,x),(y,x-1)]:
            if check_and_move(y2,x2,num_currrent_warp):
                    targets.append((y2,x2))

    ans = num_warp[Dh][Dw]
    print(-1 if ans == INF else ans)


    
main()

Submission status: Time Limit Exceeded

Solution code:
# 1マス移動するごとに周囲5*5を見て現在+1を書き込む? ◎
# それとも移動できるまで移動してから、次を探しに行く?
# 幅優先か、深さ優先か? 幅優先

# AGC033Aからコピペ

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

start = list(map(int, input().split()))
goal = list(map(int, input().split()))

masu = [input() for i in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

inf = 10 ** 7
distance = [[inf for _ in range(w)] for _ in range(h)]

from collections import deque

queue = deque([])
distance[start[0]-1][start[1]-1] = 0
queue.append((start[0]-1, start[1]-1, 0))

while True:
    if len(queue) == 0:
        break
    now = queue.popleft()
    now_h = now[0]
    now_w = now[1]
    now_distance = now[2]
    now_distance_matrix = distance[now_h][now_w]

    if now_distance > now_distance_matrix:
        # もう小さい数字がdistanceに書かれているので
        continue
    distance[now_h][now_w] = now_distance

    for hh in range(now_h - 2, now_h + 2+1):
        for ww in range(now_w - 2, now_w + 2+1):
            if not (0 <= hh <= h-1 and 0 <= ww <= w-1):
                continue
            if masu[hh][ww] == '#':
                continue
            if distance[hh][ww] <= now_distance:
                continue
            queue.append((hh, ww, now_distance + 1))

    for i in range(4):
        next_h = now_h + dx[i]
        next_w = now_w + dy[i]
        if not (0 <= next_h <= h-1 and 0 <= next_w <= w-1):
            continue
        if masu[next_h][next_w] == '#':
            continue
        if distance[next_h][next_w] <= now_distance:
            continue
        else:
            distance[next_h][next_w] = now_distance
            queue.appendleft((next_h, next_w, now_distance))

t = distance[goal[0]-1][goal[1]-1]
if t == inf:
    print(-1)
else:
    print(t)

# print(distance)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

H, W = map(int, input().split())
ori = list(map(int, input().split()))
dis = list(map(int, input().split()))
S = [0] * H
for i in range(H):
    S[i] = input()

D = 10 ** 7

def co_num(h, w):
    return h * W + w

row = []
col = []
dist = []
for h in range(H):
    for w in range(W):
        if S[h][w] == '#': continue
        for hh in range(-2, 3):
            if not 0 <= h + hh < H: continue
            for ww in range(-2, 3):
                if not (0 <= h + hh < H and 0 <= w + ww < W): continue
                if hh == ww == 0: continue
                if S[h+hh][w+ww] == '#': continue
                if abs(hh) + abs(ww) == 1:
                    d = 1
                else:
                    d = D
                row.append(co_num(h, w))
                col.append(co_num(h+hh, w+ww))
                dist.append(d)
                
d = dijkstra(csr_matrix((dist, (row, col)), shape=[H*W, H*W]), directed=True, indices=co_num(ori[0]-1, ori[1]-1))

if d[co_num(dis[0]-1, dis[1]-1)] == np.inf:
    print(-1)
else:
    print(int(d[co_num(dis[0]-1, dis[1]-1)] // D))

# d.reshape([H, W])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import collections
    import sys
    input = sys.stdin.readline
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [input() for i in range(H)]

    q = collections.deque()
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    G = [[H*W]*W for i in range(H)]
    # q.append((Ch, Cw))
    G[Ch][Cw] = 0
    flag = True
    # while(q):
    #     x, y = q.popleft()
    #     # for i, j in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
    #     #     if 0 <= i <= H and 0 <= j <= W and S[i][j] != '#' and G[i][j] == -1:
    #     if x == Dh and y == Dw:
    #         print(G[x][y])
    #         flag = False
    #         break
    #     for i in range(x-2, x+3):
    #         if 0 <= i <= H-1:
    #             for j in range(y-2, y+3):
    #                 if 0 <= j <= W-1:
    #                     if S[i][j] != '#':
    #                         if abs(i-x) + abs(j-y) == 1 and G[i][j] > G[x][y]:
    #                             q.append((i, j))
    #                             G[i][j] = G[x][y]
    #                         elif G[i][j] > G[x][y] + 1:
    #                             q.append((i, j))
    #                             G[i][j] = G[x][y] + 1

    #     # for i in range(H):
    #     #     print(G[i])
    #     # print()
    r = set()
    ss = []
    start = -1
    goal = -1
    D = collections.defaultdict(int)
    for i in range(H):
        for j in range(W):
            if (i, j) in r or S[i][j] == '#':
                continue
            q.append((i, j))
            ss.append(set([(i, j)]))
            r.add((i, j))
            L = len(ss)
            D[(i, j)] = L-1
            while(q):
                x, y = q.popleft()
                for k, l in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
                    if 0 <= k <= H-1 and 0 <= l <= W-1 and S[k][l] != '#' and (k, l) not in r:
                        r.add((k, l))
                        D[(k, l)] = L - 1
                        q.append((k, l))
                        ss[-1].add((k, l))
            if (Ch, Cw) in ss[-1]:
                start = L - 1
            if (Dh, Dw) in ss[-1]:
                goal = L - 1

    if D[Ch, Cw] == D[(Dh, Dw)]:
        print(0)
        exit(0)

    G = [set() for i in range(L)]
    for id, X in enumerate(ss):
        for x, y in X:
            for i in range(x-2, x+3):
                if 0 <= i <= H-1:
                    for j in range(y-2, y+3):
                        if 0 <= j <= W-1:
                            if D[(i, j)] != id:
                                G[id].add(D[(i, j)])
    r = set()
    r.add(start)
    q.append((start, 0))
    while(q):
        x, c = q.popleft()
        if x == goal:
            print(c)
            flag = False
            break
        for y in G[x]:
            if y in r:
                continue
            else:
                r.add(y)
                q.append((y, c+1))
    # print(G)
    if flag:
        print(-1)


main()

Submission status: Time Limit Exceeded

Solution code:

import heapq
h,w = map(int, raw_input().split())
s = tuple(map(lambda x:int(x)-1 , raw_input().split()))
t = tuple(map(lambda x:int(x)-1 , raw_input().split()))

heap = [(0,s)]
r = {}
mat = [raw_input() for _ in range(h)]

def neighbors(u,mat):
	ret = []
	for i in [-2,-1,0,+1,+2]:
		for j in [-2,-1,0,+1,+2]:
			v= (u[0]+i,u[1]+j)
			if 0<=v[0]< len(mat) and 0<=v[1]< len(mat[0]) and mat[v[0]][v[1]] == '.':
				if v != u:
					ret.append(v)
	return ret


while(heap):
	d,u = heapq.heappop(heap)
	if u in r and d > r[u]: continue
	r[u] = min(r[u] if u in r else +float('inf'), d)
	if u == t:
		break

	for v in [(u[0],u[1]-1),(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]+1)]:
		if 0 <= v[0] < h and 0 <= v[1] < w and mat[v[0]][v[1]] == '.':
			if (v not in r) or r[v] > d:
				heapq.heappush(heap,(d,v))
				r[v] = d
	for v in neighbors(u,mat):
		
		if 0 <= v[0] < h and 0 <= v[1] < w:
			if (v not in r) or r[v] > d:
				heapq.heappush(heap,(d+1,v))
				r[v] = d + 1

print (r[t] if t in r else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
S = [[s for s in input()]for _ in range(h)]
que = deque([[C[0]-1,C[1]-1]])
que2 = deque([])
dd = [-1,1]
d1 = [-2,-1,0,1,2]
reach = [[False for _ in range(w)]for _ in range(h)]
reach[C[0]-1][C[1]-1]=True
ans = 0
while que:
    u = que.popleft()
    x,y = u
    if y < 0 or x < 0 or y >= w or x >= h:
        continue
    if S[x][y] == '#':
        continue
    else:
        reach[x][y] = True
    for d in dd:
        xx = x+d
        yy = y+d
        if 0 <= xx < h:
            if S[xx][y] == '.':
                if not reach[xx][y]:
                    que.append([xx,y])
                    reach[xx][y] = True
            else:
                for i in d1:
                    for j in d1:
                        s,t = x+i,y+j
                        if 0<=s<h and 0<=t<w:
                            if S[s][t] == '.' and not reach[s][t]:
                                que2.append([s,t])  
        if 0 <= yy < w:
            if S[x][yy] =='.':
                if not reach[x][yy]:
                    que.append([x,yy])
                    reach[x][yy] = True
            else:
                for i in d1:
                    for j in d1:
                        s,t = x+i,y+j
                        if 0<=s<h and 0<=t<w:
                            if S[s][t] == '.' and not reach[s][t]:
                                que2.append([s,t])  
    if reach[D[0]-1][D[1]-1]:
        print(ans)
        exit()    
    if not que:
        que = que2
        que2 = deque([])
        ans += 1
print(-1)

Submission status: Time Limit Exceeded

Solution code:
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())
ch, cw = ch-1, cw-1
dh, dw = dh-1, dw-1

s = [input() for _ in range(h)]

num = np.empty((h,w))
for i in range(h):
    for j in range(w):
        num[i,j] = np.inf

num[dh,dw] = 0
q = deque([[dh,dw]])
walk = [[-1,0],[0,-1],[0,1],[1,0]]
warp = [[-2,i] for i in range(-2,3)] + [[i,-2] for i in range(-1,2)]  + [[i,2] for i in range(-1,2)] + [[2,i] for i in range(-2,3)]

while len(q)>0:
    now = q.popleft()
    for x in walk:
        next_point = [now[0]+x[0], now[1]+x[1]]
        if not (0 <= next_point[0] < h and 0 <= next_point[1] < w ): # 外に出てた場合
            continue
        if s[next_point[0]][next_point[1]] =='.'  and \
            (np.isinf(num[next_point[0],next_point[1]]) or\
            num[next_point[0],next_point[1]] > num[now[0],now[1]]): # まだやってない場合
            num[next_point[0],next_point[1]] = num[now[0],now[1]]
            q.append(next_point)
    for x in warp:
        next_point = [now[0]+x[0], now[1]+x[1]]
        if not (0 <= next_point[0] < h and 0 <= next_point[1] < w ): # 外に出てた場合
            continue
        if s[next_point[0]][next_point[1]] =='.'  and \
            (np.isinf(num[next_point[0],next_point[1]]) or\
            num[next_point[0],next_point[1]] > num[now[0],now[1]]+1): # まだやってない場合
            num[next_point[0],next_point[1]] = num[now[0],now[1]] +1
            q.append(next_point)
if np.isinf(num[ch,cw]):
    print(-1)
else:
    print(int(num[ch,cw]))