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:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W = getNM()
Ch, Cw = getNM()
Dh, Dw = getNM()
maze = [input() for i in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

# ワープを最低で何回使うか
# 上下左右2つ向こうまでの範囲内でワープできる
# 隣接する'.'が領域

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

pos = deque([[Ch, Cw]])
dp = [[-1] * W for i in range(H)]
dp[Ch][Cw] = 0

while len(pos) > 0:
    y, x = pos.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 歩いて移動
        if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] == "." and (dp[ny][nx] == -1 or dp[y][x] < dp[ny][nx]):
            pos.append([ny, nx])
            dp[ny][nx] = dp[y][x]
    # ワープ
    for i in range(-2, 3):
        for j in range(-2, 3):
            wy = y + i
            wx = x + j
            # 歩いて移動不可能でないと使わない
            if 0 <= wx < W and 0 <= wy < H and maze[wy][wx] == "." and (dp[wy][wx] == -1 or dp[y][x] + 1 < dp[wy][wx]):
                pos.append([wy, wx])
                dp[wy][wx] = dp[y][x] + 1

print(dp[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(1000000)
from collections import deque

# スペース区切りの整数の入力
H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())

#配列の入力
S = [list(input()) for _ in range(H)]
MAX = float('inf')
lst = [[MAX for _ in range(W)] for _ in range(H)]

def dfs(h ,w, warp_flg, warp_num):
    if h > H-1 or w > W-1 or h < 0 or w < 0:
        return
    if S[h][w] == '#':
        return
    
    if warp_num < lst[h][w]:
        lst[h][w] = warp_num
    else:
        return
    
    dfs(h-1, w, False, warp_num)
    dfs(h+1, w, False, warp_num)
    dfs(h, w-1, False, warp_num)
    dfs(h, w+1, False, warp_num)

    for i in range(-2,3):
        for j in range(-2, 3):
            if i == 0 and j == 0:
                continue
            if i == -1 and j == 0:
                continue
            if i == 1 and j == 0:
                continue
            if i == 0 and j == 1:
                continue
            if i == 0 and j == -1:
                continue

            dfs(h+i, w+j, True, warp_num+1)

dfs(Ch-1, Cw, False, 0)
dfs(Ch+1, Cw, False, 0)
dfs(Ch, Cw-1, False, 0)
dfs(Ch, Cw+1, False, 0)

for i in range(-2,3):
    for j in range(-2, 3):
        if i == 0 and j == 0:
            continue
        if i == -1 and j == 0:
            continue
        if i == 1 and j == 0:
            continue
        if i == 0 and j == 1:
            continue
        if i == 0 and j == -1:
            continue
        dfs(Ch+i, Cw+j, True, 1)

if lst[Dh][Dw] == MAX:
    print(-1)
else:
    print(lst[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

H = 0
W = 0
table = None


def search(h, w, cnt):
    global H, W, table

    if(type(table[h][w]) is int and table[h][w] < cnt):
        return

    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, 1), (-1, 2),
             (0, -2), (0, 2),
             (1, -2), (1, -1), (1, 1), (1, 2),
             (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

    for k in range(len(move)):
        i, j = move[k]
        if h+i < 0 or w+j < 0 or h+i >= H or w+j >= W:
            continue
        if table[h+i][w+j] == '.':
            table[h+i][w+j] = cnt
            search(h+i, w+j, cnt)
        elif table[h+i][w+j] != '#' and table[h+i][w+j] > cnt:
            table[h+i][w+j] = cnt
            search(h+i, w+j, cnt)

    for k in range(len(move2)):
        i, j = move2[k]
        if h+i < 0 or w+j < 0 or h+i >= H or w+j >= W:
            continue
        if table[h+i][w+j] == '.':
            table[h+i][w+j] = cnt+1
            search(h+i, w+j, cnt+1)
        elif table[h+i][w+j] != '#' and table[h+i][w+j] > cnt+1:
            table[h+i][w+j] = cnt+1
            search(h+i, w+j, cnt+1)


def main(input, print):
    global H, W, table
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    table = [[] for _ in range(H)]
    for i in range(H):
        table[i] = list(input().strip())
    table[Ch-1][Cw-1] = 0
    search(Ch-1, Cw-1, 0)
    if(table[Dh-1][Dw-1] == '.'):
        print(-1)
    else:
        print(table[Dh-1][Dw-1])


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Time Limit Exceeded

Solution code:
from queue import deque
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

h,w = map(int,stdin.readline().rstrip().split())
ch,cw = map(int,stdin.readline().rstrip().split())
dh,dw = map(int,stdin.readline().rstrip().split())
inf = 10**10

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

def main():
    li = [["" for i in range(w)]for j in range(h)]

    for i in range(h):
        s = stdin.readline().rstrip()
        for j in range(w):
            li[i][j] = s[j]

    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    que = deque()

    mx = []
    my = []

    for i in range(-2,3):
        for j in range(-2,3):
            if i == 0 and j == 0:
                continue
            mx.append(i)
            my.append(j)

    lin = [[inf for i in range(w)]for j in range(h)]
    lin[ch][cw] = 0#ここをスタートの座標に変えること
    que.append((ch,cw))#ここもスタートの座標に変えること

    while que:
        k = que.popleft()
        x = k[0]
        y = k[1]

        for i,j in zip(dx,dy):
            nx = x + i
            ny = y + j
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            elif li[nx][ny] == "#" :
                continue
            else:
                if lin[nx][ny] > lin[x][y]:
                    if (nx,ny) not in que:
                        que.append((nx,ny))
                    lin[nx][ny] = lin[x][y]# 直接行ける
        
        # 魔法の力をもってすれば行ける
        for i,j in zip(mx,my):
            nx = x + i
            ny = y + j
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            elif li[nx][ny] == "#" :
                continue
            else:
                if lin[nx][ny] > lin[x][y]+1:
                    if (nx,ny) not in que:
                        que.append((nx,ny))
                    lin[nx][ny] = lin[x][y]+1

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
from itertools import combinations

input = sys.stdin.readline


def main():
    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 = [None] * (H + 4)
    S[0] = S[1] = S[-1] = S[-2] = "#" * (W + 4)
    for h in range(2, H + 2):
        S[h] = "".join(["##", input().rstrip(), "##"])

    CC = [[-1] * (W + 4) for _ in range(H + 4)]
    CC_i = 0
    for h in range(2, H + 2):
        for w in range(2, W + 2):
            if CC[h][w] != -1: continue
            if S[h][w] == "#": continue
            queue = deque([(h, w)])
            while queue:
                h, w = queue.popleft()
                CC[h][w] = CC_i
                for i, j in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                    y, x = h + i, w + j
                    if CC[y][x] != -1: continue
                    if S[y][x] == "#": continue
                    queue.append((y, x))
            CC_i += 1

    CC_S = CC[Ch][Cw]
    CC_G = CC[Dh][Dw]

    G = [[False] * CC_i for _ in range(CC_i)]
    for h in range(2, H + 2):
        for w in range(2, W + 2):
            CC_list = []
            for i in (0, 1, 2):
                for j in (0, 1, 2):
                    y, x = h + i, w + j
                    CC_to = CC[y][x]
                    if CC_to == -1: continue
                    CC_list.append(CC_to)
            if len(CC_list) >= 2:
                for a, b in combinations(CC_list, r=2):
                    G[a][b] = G[b][a] = True

    ans = -1
    visited_CC = [False] * CC_i
    queue = deque([(CC_S, 0)])
    while queue:
        cc, n_warp = queue.popleft()
        visited_CC[cc] = True
        if cc == CC_G:
            ans = n_warp
            break
        for i in range(CC_i):
            if not G[cc][i]: continue
            if visited_CC[i]: continue
            queue.append((i, n_warp + 1))

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from heapq import heappop, heappush

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

    S = [['#'] * (W + 4)]
    tmp = ['#'] * (W + 4)
    S.append(tmp)

    for _ in range(H):
        tmp = ['#', '#'] + list(input()) + ['#']
        S.append(tmp)

    tmp = ['#'] * (W + 4)
    S.append(tmp)
    S.append(tmp)
    # print (*S, sep = '\n')

    INF = 10 ** 9

    G = [[INF] * (W + 4) for _ in range(H + 4)] 

    move1 = ((1, 0), (-1, 0), (0, 1), (0, -1))

    pque = [(0, Ch + 1, Cw + 1)]
    G[Ch + 1][Cw + 1] = 0

    while pque:
        xy = heappop(pque)
        tmp, x, y = xy[0], xy[1], xy[2]
        # print (tmp, x, y)
        if G[x][y] < tmp: #すでに小さい
            continue

        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx = x + dx
                ny = y + dy
                if dx == 0 and dy == 0:
                    continue
                if S[nx][ny] == '.': #道の時
                    if (dx, dy) in move1:
                        if G[nx][ny] > tmp:
                            G[nx][ny] = tmp
                            heappush(pque, (tmp, nx, ny))
                    else:
                        if G[nx][ny] > tmp + 1:
                            G[nx][ny] = tmp + 1
                            heappush(pque, (tmp + 1, nx, ny))

    # print (*G, sep = '\n')

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
import math

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

tobool = lambda s: s == "#"

S = [
  list(map(tobool, input())) for _ in range(H)
]
visited_m = [[False for w in range(W) ] for h in range(H)]
cost_m = [[math.inf for w in range(W) ] for h in range(H)]

def enum_moveA(Ch, Cw):
  return [(Ch-1, Cw), (Ch+1, Cw), (Ch, Cw-1), (Ch, Cw+1)]

def enum_moveB(Ch, Cw):
  return [
    (Ch-2, Cw-2), (Ch-2, Cw-1), (Ch-2, Cw), (Ch-2, Cw+1), (Ch-2, Cw+2),
    (Ch-1, Cw-2), (Ch-1, Cw-1), (Ch-1, Cw+1), (Ch-1, Cw+2),
    (Ch, Cw-2), (Ch, Cw+2),
    (Ch+1, Cw-2), (Ch+1, Cw-1), (Ch+1, Cw+1), (Ch+1, Cw+2),
    (Ch+2, Cw-2), (Ch+2, Cw-1), (Ch+2, Cw), (Ch+2, Cw+1), (Ch+2, Cw+2),
  ]

heap = []
heapq.heappush(heap, (0, Ch, Cw))
while True:
  if len(heap) == 0:
    break
  visited_m[Ch][Cw] = True
  c_cost, Ch, Cw = heapq.heappop(heap)
  for h, w in enum_moveA(Ch, Cw):
    if 0 <= h <H and 0 <= w <W:
      tmp_cost = cost_m[h][w]
      visited = visited_m[h][w]
      kabe = S[h][w]
      if c_cost + 0 < tmp_cost and not visited and not kabe:
        cost_m[h][w] = c_cost + 0
        heapq.heappush(heap, (c_cost + 0, h, w))
        
  for h, w in enum_moveB(Ch, Cw):
    if 0 <= h <H and 0 <= w <W:
      tmp_cost = cost_m[h][w]
      visited = visited_m[h][w]
      kabe = S[h][w]
      if c_cost + 1 < tmp_cost and not visited and not kabe:
        cost_m[h][w] = c_cost + 1
        heapq.heappush(heap, (c_cost + 1, h, w))
    
total_cost = cost_m[Dh][Dw]
if total_cost < math.inf:
  print(total_cost)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
sys.setrecursionlimit(500*500)
import itertools
from collections import Counter,deque

def main():
    h,w = map(int, input().split())
    start = list(map(int, input().split()))
    qy, qx = start[0]-1,start[1]-1
    end = list(map(int, input().split()))
    ey, ex = end[0]-1, end[1]-1

    s = [input().rstrip() for i in range(h)]

    visited = [[0]*w for i in range(h)]

    que = deque([(qx,qy)])
    visited[qy][qx] = 1
    visit = set()

    dx = (1, -1, 0, 0)
    dy = (0, 0, 1, -1)
    cnt = 0

    dxw = (-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,0,1,1,1,1,2,2,2,2,2)
    dyw = (-2,-1,0,1,2,-2,-1,1,2,-2,0,2,-2,-1,1,2,-2,-1,0,1,2)

    while True:
        while len(que) > 0:
            x,y = que.popleft()
            visited[y][x] = 1
            visit.add((x,y))

            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]

                if 0<=nx<w and 0<=ny<h and s[ny][nx]=='.' and visited[ny][nx]==0:
                    que.append((nx,ny))
                    visited[ny][nx] = 1
        if visited[ey][ex] == 0:
            cnt += 1
            flg = False
            for g in visit:
                if visited[g[1]][g[0]] == 1:
                    for k in range(21):
                        nx = g[0] + dyw[k]
                        ny = g[1] + dxw[k]
                        if 0<=nx<w and 0<=ny<h and s[ny][nx]=='.' and visited[ny][nx]==0:
                            flg = True
                            que.append((nx,ny))
                            break
                if flg == True:
                        break
            if flg == False:
                print(-1)
                exit()

        else:
            print(cnt)
            exit()

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

H, W = map(int, input().split())
C = [int(i) for i in input().split()]
D = [int(i) for i in input().split()]
maze = [["#"]+[i for i in input()]+["#"] for j in range(H)]
maze = [["#"]*(W+2)] + maze + [["#"]*(W+2)]
dp = [[-1 for i in range(W+2)] for j in range(H+2)]

dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]
dp[C[0]][C[1]] = 0
pos = deque([[C[0], C[1], 0]])

while len(pos) > 0:

    h, w, count = pos.popleft()

    for dh, dw in dir:
        if maze[h+dh][w+dw] == "#":
            continue
        elif dp[h+dh][w+dw] == -1 or count < dp[h+dh][w+dw]:
            dp[h+dh][w+dw] = count
            pos.append([h+dh, w+dw, count])

    for next_h in range(max(0, h-2), min(H, h+2)+1):
        for next_w in range(max(0, w-2), min(W, w+2)+1):
            if maze[next_h][next_w] == "#":
                continue
            elif dp[next_h][next_w] == -1 or count + 1 < dp[next_h][next_w]:
                dp[next_h][next_w] = count + 1
                pos.append([next_h, next_w, count+1])

print(dp[D[0]][D[1]])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())

field = [[c for c in input()] for i in range(H)]
movement = ((1, 0), (-1, 0), (0, 1), (0, -1))
def main():
    clusters = []
    sg = [-1, -1]
    c = 0
    checked = set()
    for y in range(H):
        for x in range(W):
            if (x, y) in checked or field[y][x] == '#':
                continue
            visited = set()
            queue = [(x, y)]
            while queue:
                now_x, now_y = queue.pop()
                if (now_x, now_y) in visited:
                    continue
                visited.add((now_x, now_y))
                for dx, dy in movement:
                    nx, ny = now_x+dx, now_y+dy
                    if (nx, ny) not in visited and 0<=nx<W and 0<=ny<H and field[ny][nx]=='.':
                        queue.append((nx, ny))
            if (sx-1, sy-1) in visited:
                sg[0] = c
            if (gx-1, gy-1) in visited:
                sg[1] = c
            checked = checked | visited
            clusters.append(sorted(list(visited)))
            c+=1

    def nearp(c1, c2):
        min1, max1 = c1[0][0], c1[-1][0]
        min2, max2 = c2[0][0], c2[-1][0]
        if max2 + 2 < min1 or max1 + 2 < min2:
            return False
        
        for x1, y1 in c1:
            for x2, y2 in c2:
                if abs(x1 - x2) < 3:
                    if abs(y1 - y2) < 3:
                        return True
        
        return False

    path = {i:[] for i in range(len(clusters))}

    for i in range(len(clusters)-1):
        for j in range(i+1, len(clusters)):
            if nearp(clusters[i], clusters[j]):
                path[i].append(j)
                path[j].append(i)

    start, goal = sg
    visited = set()
    queue = deque()
    queue.append((start, 0))
    result = -1
    while queue:
        now, dist = queue.popleft()
        if now == goal:
            result = dist
            break
        if now in visited:
            continue
        visited.add(now)
        for nxt in path[now]:
            if nxt not in visited:
                queue.append((nxt, dist+1))

    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n , m = map(int, input().split())
ch , cw = map(int, input().split())
dh , dw = map(int, input().split())
maze = [['#','#']+list(input())+['#','#'] for i in range(n)]
maze = [['#']*(m+4)]+[['#']*(m+4)]+maze+[['#']*(m+4)]+[['#']*(m+4)]

step = [(0,1),(1,0),(-1,0),(0,-1)]
warp_u = [(-2,0)]
warp_d = [(2,0)]
warp_r = [(0,2)]
warp_l = [(0,-2)]
warp_ur = [(-1,1),(-2,1),(-2,2),(0,2),(-2,0),(-1,2)]
warp_dr = [(2,0),(2,1),(2,2),(1,1),(1,2),(0,2)]
warp_ul = [(-2,0),(-2,-1),(-2,-2),(-1,-1),(-1,-2),(0,-2)]
warp_dl = [(2,0),(2,-1),(2,-2),(1,-1),(1,-2),(0,-2)]



warp=0

v = [[-1]*(m+4) for i in range(n+4)]
d = deque()
d.append((ch+1,cw+1,0,0,0))
v[ch+1][cw+1]=0
while d:
    y,x,wa,ex_y,ex_x=d.popleft()
    for dy,dx in step:
        if dy==ex_y*(-1) and dx==ex_x*(-1):
            continue
        if maze[y+dy][x+dx]=='.' and (v[y+dy][x+dx]==-1 or v[y+dy][x+dx]>wa):
            v[y+dy][x+dx]=wa
            d.append((y+dy,x+dx,wa,dy,dx))
        elif maze[y+dy][x+dx]=='#' and dy>0 and maze[y][x+1]=='.' and maze[y][x-1]=='.':
            for dy2,dx2 in warp_d:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dy>0 and maze[y][x+1]=='#':
            for dy2,dx2 in warp_dr:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dy>0 and maze[y][x-1]=='#':
            for dy2,dx2 in warp_dl:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dx>0 and maze[y+1][x]=='.' and maze[y-1][x]=='.':
            for dy2,dx2 in warp_r:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dx>0 and maze[y+1][x]=='#':
            for dy2,dx2 in warp_dr:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dx>0 and maze[y-1][x]=='#':
            for dy2,dx2 in warp_ur:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dy<0 and maze[y][x+1]=='.' and maze[y][x-1]=='.':
            for dy2,dx2 in warp_u:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dy<0 and maze[y][x+1]=='#':
            for dy2,dx2 in warp_ur:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dy<0 and maze[y][x-1]=='#':
            for dy2,dx2 in warp_ul:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dx<0 and maze[y+1][x]=='.' and maze[y-1][x]=='.':
            for dy2,dx2 in warp_l:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dx<0 and maze[y+1][x]=='#':
            for dy2,dx2 in warp_dl:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
        elif maze[y+dy][x+dx]=='#' and dx<0 and maze[y-1][x]=='#':
            for dy2,dx2 in warp_ul:
                if maze[y+dy2][x+dx2]=='.' and (v[y+dy2][x+dx2]==-1 or v[y+dy2][x+dx2]>v[y][x]+1):
                    v[y+dy2][x+dx2]=v[y][x]+1
                    d.append((y+dy2,x+dx2,wa+1,dy2,dx2))
print(v[dh+1][dw+1])

Submission status: Time Limit Exceeded

Solution code:
H,W = list(map(int,input().split()))
Ch,Cw = list(map(int,input().split()))
Dh,Dw = list(map(int,input().split()))
Ch,Cw,Dh,Dw = Ch-1,Cw-1,Dh-1,Dw-1

from collections import deque
maze = []
for i in range(H):
    maze.append(list(input()))
times = [[-1]*W for i in range(H)]

dh = [1, 0, -1, 0]
dw = [0, 1, 0, -1]
que = deque([])
que.append((Ch, Cw))
times[Ch][Cw] = 0
cnt = 0
flag = 0
while flag==0:
    loc = deque([])
    while que:
        p = que.popleft()
        wallflag = 0
        if p[0] == Dh and p[1] == Dw:
            times[Dh][Dw] = cnt
            flag = 1
            break
        for i in range(4):
            nh = p[0] + dh[i]
            nw = p[1] + dw[i]
            if (0<=nh<H)and(0<=nw<W)and(maze[nh][nw]!="#")and(times[nh][nw]==-1):
                que.append((nh, nw))
                times[nh][nw] = cnt
            if (0<=nh<H)and(0<=nw<W)and(maze[nh][nw]=="#"):
                wallflag = 1
        if wallflag ==1:
            loc.append(p)
    que = deque([])
    while loc:
        p = loc.popleft()
        for i in range(-2,3):
            for j in range(-2,3):
                nh = p[0] + i
                nw = p[1] + j
                if (0<=nh<H)and(0<=nw<W)and(maze[nh][nw]!="#")and(times[nh][nw]==-1):
                    que.append((nh, nw))
    if len(que)==0:
        break
    cnt += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
C0, C1 = map(int, input().split())
D0, D1 = map(int, input().split())

ARR = []

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


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

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

    q = deque()

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

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


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

                        if status[_hIndex][_wIndex] == -1:
                            status[_hIndex][_wIndex] = tmpIndex
                            q.append((_hIndex, _wIndex, tmpIndex))
                        else:
                            if status[_hIndex][_wIndex] > tmpIndex:
                                status[_hIndex][_wIndex] = tmpIndex
                                q.append((_hIndex, _wIndex, tmpIndex))

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



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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())

cy -= 1
cx -= 1
gy -= 1
gx -= 1

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

q = deque()
# x, y, 累積移動距離, ブロック通過数, ワープ利用数
q.append((cx, cy, 0, 0, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, c, d, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    # print(x, y, c, d, e)
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            q.append((nx, ny, c+1, d, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            # print("warp", dx, dy)
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e+1)
                    continue
                # print("warp append")
                q.append((nx, ny, c+1, d, e+1))

print(-1 if ans == float("inf") else ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())

h,w=NM()
sh,sw=NM()
sh-=1
sw-=1
gh,gw=NM()
gh-=1
gw-=1
l=[[j for j in input()] for i in range(h)]
from collections import deque
def dijkstra(s,n,g):
    d = [float('inf') for i in range(n+1)]
    pq = deque([s])
    d[s]=0
    while pq:
        u = pq.popleft()
        dist=d[u]
        for v,cost in edge[u]:
            if d[v]<=dist+cost:
                continue
            d[v]=dist+cost
            pq.append(v)
    return d[g]
edge=[[] for i in range(h*w)]

def v(i,j):
    return (j*h+i)
def f(i,j,x,y):
    if x>=h or y>=w or x<0 or y<0:
        return
    if l[x][y]==".":
        edge[v(i,j)].append((v(x,y),1))
        edge[v(x,y)].append((v(i,j),1))
for x in range(h*w):
        i=x%h
        j=x//h
        if l[i][j]=="#":
            continue
        if i<h-1:
            if l[i+1][j]==".":
                edge[v(i,j)].append((v(i+1,j),0))
                edge[v(i+1,j)].append((v(i,j),0))
        if j<w-1:
            if l[i][j+1]==".":
                edge[v(i,j)].append((v(i,j+1),0))
                edge[v(i,j+1)].append((v(i,j),0))
        f(i,j,i+1,j+1)
        f(i,j,i+2,j+1)
        f(i,j,i+2,j+2)
        f(i,j,i+1,j+2)
        f(i,j,i+2,j)
        f(i,j,i,j+2)
        
        f(i,j,i-1,j+1)
        f(i,j,i-2,j+1)
        f(i,j,i-2,j+2)
        f(i,j,i-1,j+2)


d=dijkstra(v(sh,sw),h*w,v(gh,gw))
if d==float("inf"):
    print(-1)
else:
    print(d)