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:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

h,w = lr()
ch,cw = lr()
ch-=1
cw-=1
dh, dw = lr()
dh-=1
dw-=1
s = [input() for i in range(h)]
visited = [[inf for j in range(w)] for i in range(h)]
visited[ch][cw] = 0
q = deque([[ch, cw]])
dir = [[0,1], [0,-1], [-1,0], [1,0]]
while q:
    y,x = q.popleft()
    c = visited[y][x]
    for dy,dx in dir:
        ny,nx = y+dy,x+dx
        if 0<=ny<h and 0<=nx<w:
            if s[ny][nx] == '.':
                if visited[ny][nx] > c:
                    visited[ny][nx] = c
                    q.append([ny,nx])
    # ワープ処理
    ty, tx = y-2, x-2
    for i in range(5):
        for j in range(5):
            ny, nx = ty + i, tx + j
            if 0<=ny<h and 0<=nx<w:
                if s[ny][nx]=='.':
                    if visited[ny][nx] > c+1:
                        visited[ny][nx] = c+1
                        q.append([ny,nx])
if visited[dh][dw] != inf:
    print(visited[dh][dw])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
inf=float("inf")


def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque([])

    x,y=C
    x -=1
    y -=1
    queue.append([x,y])
    D[x][y]=0

    for i in range(h):
        for j in range(w):
            if S[i][j]=="#":
                color[i][j]="black"

    while len(queue)>0:
        x,y=queue.popleft()
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]!="black":
                    D[X][Y]=min(D[X][Y],D[x][y])
                    color[X][Y]="gray"
                    queue.append([X,Y])

        for i in range(max(0,x-3),min(h,x+3)):
            for j in range(max(0,y-3),min(w,y+3)):
                X,Y=i,j
                if 0<=X<h and 0<=Y<w:
                    if color[X][Y]!="black":
                        D[X][Y]=min(D[X][Y],D[x][y]+1)
                        color[X][Y]="gray"
                        queue.append([X,Y])
        color[x][y]="black"

    return D[G[0]-1][G[1]-1]


h,w=map(int,input().split())
C=list(map(int,input().split()))
G=list(map(int,input().split()))
S=[list(input()) for _ in range(h)]

D=BFS()
print(D if D!=inf else -1)

Submission status: Time Limit Exceeded

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  H,W=LI()
  Ch,Cw=LI()
  Dh,Dw=LI()
  Ch-=1
  Cw-=1
  Dh-=1
  Dw-=1
  field=[S() for _ in range(H)]

  q=collections.deque()
  q.append((Ch,Cw,0))
  ans=[[inf]*W for _ in range(H)]
  while q:
    # for x in ans:
    #   print(x)
    # print()
    y,x,cnt=q.popleft()
    if ans[y][x]<=cnt:
      continue
    ans[y][x]=cnt
    if y==Dh and x==Dw:
      continue

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny<H and 0<=nx<W:
        if field[ny][nx]=='.':
          q.append((ny,nx,cnt))
        else:
          if dy==1 and dx==0:
            for i in range(0,2):
              for j in range(-2,3):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    if ans[nny][nnx]>cnt+1:
                      q.append((nny,nnx,cnt+1))
          elif dy==0 and dx==1:
            for i in range(-2,3):
              for j in range(0,2):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    if ans[nny][nnx]>cnt+1:
                      q.append((nny,nnx,cnt+1))
          elif dy==-1 and dx==0:
            for i in range(-1,1):
              for j in range(-2,3):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    if ans[nny][nnx]>cnt+1:
                      q.append((nny,nnx,cnt+1))
          elif dy==0 and dx==-1:
            for i in range(-2,3):
              for j in range(-1,1):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    if ans[nny][nnx]>cnt+1:
                      q.append((nny,nnx,cnt+1))

  x=ans[Dh][Dw]
  if x==inf:
    return -1
  return x

# main()
print(main())

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):
                warp.append((i, j))
        h = []
        self.set(start[1], start[0], 0)
        heappush(h, (cx, cy))
        while h:
            cx, cy = heappop(h)
            cc = self.get(cx, cy)
            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, (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, (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



        # for i in range(1, self.h+1):
        #     for j in range(1, self.w+1):
        #         cx, cy = j, i
        #         for dx, dy in move_eight:
        #             nx, ny = dx + cx, dy + cy

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:
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
road_map = []
for i in range(h):
    road = input()
    road_map.append(road)

queue = [[ch-1,cw-1,0]]
used_map = [[-1]*w for _ in range(h)]

while queue != []:
    dot = queue.pop()
    if dot[0] < 0 or dot[1] < 0 or dot[0] >= h or dot[1] >= w:
        continue
    if used_map[dot[0]][dot[1]] > -1 and used_map[dot[0]][dot[1]] <= dot[2]:
        continue
    if road_map[dot[0]][dot[1]] == "#":
        continue
    used_map[dot[0]][dot[1]] = dot[2]

    queue.append([dot[0],dot[1]-1,dot[2]])
    queue.append([dot[0],dot[1]+1,dot[2]])
    queue.append([dot[0]+1,dot[1],dot[2]])
    queue.append([dot[0]+1,dot[1],dot[2]])

    for x in range(-2,3,1):
        for y in range(-2,3,1):
            queue.append([dot[0]+x,dot[1]+y,dot[2]+1])
    
print(used_map[dh-1][dw-1])

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())

c = [[] for i in range(h)]

for i in range(h):
    c[i] = input()
d = [[10000000 for i in range(w)] for j in range(h)]
    
d[ch-1][cw-1] = 0
que = deque([[ch-1,cw-1]])

dx = [1,0,-1,0]
dy = [0,1,0,-1]
ddx = [1,1,-1,-1,2,2,2,2,2,1,1,0,0,-1,-1,-2,-2,-2,-2,-2]
ddy = [1,-1,1,-1,2,1,0,-1,-2,2,-2,2,-2,2,-2,2,1,0,-1,-2]
    
while que:
    y,x = que.popleft()
        
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[y][x] != '#':
            if d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.append([ny,nx])
                
    for k in range(20):
        nx = x + ddx[k]
        ny = y + ddy[k]
            
        if 0<=nx and nx<w and 0<=ny and ny<h and c[y][x] != '#':
            if d[ny][nx] > d[y][x] + 1:
                d[ny][nx] = d[y][x] + 1
                que.append([ny,nx])

if d[dh-1][dw-1] == 10000000:
    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())
dh_, dw_ = map(int, input().split())

mvs = [(-1,0),(1,0),(0,1),(0,-1)]
fs = []

for i in range(H):
    r = list(input())
    fs.append(r)

INF = 1<<50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
from collections import deque
q = deque([])
q.append((ch-1,cw-1))
while len(q)>0:
    h,w = q.popleft()
    cnt = dps[h][w]
    # 先に魔法を使っておく
    for i in range(-2,3):
        for j in range(-2,3):
            if 0<=h+i<H and 0<=w+j<W:
                if fs[h+i][w+j] == ".":
                    if dps[h+i][w+j] <= cnt:continue
                    q.append((h+i,w+j))
                    dps[h+i][w+j] = min(dps[h+i][w+j], cnt + 1)
    for dh, dw in mvs:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] <= cnt:continue
            if fs[hn][wn] == ".":
                q.append((hn, wn))
                dps[hn][wn] = min(dps[h][w], cnt)

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W = list(map(int,input().split()))
Ch,Cw = list(map(int,input().split()))
Dh,Dw = list(map(int,input().split()))

maze = [["#"]*(W+4)]
maze.append(["#"]*(W+4))
for i in range(H):
    row = ["#","#"]
    row.extend(list(input()))
    row.append("#")
    row.append("#")
    maze.append(row)
maze.append(["#"]*(W+4))
maze.append(["#"]*(W+4))
warp = [[114514]*(W+4) for i in range(H+4)]

queue = deque()
queue.append((Ch+1,Cw+1))
warp[Ch+1][Cw+1] = 0
move_one = set(((1,0),(0,1),(-1,0),(0,-1)))
while queue:
    y,x = queue.popleft()
    for i in range(-2,3):
        for j in range(-2,3):
            if i == 0 and j == 0:
                continue
            ny,nx = y+i,x+j
            if maze[ny][nx] == "#":
                continue
            if (i,j) in move_one:
                warp[ny][nx] = warp[y][x]
                queue.appendleft((ny,nx))
                maze[ny][nx] = "#"
            else:
                if warp[ny][nx] == 114514:
                    warp[ny][nx] = min(warp[ny][nx],warp[y][x]+1)
                    queue.append((ny,nx))

if warp[Dh+1][Dw+1] == 114514:
    print(-1)
else:
    print(warp[Dh+1][Dw+1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

INF = 10 ** 8

H, W = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
MAP = []
for _ in range(H):
    MAP.append(list(input()))
d = [[INF for i in range(W)] for j in range(H)]
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]
tx_y = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i != 0 or j != 0)]

def dfs(x, y, cnt):
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt:
            d[nx][ny] = cnt
            dfs(nx, ny, cnt)
    for i, j in tx_y:
        nx = x + i
        ny = y + j
        if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt + 1:
            d[nx][ny] = cnt + 1
            dfs(nx, ny, cnt + 1)

d[C[0]-1][C[1]-1] = 0
dfs(C[0]-1, C[1]-1, 0)

if d[D[0]-1][D[1]-1] == INF:
    print(-1)
else:
    print(d[D[0]-1][D[1]-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000) 
H,W = map(int,input().split())
C = list(map(int,input().split()))
C[0] -= 1; C[1] -= 1
D = list(map(int,input().split()))
D[0] -= 1; D[1] -= 1
S = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp =list(temp)
  S.append(temp)
#print(S)
reach = [[INF]*W for _ in range(H)]
reach[C[0]][C[1]] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
def dfs(v,score):
  #if reach[v[0]][v[1]] < score:
  #  return

  for i in range(4):
    nx = v[0] + dxdy[i][0]
    ny = v[1] + dxdy[i][1]
    if 0<=nx<H and 0<=ny<W and S[nx][ny] == "." and reach[nx][ny] > score:
      reach[nx][ny] = min(score,reach[nx][ny])
      u = [nx,ny]
      dfs(u,score)

  for i in range(5): #0~4
    for j in range(5):
      mx = v[0]-2 + i
      my = v[1]-2 + j
      if i == 2 and j == 2:
        continue
      if mx < 0 or mx >= H or my < 0 or my >= W or S[mx][my] == "#":
        continue
      if reach[mx][my] < score+1: #すでにこのスコア以下でいける。
        continue
      reach[mx][my] = min(score+1,reach[mx][my])
      p = [mx,my]
      dfs(p,score+1)
dfs(C,0)
#print(reach)
#print(reach[D[0]][D[1]])
if reach[D[0]][D[1]] == INF:
  print(-1)
else:
  print(reach[D[0]][D[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(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if s[ny][nx] == '.' and d[ny][nx] > D:
                d[ny][nx] = D
                heappush(H, (D, nx, ny))
    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 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:
from collections import deque


h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
tizu = [input() for _ in range(h)]
inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
dh -= 1
dw -= 1
check[ch][cw] = 0
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]
magic = [[1, 1], [-1, 1], [1, -1], [-1, -1], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]
    ,[1, -2], [1, 2], [0, -2], [0, 2], [-1, -2], [-1, 2], [-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2]]

queue.append([ch, cw])
queue.append(0)
while queue:
    pos = queue.popleft()
    dd = queue.popleft()
    flg = False
    for dy, dx in walk:
        n_h = pos[0] + dy
        n_w = pos[1] + dx
        if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
            continue
        if check[n_h][n_w] <= dd:
            continue
        if tizu[n_h][n_w] == "#":
            flg = True
            continue
        check[n_h][n_w] = dd
        queue.append([n_h, n_w])
        queue.append(dd)
        
    if flg:
        for dy, dx in magic:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)

if check[dh][dw] == inf:
    print(-1)
else:
    print(check[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
H, W = map(int, input().split())
ch, cw = map(lambda x:int(x)-1, input().split())
dh, dw = map(lambda x:int(x)-1, input().split())
S = [list(input()) for _ in range(H)]

moves = ((1, 0), (0, 1), (0, -1), (-1, 0))
moves2 = ((1, 0), (0, 1), (0, -1), (-1, 0), (1, 1), (-1, 1), (1, -1), (-1, -1), 
          (2, 0), (2, 2), (2, 1), (2, -1), (2, -2), 
          (1, 2), (1, -2), (0, 2), (0, -2), (-1, 2), (-1, -2), 
          (-2, 0), (-2, 1), (-2, 2), (-2, -1), (-2, -2))
T = S[:]

def dfs(y, x, prey, prex, c):
  T[y][x] = c
  for dy, dx in moves:
    ny = y + dy
    nx = x + dx
    if 0 <= ny < H and 0 <= nx < W:
      if T[ny][nx] == "." or (T[ny][nx] != "." and T[ny][nx] != "#" and  T[ny][nx] > c):
        if prey != ny or prex != nx:
          dfs(ny, nx, y, x, c)

  for dy, dx in moves2:
    ny = y + dy
    nx = x + dx
    if 0 <= ny < H and 0 <= nx < W:
      if T[ny][nx] == "." or (T[ny][nx] != "." and T[ny][nx] != "#" and  T[ny][nx] > c):
        if prey != ny or prex != nx:
          dfs(ny, nx, y, x, c+1)

c = 0
dfs(ch, cw, -1, -1, c)


if T[dh][dw] == "." or T[dh][dw] == "#":
  print(-1)
else:
  print(T[dh][dw])

Submission status: Time Limit Exceeded

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

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


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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import deque
    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
    maze = [list(input()) for _ in range(H)]

    que = deque([(Ch,Cw,0)])
    adjecents = [(1,0),(0,1),(-1,0),(0,-1)]
    while que:
        h,w,worp = que.popleft()
        if maze[h][w] == "#" or (maze[h][w]!="." and maze[h][w] <= worp):
            continue
        else:
            maze[h][w] = worp
            for a,b in adjecents:
                nxh,nxw = h+a,w+b
                if 0<=nxh < H and 0<=nxw < W:
                    que.append((nxh,nxw,worp))
            
            for i in range(-2,3,1):
                for j in range(-2,3,1):
                    nxh,nxw = h+i,w+j
                    if 0<=nxh < H and 0<=nxw < W:
                        que.append((nxh,nxw,worp+1))
    if maze[Dh][Dw] == "#" or maze[Dh][Dw] == ".":
        print(-1)
    else:
        print(maze[Dh][Dw])
main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

h,w = map(int,input().split())
sh,sw = map(int,input().split())
gh,gw = map(int,input().split())
s = [input() for _ in range(h)]

sh-=1; sw-=1; gh-=1; gw-=1;

INF = 10**7
dist = [[INF]*w for _ in range(h)]
dist[sh][sw] = 0
q = [(0,sh,sw)]
flag = 0
while q:
    
    d,vsh,vsw = heapq.heappop(q)
    
    for dh in range(-2,3):
        for dw in range(-2,3):
            newh = vsh+dh
            neww = vsw+dw
            if newh<0 or h<=newh or neww<0 or w<=neww: continue
            if dh == 0 and dw==0: continue
            if s[newh][neww] == "#": continue
                
            if abs(dh)+abs(dw)==1:
                if dist[newh][neww] > d:
                    dist[newh][neww] = d
                    if newh == gh and neww == gw: flag
                    heapq.heappush(q,(d,newh,neww))
            else:
                if dist[newh][neww] > d+1:
                    dist[newh][neww] = d+1
                    heapq.heappush(q,(d+1,newh,neww))
    if flag: break
if dist[gh][gw] == INF: print(-1)
else: print(dist[gh][gw])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())

maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]

maze2 = [[-1]*W for _ in range(H)]

def mizutamari(maze,maze2,y,x,ct):
    maze2[y][x] = ct
    stack = deque([[y,x]])
    while stack:
        i,j = stack.pop()
        for ni,nj in [(0,1),(1,0),(0,-1),(-1,0)]:
            if not 0 <= i + ni < H or not 0 <= j + nj < W:
                continue
            if maze[i+ni][j+nj] == "." and maze2[i+ni][j+nj] == -1:
                maze2[i+ni][j+nj] = ct
                stack.append([i+ni,j+nj])
    return maze2

def func(maze,maze2):
    ct = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == "." and maze2[h][w] == -1:
                maze2 = mizutamari(maze,maze2,h,w,ct)
                ct += 1
    return maze2,ct

maze2,ct = func(maze,maze2)

g = [[] for i in range(ct)]
g2 = [[0]*ct for _ in range(ct)]
for i in range(ct):
    g2[i][i] = 1
for h in range(H):
        for w in range(W):
            if maze2[h][w] != -1:
                for i in range(-2,3):
                    for j in range(-2,3):
                        if not 0 <= i + h < H or not 0 <= j + w < W:
                            continue
                        if maze2[h+i][w+j] != -1 and \
                            not g2[maze2[h][w]][maze2[h+i][w+j]]:
                            g[maze2[h][w]].append((1,maze2[h+i][w+j]))
                            g[maze2[h+i][w+j]].append((1,maze2[h][w]))
                            g2[maze2[h][w]][maze2[h+i][w+j]] = 1
                            g2[maze2[h+i][w+j]][maze2[h][w]] = 1


#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge): #s:始点,g:グラフ
    #始点sから各頂点への最短距離
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]: #既に最小距離が確定しているなら
            continue
        v = minedge[1] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)


start = maze2[sh-1][sw-1]
goal = maze2[gh-1][gw-1]

res = dijkstra_heap(start,g)

if res[goal] == float("inf"):
    print(-1)
else:
    print(res[goal])