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:
from collections import defaultdict,deque

H, W = map(int, input().split())
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S[0] -= 1
S[1] -= 1
G[0] -= 1
G[1] -= 1
c = [input() for i in range(H)]
dist = [[-1]*W for _ in range(H)]

for i in range(H):
    for g in range(W):
        if c[i][g] == "#":
            dist[i][g] = -2

checkList = set()
que = deque()
que.append(S)
dist[S[0]][S[1]] = 0

directions = [(0, -1), (0, 1), (1, 0), (-1, 0)]

cost = 0

while True:
    if len(que) == 0:
        cost += 1
        que = set()
        for h, w in checkList:
            for i in [-2, -1, 0, 1, 2]:
                for g in [-2, -1, 0, 1, 2]:
                    nh = h+i
                    nw = w+g
                    if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                        continue
                    else:
                        if dist[nh][nw] == -1:
                            que.add((nh, nw))
        que = deque(que)
        checkList = set()
        if len(que) == 0:
            print(-1)
            exit()
    else:
        h, w = que.popleft()
        if h == G[0] and w == G[1]:
            print(cost)
            exit()
        checkList.add((h, w))
        for i in range(4):
            nh = h+directions[i][0]
            nw = w+directions[i][1]
            if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                continue
            if dist[nh][nw] == -1:
                que.append((nh, nw))
                dist[nh][nw] = cost

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

ido = [[1,0],[0,1],[-1,0],[0,-1]]

warp = [[2,2],[2,1],[1,2],[0,2],[2,0],[-2,-2],[-2,-1],[-1,-2],[0,-2],[-2,0],[2,-2],[2,-1],[1,-2],[-2,2],[-2,1],[-1,2],[1,1],[1,-1],[-1,1],[-1,-1]]

d = deque()
d.append([C[1]-1,C[0]-1])
cost = [[10000 for i in range(W)] for j in range(H)]
flg = [[-1 for i in range(W)] for j in range(H)]

cost[C[0]-1][C[1]-1] = 0

while d:
    x,y = d.popleft()
    for dx, dy in ido:
        nx = x + dx
        ny = y + dy

        if 0>nx or W<=nx or 0>ny or H<=ny:
            continue

        if  S[ny][nx] == "#":
            continue

        cost[ny][nx] = min(cost[y][x],cost[ny][nx])
        if flg[ny][nx] != -1 :
            continue
        d.append([nx,ny])
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy

        if 0 > nx or W <= nx or 0 > ny or H <= ny:
            continue
        if  S[ny][nx] == "#":
            continue

        cost[ny][nx] = min(cost[y][x]+1, cost[ny][nx])
        if flg[ny][nx] != -1:
            continue
        d.append([nx, ny])
    flg[y][x] = 1
answer = cost[D[0]-1][D[1]-1]
if answer == 10000:
    print(-1)
else:
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
import numpy as np
# input = sys.stdin.buffer.readline
H, W = map(int, input().split())
ch, cw = map(int, input().split())
ch, cw = ch - 1, cw - 1  # 0-indexed
dh, dw = map(int, input().split())
dh, dw = dh - 1, dw - 1  # 0-indexed
# print(f'{ch=}, {cw=}')
S = []
for _ in range(H):
    S.append(list(input()))
S = np.array(S)
# print(f'{S=}')

G = np.full_like(S, -1, dtype='int')
# print(f'{G=}')

current_G = 0
for h in range(H):
    for w in range(W):
        if S[h, w] == '#':
            continue
        if G[h, w] != -1:
            continue
        G[h, w] = current_G
        q = deque([(h, w)])
        while q:
            # print(f'{q=}')
            _h, _w = q.popleft()
            # print(f'{_h=}, {_w=}')
            for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nx = _w + dx
                ny = _h + dy
                # print(f'{nx=}, {ny=}')
                if nx < 0 or ny < 0 or nx >= W or ny >= H:
                    # print(f'fuga {nx=}, {ny=}')
                    continue
                if S[ny, nx] == '#':
                    continue
                if G[ny, nx] != -1:
                    # print(f'hoge')
                    continue
                G[ny, nx] = current_G
                q.append((ny, nx))
        current_G += 1
#         print(f'')
# print(f'{G=}')
# print(f'{current_G=}')

# print(f'start group = {G[ch, cw]=}')
start_group = G[ch, cw]

P = [-1] * (current_G)
P[start_group] = 0
# print(f'{P=}')

g = start_group
GG = deque([start_group])
while GG:
    g = GG.popleft()
    for h in range(H):
        for w in range(W):
            if G[h, w] == g:
                for dx, dy in ((-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)):
                    nx = w + dx
                    ny = h + dy
                    if nx < 0 or ny < 0 or nx >= W or ny >= H:
                        continue
                    if S[ny, nx] == '#':
                        continue
                    _g = G[ny, nx]
                    if P[_g] != -1:
                        continue
                    P[_g] = P[g] + 1
                    GG.append(_g)

# print(f'{P=}')
# print(f'goal group = {G[dh, dw]=}')
ans = P[G[dh, dw]]
print(ans)

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())
S = []
for h in range(H):
    S.append(list(input()))
H -= 1;W -= 1;CH -= 1;CW -= 1;DH -= 1;DW -= 1
from collections import deque
Q = deque([[CH,CW,0]])
ans = 9999999999999999999999
able = False
while Q:
    q = Q.popleft()
    for w in range(-2,3):
        for h in range(-2,3):
            # 場外判定
            # from IPython.core.debugger import Pdb; Pdb().set_trace()
            if q[0] + h >= 0 and q[0] + h <= H and q[1] + w >= 0 and q[1] + w <= W:
                # 壁判定
                if S[q[0]+h][q[1]+w] != '#':
                    # 動かないのは処理しない
                    if w == 0 and h == 0:
                        pass
                    # 徒歩判定(4パターン)
                    elif (w == -1 and h == 0) or (w == 0 and h == -1) or (w == 1 and h == 0) or (w == 0 and h == 1):
                            # ゴールの場合
                            if q[0]+h == DH and q[1]+w == DW:
                                ans = min(ans,q[2])
                                able = True
                            # 未処理の場合
                            elif S[q[0]+h][q[1]+w] == '.':
                                S[q[0]+h][q[1]+w] = str(q[2])
                                Q.append([q[0]+h,q[1]+w,q[2]])
                            # 処理済の場合
                            else:
                                if int(S[q[0]+h][q[1]+w]) > q[2]:
                                    S[q[0]+h][q[1]+w] = str(q[2])
                                    Q.append([q[0]+h,q[1]+w,q[2]])
                    # ワープの場合
                    else:
                        if q[0]+h == DH and q[1]+w == DW:
                            ans = min(ans,q[2]+1)
                            able = True
                        elif S[q[0]+h][q[1]+w] == '.':
                            S[q[0]+h][q[1]+w] = str(q[2]+1)
                            Q.append([q[0]+h,q[1]+w,q[2]+1])
                        else:
                            if int(S[q[0]+h][q[1]+w]) > q[2]+1:
                                S[q[0]+h][q[1]+w] = str(q[2]+1)
                                Q.append([q[0]+h,q[1]+w,q[2]+1])
                            
print(ans) if able else print(-1)

Submission status: Time Limit Exceeded

Solution code:
#d
h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
s = [input() for _ in range(h)]
inf = 99999999
dist = [[inf]* w for i in range(h)]
queue = []
queue.append([ch-1,cw-1])
dist[ch-1][cw-1] = 0

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

wx=[-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
wy=[-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
import sys
warp = 0
wall = []
while True:
    while queue!=[]:
        y,x = map(int, queue.pop())

        if x == dw-1 and y ==dh-1:
            print(dist[y][x])
            sys.exit()

        for i in range(len(dx)):#まず壁探知
            next_x = x +dx[i]
            next_y = y +dy[i]

            if 0 <= next_x < len(s[0]) and 0 <= next_y < len(s):
                if dist[next_y][next_x] == inf: 
                    if s[next_y][next_x] == ".":
                        queue.append([next_y,next_x])
                        dist[next_y][next_x] = dist[y][x]
                    else:
                        wall.append([y,x]) 
    while wall != []:
        y,x = map(int, wall.pop())
        for i in range(len(wx)):
            next_x = x +wx[i]
            next_y = y +wy[i]

            if 0 <= next_x < len(s[0]) and 0 <= next_y < len(s):
                if dist[next_y][next_x] == inf: 
                    if s[next_y][next_x] == ".":
                        queue.append([next_y,next_x])
                        dist[next_y][next_x] = dist[y][x]+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())
s=[0]*h
for i in range(h):
  st=str(input())
  st=list(st)
  s[i]=st
  
from collections import deque
temp=[[999999]*w for i in range(h)]
temp2=[[0]*w for i in range(h)]
temp[ch-1][cw-1]=0
queue = deque([[ch-1, cw-1]])
while queue:  
  x,y=queue.popleft()
  for i,j in [[1,0],[-1,0],[0,1],[0,-1],[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]]:
    xtemp,ytemp=x+i,y+j
    if xtemp<0 or h<=xtemp or ytemp<0 or w<=ytemp or s[xtemp][ytemp]!=".":
      continue
    if temp[xtemp][ytemp]<=temp[x][y]:
      continue
    if (i==1 and j==0) or (i==-1 and j==0) or (i==0 and j==1) or (i==0 and j==-1):
      temp[xtemp][ytemp]=min(temp[xtemp][ytemp],temp[x][y])
    else:
      temp[xtemp][ytemp]=min(temp[xtemp][ytemp],temp[x][y]+1)
    queue.append([xtemp,ytemp])

if temp[dh-1][dw-1]==999999:
  print(-1)
else:
  print(temp[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue

# input
H, W = map(int, sys.stdin.readline().strip().split())
Ch, Cw = map(int, sys.stdin.readline().strip().split())
Dh, Dw = map(int, sys.stdin.readline().strip().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

S = []
for _ in range(H):
    s = str(input())
    S.append(list(s))


# solve
q = queue.Queue()
q.put((Ch, Cw))
fp = [[float('inf')] * W for _ in range(H)]
fp[Ch][Cw] = 0
while True:
    if q.empty():
        break
    uh, uw = q.get()

    for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        vh = uh + dh
        vw = uw + dw

        # 盤上にいるか確認
        if vh < 0 or vh >= H:
            continue
        if vw < 0 or vw >= W:
            continue

        # 壁の確認
        if S[vh][vw] == "#":
            continue

        # 到達済みか確認
        if fp[vh][vw] <= fp[uh][uw]:
            continue

        # 探索候補地に追加
        q.put((vh, vw))
        fp[vh][vw] = fp[uh][uw]

    for dh in range(-2, 3):
        for dw in range(-2, 3):
            vh = uh + dh
            vw = uw + dw

            # 盤上にいるか確認
            if vh < 0 or vh >= H:
                continue
            if vw < 0 or vw >= W:
                continue

            # 壁の確認
            if S[vh][vw] == "#":
                continue

            # 到達済みか確認
            if fp[vh][vw] <= fp[uh][uw] + 1:
                continue

            # 探索候補地に追加
            q.put((vh, vw))
            fp[vh][vw] = fp[uh][uw] + 1


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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
from pprint import pprint


def read():
    H, W = map(int, input().strip().split())
    CH, CW = map(int, input().strip().split())
    DH, DW = map(int, input().strip().split())
    S = [[0 for j in range(W)] for i in range(H)]
    for i in range(H):
        s = list(input().strip())
        for j in range(W):
            if s[j] == "#":
                S[i][j] = -2
            else:
                S[i][j] = -1
    return H, W, CH, CW, DH, DW, S



def bellman_ford(N, G, start, INF=10**7):
    D = [INF] * N
    D[start] = 0
    for k in range(N):
        for i in range(N):
            for j, v in G[i].items():
                if D[j] > D[i] + v:
                    D[j] = D[i] + v
    return D


def solve(H, W, CH, CW, DH, DW, S, INF=10**7):
    DIR = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    # 島を作る
    id = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == -1:
                id += 1
                S[i][j] = id
                q = deque()
                q.append((i, j))
                while q:
                    y, x = q.popleft()
                    for dy, dx in DIR:
                        ny, nx = y+dy, x+dx
                        if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == -1:
                            S[ny][nx] = id
                            q.append((ny, nx))

    start_id = S[CH-1][CW-1]
    goal_id = S[DH-1][DW-1]
    if start_id == goal_id:
        return 0

    # id: 島の数
    N = id
    G = [dict() for i in range(N)]
    # 島を連結する
    for i in range(H):
        for j in range(W):
            source_id = S[i][j]
            if source_id > 0:
                for k in range(i-2, i+3):
                    for l in range(j-2, j+3):
                        if 0 <= k < H and 0 <= l < W:
                            target_id = S[k][l]
                            if target_id > 0 and source_id != target_id:
                                G[source_id-1][target_id-1] = 1
                                G[target_id-1][source_id-1] = 1
    D = bellman_ford(N, G, start=start_id-1, INF=INF)
    if D[goal_id-1] < INF:
        return D[goal_id-1]
    return -1


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

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)]
    dist = [[INF]*w for i in range(h)]

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

    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
            if x==ex  and y== ey: # ゴールまで辿ったら
                break

            for k in range(4): # 上下左右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 i in range(h):
                for j in range(w):
                    if visited[i][j] == 1:
                        for k in range(21):
                            nx = j + dyw[k]
                            ny = i + 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))
            if flg == False:
                print(-1)
                exit()

        else:
            print(cnt)
            exit()

if __name__=="__main__":
    main()

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())
from collections import deque

grid =  ''
grid +=  '#' * (W+4) * 2
for h in range(H):
  S = str(input())
  grid += '#' * 2 + S + '#' * 2
grid +=  '#' * (W+4) * 2

#print(grid)

Dire = [W+4, -W-4, 1, -1]
WAAP_ = [
  -2*(W+4)-2,-2*(W+4)-1,-2*(W+4), -2*(W+4)+1, -2*(W+4)+2, 
  -1*(W+4)-2,-1*(W+4)-1,-1*(W+4), -1*(W+4)+1, -1*(W+4)+2, 
  -2, -1, 1, 2,
  1*(W+4)-2,1*(W+4)-1,1*(W+4), 1*(W+4)+1, 1*(W+4)+2, 
  2*(W+4)-2,2*(W+4)-1,2*(W+4), 2*(W+4)+1, 2*(W+4)+2, 
]
start = 2 * (W+4) + (Ch - 1) * (W+4) + 2 + (Cw - 1)
end = 2 * (W+4) + (Dh - 1) * (W+4) + 2 + (Dw - 1)

#print(start, end)


def WAAP(lst):
  res =  []
  for l in lst:
    for waap_ in  WAAP_:
      l_ = l+ waap_
      if grid[l_] == '.' :
        res.append(l_)
  return list(set(res))
        
        
    

def dfs(wwww, stack):
  fin =  []
  
  while True:
    #print(stack)
    if len(stack) == 0:
      for f in fin:
        grid[f] == '#'
      waap = WAAP(fin)
      return False, waap
      break
    q = stack.pop()
    fin.append(q)
    if q == end:
      return True, wwww
    else:
      for d in Dire:
        new_q = q + d
        if grid[new_q] == '.' and  new_q not in fin:
          stack.append(new_q)
          
          
          
          
def main():
  stack_ = deque([start])
  ans = 0
  while True:
    is_fin, res = dfs(ans, stack_)
    if is_fin:
      print(ans)
      break
    else:
      #print(res)
      if len(res) == 0:
        print(-1)
        break
      stack_ = res
      ans += 1
      
main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(H, W, Ch, Cw, Dh, Dw, data):
    # data = list(data.reshape(-1))
    HEIGHT = H + 4
    WIDTH = W + 4
    N = HEIGHT * WIDTH
    visited = [0] * N
    distance = [0] * N
    jump = [0] * N

    start = (Ch + 1) * WIDTH + (Cw + 1)
    goal = (Dh + 1) * WIDTH + (Dw + 1)
    q = []
    q.append(start)

    currentDistance = 0
    while True:
        while q:
            p = q.pop()
            if p == goal:
                return currentDistance
            if visited[p]:
                continue
            distance[p] = currentDistance
            for dx in [-2, -1, 0, +1, +2]:
                for dy in [-WIDTH * 2, -WIDTH, 0, WIDTH, WIDTH * 2]:
                    jump[p + dx + dy] = currentDistance + 1
            visited[p] = 1
            for d in [-1, +1, -WIDTH, +WIDTH]:
                if data[p + d] and not visited[p + d]:
                    q.append(p + d)

        # no continuous cell
        for i in range(HEIGHT * WIDTH):
            if not data[i]:
                continue
            if visited[i]:
                continue
            # not visited vacant cell
            if jump[i] > 0:
                q.append(i)
        currentDistance += 1
        if not q:
            return -1

    # print(distance)
    # print(visited.reshape((H+4, -1)))


def main():
    # parse input
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    D = [0] * ((H + 4) * (W + 4))
    for i in range(H):
        S = input().strip()
        for j in range(W):
            D[(i + 2) * (W + 4) + (j + 2)] = 1 if S[j] == ord(b".") else 0
    # print(D)
    # for i in range(H + 4):
    #     print(D[i * (H + 4): i * (H + 4) + (W + 4)])
    # data = np.array(list(read().strip()) + [0])
    # data = np.equal(data, 46).reshape((H, W + 1))
    # D = np.zeros((H + 4, W + 4), dtype=np.int8)
    # D[2:2+H, 2:2+W+1] = data
    # print(data)
    # print(D)
    print(solve(H, W, Ch, Cw, Dh, Dw, D))


# tests
T1 = """
4 4
1 1
4 4
..#.
..#.
.#..
.#..
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1
"""

T2 = """
4 4
1 4
4 1
.##.
####
####
.##.
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
-1
"""

T3 = """
4 4
2 2
3 3
....
....
....
....
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
0
"""

T4 = """
4 5
1 2
2 5
#.###
####.
#..##
#..##
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
2
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W = map(int, readline().split())
    sh, sw = map(int, readline().split())
    sh -= 1
    sw -= 1
    gh, gw = map(int, readline().split())
    gh -= 1
    gw -= 1
    S = read().split()
    dist = [[INF] * W for _ in range(H)]
    walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    warp = [(1, 1), (1, -1), (-1, 1), (-1, -1), \
            (2, 0), (2, 1), (2, 2), (2, -1), (2, -1), (2, -2), \
            (-2, 0), (-2, 1), (-2, 2), (-2, -1), (-2, -1), (-2, -2), \
            (0, 2), (1, 2), (-1, 2), (0, -2), (1, -2), (-1, -2)]
    Q = deque()
    Q.append((sh, sw))
    dist[sh][sw] = 0
    while Q:
        h, w = Q.popleft()
        if h == gh and w == gw:
            continue
        flag = False
        for dh, dw in walk:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if S[nh][nw] != '#':
                    if dist[nh][nw] > dist[h][w]:
                        dist[nh][nw] = dist[h][w]
                        Q.append((nh,nw))
                else:
                    flag = True
        if flag:
            for dh, dw in warp:
                nh = h + dh
                nw = w + dw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                    if dist[h][w] + 1 < dist[nh][nw]:
                        dist[nh][nw] = dist[h][w] + 1
                        Q.append((nh,nw))

    if dist[gh][gw]==INF:
        print(-1)
    else:
        print(dist[gh][gw])




if __name__ == '__main__':
    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()))

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
def f(s,t,mat):
	if all(['#' not in l for l in mat]):
		return 0

	heap = [(0,s)]
	r = {} 
	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:
			return d

		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
	return -1
print f(s,t,mat)

Submission status: Time Limit Exceeded

Solution code:
def abc176d_wizard_in_maze():
    h, w = map(int, input().split())
    start = list(map(int, input().split()))
    goal = list(map(int, input().split()))
    start[0] -= 1
    start[1] -= 1
    goal[0] -= 1
    goal[1] -= 1
    maze = []
    for i in range(h):
        maze.append(input())
    dp = [[float('inf')] * w for _ in range(h)]

    dp[start[0]][start[1]] = 0
    q = [start]

    while len(q) != 0:
        v = q.pop()
        x, y = v[0], v[1]
        for dx, dy in zip([-1, 1, 0, 0], [0, 0, -1, 1]):
            if 0 <= x + dx < h and 0 <= y + dy < w and maze[x + dx][y + dy] != '#' and dp[x][y] < dp[x + dx][y + dy]:
                dp[x + dx][y + dy] = dp[x][y]
                q.append([x + dx, y + dy])

        for dx in [-2, 1, 0, 1, 2]:
            if not 0 <= x + dx < h:
                continue
            for dy in [-2, 1, 0, 1, 2]:
                 if 0 <= y + dy < w and maze[x + dx][y + dy] != '#' and dp[x][y]+1 < dp[x + dx][y + dy]:
                    dp[x + dx][y + dy] = dp[x][y]+1
                    q.append([x + dx, y + dy])

    if dp[goal[0]][goal[1]] == float('inf'):
        print('-1')
    else:
        print(dp[goal[0]][goal[1]])


abc176d_wizard_in_maze()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
from heapq import _heapify_max, _heappop_max
import heapq

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)

"""
method:
    heapify(x): ヒープに変換
    heappush(heap, item): itemをheapにpush
    heappop(heap): heapから最小値を取得 空の場合はIndexError
note:
    max heapにする場合は、prefix: _ とsuffix: _maxをつければ良い
"""

def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    inf = 10**7
    dp = [[inf]*w for _ in range(h)]
    s = [list(input()) for _ in range(h)]
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    dxy = list(zip(dx, dy))
    
    dp[ch-1][cw-1] = 0
    
    q = []
    heappush(q, (0, ch-1, cw-1))
    while q:
        cost, px, py = heappop(q)
        for xi, yj in dxy:
            x = px + xi
            y = py + yj
            if x >= h or y >= w or x < 0 or y < 0 or s[x][y] == "#":
                continue
            if dp[x][y] > cost:
                dp[x][y] = cost
                heappush(q, (cost, x, y))
        cost += 1
        for di in range(-2, 3):
            x = px + di
            if x >= h or x < 0:
                continue
            sx = s[x]
            dpx = dp[x]
            for dj in range(-2, 3):
                y = py + dj
                if y >= w or y < 0 or sx[y] == "#":
                    continue
                if dpx[y] > cost:
                    dpx[y] = cost
                    heappush(q, (cost, x, y))
    if dp[dh-1][dw-1] == inf:
        print(-1)
    else:
        print(dp[dh-1][dw-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    h, w = tuple(map(int, input().split()))
    c = tuple(map(int, input().split()))
    d = tuple(map(int, input().split()))
    s = [list(input()) for i in range(h)]

    flag = 0
    goal = (d[0] - 1, d[1] - 1)
    available_mat = [[(c[0] - 1, c[1] - 1)]]
    available_list = [(c[0] - 1, c[1] - 1)]

    while not len(available_mat[-1]) == 0:
        index = 0
        while index < len(available_mat[-1]):
            i, j = available_mat[-1][index]
            if i > 0 and s[i - 1][j] == '.':
                if not (i - 1, j) in available_list:
                    available_mat[-1].append((i - 1, j))
                    available_list.append((i - 1, j))
            if j > 0 and s[i][j - 1] == '.':
                if not (i, j - 1) in available_list:
                    available_mat[-1].append((i, j - 1))
                    available_list.append((i, j + 1))
            if i < h - 1 and s[i + 1][j] == '.':
                if not (i + 1, j) in available_list:
                    available_mat[-1].append((i + 1, j))
                    available_list.append((i + 1, j))
            if j < w - 1 and s[i][j + 1] == '.':
                if not (i, j + 1) in available_list:
                    available_mat[-1].append((i, j + 1))
                    available_list.append((i, j + 1))
            index += 1
        if goal in available_list:
            flag = 1
            break
        available_mat.append([])
        for coordinate in available_mat[-2]:
            for i in range(max(0, coordinate[0] - 2), min(h, coordinate[0] + 3)):
                for j in range(max(0, coordinate[1] - 2), min(w, coordinate[1] + 3)):
                    if not (i, j) in available_list and s[i][j] == '.':
                        available_list.append((i, j))
                        available_mat[-1].append((i, j))
        if goal in available_list:
            flag = 1
            break


    print(len(available_mat) - 1 if flag == 1 else -1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
INF = float('inf')

H, W = map(int, input().split())
ch, cw = [int(i) - 1 for i in input().split()]
dh, dw = [int(i) - 1 for i in input().split()]
S = []
for i in range(H):
    S.append(input())
# print(S)

B = [[INF for w in range(W)]
        for h in range(H)]
B[ch][cw] = 0
# print(B)

def get_B(h, w):
    if not ((0 <= h < H) and (0 <= w < W)):
        return INF
    else:
        return B[h][w]

flag = True
while flag:
    flag = False
    for h, w in product(range(H), range(W)):
        if S[h][w] == '#':
            continue
        else:
            min_v = INF
            min_v = min(min_v, get_B(h - 1, w))
            min_v = min(min_v, get_B(h + 1, w))
            min_v = min(min_v, get_B(h, w - 1))
            min_v = min(min_v, get_B(h, w + 1))
            # print(min_v)

            # min_v2 = INF
            for i, j in product(range(5), repeat=2):
                if not ((0 <= h - i + 2 < H) and (0 <= w - j + 2 < W)):
                    continue
                min_v = min(B[h - i + 2][w - j + 2] + 1, min_v)

            # min_v = min(min_v1, min_v2)

            if B[h][w] > min_v:
                B[h][w] = min_v
                flag = True
                # for b in B:
                #     print(b)
                # print()

print(B[dh][dw] if B[dh][dw] != INF else -1)