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:
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]

    if not (dot[1] - 1 < 0):
        queue.append([dot[0],dot[1]-1,dot[2]])
    if not (dot[1] + 1 >= w):
        queue.append([dot[0],dot[1]+1,dot[2]])
    if not (dot[0]+1 >= h):
        queue.append([dot[0]+1,dot[1],dot[2]])
    if not (dot[0]-1 < 0):
        queue.append([dot[0]-1,dot[1],dot[2]])

    for x in range(-2,3,1):
        for y in range(-2,3,1):
            if not(dot[0]+ x < 0 or dot[1]+y < 0 or dot[0]+x >= h or dot[1]+y >= w):
                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())
m=[list(input()) for _ in range(H)]
s=(Ch-1,Cw-1)
g=(Dh-1,Dw-1)
q=deque()
q.append(s)
d={s:0}
while q:
    y,x=q.popleft()
    for dy,dx in [(0,1),(1,0),(0,-1),(-1,0)]:
        ny=y+dy
        nx=x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if m[ny][nx]=='.':
            if (ny,nx) not in d:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]
            elif d[(ny,nx)]>d[(y,x)]:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]
    for dy,dx in [(-2,-2),(-1,-2),(0,-2),(1,-2),(2,-2),(-2,-1),(-1,-1),(1,-1),(2,-1),(-2,0),(2,0),(-2,1),(-1,1),(1,1),(2,1),(-2,2),(-1,2),(0,2),(1,2),(2,2)]:
        ny=y+dy
        nx=x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if m[ny][nx]=='.':
            if (ny,nx) not in d and (ny-1,nx) not in d and (ny,nx-1) not in d and (ny+1,nx) not in d and (ny+1,nx) not in d:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]+1
            elif (ny,nx) in d and d[(ny,nx)]>d[(y,x)]+1:
                q.append((ny,nx))
                d[(ny,nx)]=d[(y,x)]+1
if g in d:
    print(d[g])
else:
    print(-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())
smat=[]
smat.append([False]*(W+4))
smat.append([False]*(W+4))
for _ in range(H):
  line=[False,False]+[x=="." for x in input()]+[False,False]
  smat.append(line)
smat.append([False]*(W+4))
smat.append([False]*(W+4))
#print(smat)

from collections import defaultdict
import heapq
def dijkstra_heap(s):
  #始点sから各頂点への最短距離
  dist,prev={},{}
  used=set()
  for v in vlist:
    dist[v]=float("inf")
    prev[v]=-1
  dist[s]=0
  used.add(s)

  hq_edge=[]
  for v,w in graph[s]:
    heapq.heappush(hq_edge,(w,v,s))

  while hq_edge:
    min_w,min_v,u=heapq.heappop(hq_edge)
    #まだ使われてない頂点の中から最小の距離のものを探す
    if min_v in used:
      continue

    dist[min_v]=min_w
    prev[min_v]=u
    used.add(min_v)
    for v,w in graph[min_v]:
      if not v in used:
        heapq.heappush(hq_edge,(min_w+w,v,min_v))

  return dist,prev

vlist=[]
#ここで点の集合をvlistに入れておく
for i in range(2,H+2):
  for j in range(2,W+2):
    if smat[i][j]:
      vlist.append((i,j))

graph=defaultdict(list)
#graph[i]: iから出る道の[重み,行先]の辞書
for i in range(2,H+2):
  for j in range(2,W+2):
    if not smat[i][j]:
      continue
    
    if smat[i-1][j]:
      graph[(i,j)].append([(i-1,j),0])
    if smat[i+1][j]:
      graph[(i,j)].append([(i+1,j),0])
    if smat[i][j-1]:
      graph[(i,j)].append([(i,j-1),0])
    if smat[i][j+1]:
      graph[(i,j)].append([(i,j+1),0])
    
    if smat[i-1][j-1]:
      graph[(i,j)].append([(i-1,j-1),1])
    if smat[i-1][j+1]:
      graph[(i,j)].append([(i-1,j+1),1])
    if smat[i+1][j-1]:
      graph[(i,j)].append([(i+1,j-1),1])
    if smat[i+1][j+1]:
      graph[(i,j)].append([(i+1,j+1),1])

    for k in range(-2,3):
      if smat[i-2][j+k]:
        graph[(i,j)].append([(i-2,j+k),1])
      if smat[i+2][j+k]:
        graph[(i,j)].append([(i+2,j+k),1])
        
    for k in range(-1,2):
      if smat[i+k][j-2]:
        graph[(i,j)].append([(i+k,j-2),1])
      if smat[i+k][j+2]:
        graph[(i,j)].append([(i+k,j+2),1])

dist,prev=dijkstra_heap((Ch+1,Cw+1))
#print(dist)
#print(prev)

if dist[(Dh+1,Dw+1)]==float("inf"):
  print(-1)
else:
  print(dist[(Dh+1,Dw+1)])

Submission status: Time Limit Exceeded

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

import collections
import sys
input=sys.stdin.readline

import heapq

#edgeには[weight,v]を追加していく
def dijkstra(s,edge,n):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #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]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[list(input()) for _ in range(h)]
uf=UnionFind(h*w)
for y in range(h):
    for x in range(w):
        if board[y][x]=='#':
            continue
        if y-1>=0 and board[y-1][x]=='.':
            uf.Unite(y*w+x,(y-1)*w+x)
        if y+1<h and board[y+1][x]=='.':
            uf.Unite(y*w+x,(y+1)*w+x)
        if x-1>=0 and board[y][x-1]=='.':
            uf.Unite(y*w+x,y*w+x-1)
        if x+1<w and board[y][x+1]=='.':
            uf.Unite(y*w+x,y*w+x+1)
edges=[[] for _ in range(h*w+1)]
checked=set()
for y in range(h):
    for x in range(w):
        if board[y][x]=='#':
            continue
        for dy in [-2,-1,0,1,2]:
            if y+dy<0 or y+dy>=h:
                continue
            for dx in [-2,-1,0,1,2]:
                if x+dx<0 or x+dx>=w:
                    continue
                if board[y+dy][x+dx]=='#':
                    continue
                r1=uf.FindRoot(y*w+x)
                r2=uf.FindRoot((y+dy)*w+x+dx)
                if (r1,r2) in checked:
                    continue
                if r1!=r2:
                    edges[r1].append([1,r2])
                    checked.add((r1,r2))
dist=dijkstra(uf.FindRoot((sy-1)*w+(sx-1)),edges,h*w)
ans=dist[uf.FindRoot((gy-1)*w+(gx-1))]
if ans==float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from itertools import product

H, W = map(int, input().split())
start = tuple(map(lambda x: int(x) - 1, input().split()))
goal = tuple(map(lambda x: int(x) - 1, input().split()))

maze = []
for _ in range(H):
    maze.append(list(input()))

visited = set()

Q = [(0, start)]
while Q:
    c, pos = heappop(Q)
    visited.add(pos)
    if pos == goal:
        print(c)
        exit()
    # A
    for move in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        nx = pos[0] + move[0]
        ny = pos[1] + move[1]
        if 0 <= nx < H and 0 <= ny < W:
            if maze[nx][ny] == '.':
                if (nx, ny) not in visited:
                    heappush(Q, (c, (nx, ny)))
    # B
    for move in product(range(-2, 3), repeat=2):
        nx = pos[0] + move[0]
        ny = pos[1] + move[1]
        if 0 <= nx < H and 0 <= ny < W:
            if maze[nx][ny] == '.':
                if (nx, ny) not in visited:
                    heappush(Q, (c + 1, (nx, ny)))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
C = list(map(lambda x: int(x) - 1, input().split()))
D = list(map(lambda x: int(x) - 1, input().split()))
S = [input() for _ in range(H)]
toGo = [[False if i != C[0] or j != C[1] else True for j in range(W)] for i in range(H)]
queue = [C]
ans = 0

while True:
    tmp = queue.pop()
    dfs = [tmp]

    while len(dfs):
        a = dfs.pop()
        for move in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            hh, ww = a[0] + move[0], a[1] + move[1]
            if hh >= H or hh < 0 or ww >= W or ww < 0:
                continue

            if not toGo[hh][ww] and S[hh][ww] == '.':
                toGo[hh][ww] = True
                dfs.append([hh, ww])

    if toGo[D[0]][D[1]]:
        break

    flag = True
    if not len(queue):
        ttogo = [[toGo[i][j] for j in range(W)] for i in range(H)]
        ans += 1
        for i in range(H):
            for j in range(W):
                if not toGo[i][j] and S[i][j] == ".":
                    t = False
                    for ii in range(-2, 3):
                        for jj in range(-2, 3):
                            hh, ww = i + ii, j + jj
                            if hh >= H or hh < 0 or ww >= W or ww < 0:
                                continue

                            if toGo[hh][ww]:
                                ttogo[i][j] = True
                                flag, t = False, True
                                queue.append([i, j])
                                break
                        if t:
                            break
        toGo = ttogo
        if flag:
            print(-1)
            exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections, itertools
H, W, ch, cw, dh, dw, *S = open(0).read().split()
H, W, ch, cw, dh, dw = [int(_) + 1 for _ in [H, W, ch, cw, dh, dw]]
H += 3
W += 3
S = ['#' * W] + ['#' * W] + ['##' + s + '##'
                             for s in S] + ['#' * W] + ['#' * W]
Dist = [[None] * W for _ in range(H)]
Q = collections.deque([(0, ch, cw)])
while Q:
    d, ox, oy = Q.popleft()
    if Dist[ox][oy] is not None or S[ox][oy] == '#':
        continue
    stack = [[ox, oy]]
    warp = set()
    while stack:
        x, y = stack.pop()
        if (x, y) == (dh, dw):
            print(d)
            exit()
        Dist[x][y] = d
        for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            nx, ny = x + dx, y + dy
            if Dist[nx][ny] is None:
                if S[nx][ny] == '.':
                    stack += [[nx, ny]]
                else:
                    warp.add((x, y))
    for x, y in warp:
        for dx, dy in itertools.product(range(-2, 3), repeat=2):
            nx, ny = x + dx, y + dy
            if Dist[nx][ny] is None:
                Q += [(d + 1, nx, ny)]
print(-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())
S = [input() for _ in range(H)]


move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[10**8] * W for _ in range(H)]


def bfs(i, j, d):
    visited[i][j] = d
    que = deque([(i, j, d)])

    while que:
        ci, cj, d = que.popleft()

        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj] <= d:
                continue
            if S[ni][nj] == '.':
                visited[ni][nj] = d
                que.append((ni, nj, d))

        for di in range(-2, 3):
            for dj in range(-2, 3):
                ni, nj = ci+di, cj+dj
                if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj] <= d+1:
                    continue
                if S[ni][nj] == '.':
                    visited[ni][nj] = d+1
                    que.append((ni, nj, d+1))


bfs(Ch-1, Cw-1, 0)
# print(visited)
if visited[Dh-1][Dw-1] == 10**8:
    print(-1)
else:
    print(visited[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def bfs(MAZE, start, goal):
    MAP = [[INF] * len(MAZE[0]) for _ in range(len(MAZE))]
    walks = [(0,1), (1,0), (-1,0), (0, -1)]
    warps = []
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == 0 and j == 0: continue
            if not (i,j) in walks:
                warps.append((i, j))
    queue = []
    k = (0,) + start
    heappush(queue, k)

    #for m in MAZE:
    #    print(m)



    while queue:
        count, ci, cj = heappop(queue)
        if (ci, cj) == goal:
            return count
        for ii, jj in walks:
            ni, nj = ci + ii, cj + jj
            if MAZE[ni][nj] == '.' and MAP[ni][nj] > count:
                heappush(queue, (count, ni, nj))
                MAP[ni][nj] = count
        for ii, jj in warps:
            ni, nj = ci + ii, cj + jj
            if MAZE[ni][nj] == '.' and MAP[ni][nj] > count + 1:
                heappush(queue, (count+1, ni, nj))
                MAP[ni][nj] = count + 1

    return -1


def run():
    H, W = map(int, sysread().split())
    Ci, Cj = map(int, sysread().split())
    Ci += 1
    Cj += 1
    Di, Dj = map(int, sysread().split())
    Di += 1
    Dj += 1
    MAZE = []
    MAZE.append('#' * (W + 4))
    MAZE.append('#' * (W + 4))
    for i in range(H):
        s = input()
        s = '##' + s + '##'
        MAZE.append(s)
    MAZE.append('#' * (W + 4))
    MAZE.append('#' * (W + 4))
    print(bfs(MAZE, (Ci, Cj), (Di, Dj)))





if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())

sh += 1
sw += 1
gh += 1
gw += 1

S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [[float('inf')]*(W+4) for _ in range(H+4)]
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from collections import deque
d = deque()
visited[sh][sw] = 0
d.append((sh,sw))

while len(d)>0:
  h,w = d.popleft()
  cnt = visited[h][w]
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    if S[h1][w1]=='.':
      if visited[h1][w1]>cnt:
        visited[h1][w1]=cnt
        d.append((h1,w1))
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    if S[h2][w2]=='.':
      if visited[h2][w2]>cnt+1:
        visited[h2][w2]=cnt+1
        d.append((h2,w2))
ans = visited[gh][gw] if visited[gh][gw]<float('inf') else -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    CH, CW = [int(x) - 1 for x in input().split()]
    DH, DW = [int(x) - 1 for x in input().split()]
    S = [input().strip() for _ in range(H)]

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

    visited = [[float("inf")] * W for _ in range(H)]

    q = collections.deque()
    visited[CH][CW] = 0
    q.append((CH, CW))
    while q:
        cx, cy = q.popleft()
        cc = visited[cx][cy]

        # 隣接
        kabe_cnt = 0
        for nx, ny in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            nnx = cx + nx
            nny = cy + ny
            if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                if S[nnx][nny] == ".":
                    if visited[nnx][nny] > cc:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc
                else:
                    kabe_cnt += 1

        # ワープ
        if kabe_cnt > 0:
            for nx, ny in warp:
                nnx = cx + nx
                nny = cy + ny
                if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                    if S[nnx][nny] == "." and visited[nnx][nny] > cc:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc + 1

    if visited[DH][DW] == float("inf"):
        print(-1)
    else:
        print(visited[DH][DW])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from queue import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
inf = 10**20

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

li = [["" for i in range(w)]for j in range(h)]
for i in range(h):
    s = input()
    for j in range(w):
        li[i][j] = s[j]

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

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
        #elif lin[nx][ny] == inf:
        else:
            if lin[nx][ny] > lin[x][y]:
                que.append([nx,ny])
                lin[nx][ny] = min(lin[x][y],lin[nx][ny])# 直接行ける
        
    # 魔法の力をもってすれば行ける
    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:
                que.append([nx,ny])
                lin[nx][ny] = min(lin[x][y]+1,lin[nx][ny])

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

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:
R, C = map(int,input().split(" "))

at = list(map(lambda x : int(x)-1, input().split(" ")))
des = list(map(lambda x: int(x)-1, input().split(" ")))

board = []
for _ in range(R):
    board.append(list(input().strip()))


visited = [[-1]*C for _ in range(R)]
visited[at[0]][at[1]] = 0

def tele(i, j ):
    moves = []
    for di in range(-2,3):
        for dj in range(-2,3):
            if di==0 and dj ==0 : 
                continue
            elif i+di >= R or i+di < 0 or j+dj >= C or j+dj < 0 :
                continue
            elif visited[i+di][j+dj] != -1  or board[i+di][j+dj] == "#" :
                continue
            moves.append((i+di, j+dj))
    return moves 

dirs = [(1, 0), (-1, 0), (0, -1), (0, 1)]
def walk(i,j ):
    moves = []
    for di,dj in dirs:
        if i+di >= R or i+di < 0 or j+dj >= C or j+dj < 0:
            continue
        if visited[i+di][j+dj] != -1 or board[i+di][j+dj] == "#":
            continue
        moves.append((i+di, j+dj))
    return moves 

from collections import deque
movable = deque() 
movable.append( (at[0],at[1]) )

magic = 0
while movable:
    next_movable = deque()
    temp = set()
    while movable :
        i,j = movable.popleft()
        
        visited[i][j] = magic
        temp.add((i,j))
        for ni, nj in walk(i, j):
            if visited[ni][nj] != -1:
                continue
            visited[ni][nj] = magic
            movable.append((ni,nj))

    magic += 1
    for m in temp:
        for move in tele(m[0],m[1]):
            if visited[move[0]][move[1]] != -1 :
                continue
            visited[move[0]][move[1]] = magic
            next_movable.append(move)

    movable = next_movable
    
    
print(visited[des[0]][des[1]])

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(_) for _ in input().split()]
C = [int(_) - 1 for _ in input().split()]
D = [int(_) - 1 for _ in input().split()]

S = [input() for _ in range(H)]
V = [[-1 for w in range(W)] for h in range(H)]


V[C[0]][C[1]] = 0
pool = [tuple(C)]

while(pool):
    y, x = pool.pop()
    for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
        if y + dy < 0 or H <= y + dy:
            continue
        if x + dx < 0 or W <= x + dx:
            continue
        if S[y+dy][x+dx] == "#":
            continue
        if V[y+dy][x+dx] == -1 or V[y+dy][x+dx] > V[y][x]:
            V[y+dy][x+dx] = V[y][x]
            pool.append((y+dy, x+dx))
    for dx in [-2,-1,0,1,2]:
        for dy in [-2,-1,0,1,2]:
            if y + dy < 0 or H <= y + dy:
                continue
            if x + dx < 0 or W <= x + dx:
                continue
            if S[y+dy][x+dx] == "#":
                continue
            if V[y+dy][x+dx] == -1 or V[y+dy][x+dx] > V[y][x] + 1:
                V[y+dy][x+dx] = V[y][x] + 1
                pool.append((y+dy, x+dx))

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush

H, W = map(int, input().split())
Si, Sj = map(int, input().split())
Gi, Gj = map(int, input().split())
matrix = []
for i in range(H):
    matrix.append(list(input()))

que = [(0, Si-1, Sj-1, 0)]
heapify(que)
visited = set()

while que:
    priority, r, c, count = heappop(que)
    if not(0 <= r < H and 0 <= c < W):
        continue
    elif (r, c) in visited:
        continue
    elif matrix[r][c] == '#':
        continue
    elif (r, c) == (Gi-1, Gj-1):
        print(count)
        exit()
    visited.add((r, c))
    for td, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        heappush(que, (priority+1, r+td, c+lr, count))
    for ud in range(-2, 3):
        for lr in range(-2, 3):
            heappush(que, (priority+1+H*W, r+ud, c+lr, count+1))

print('-1')

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    CH, CW = [int(x) - 1 for x in input().split()]
    DH, DW = [int(x) - 1 for x in input().split()]
    S = [input().strip() for _ in range(H)]

    warp = [[-2, -2], [-2, -2], [-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, -2], [2, 0], [2, 1], [2, 2]]

    visited = [[float("inf")] * W for _ in range(H)]

    q = collections.deque()
    visited[CH][CW] = 0
    q.append((CH, CW))
    while q:
        cx, cy = q.popleft()
        cc = visited[cx][cy]

        # 隣接
        kabe_cnt = 0
        for nx, ny in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            nnx = cx + nx
            nny = cy + ny
            if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                if S[nnx][nny] == ".":
                    if visited[nnx][nny] > cc:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc
                else:
                    kabe_cnt += 1

        # ワープ
        if kabe_cnt > 0:
            for nx, ny in warp:
                nnx = cx + nx
                nny = cy + ny
                if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                    if S[nnx][nny] == "." and visited[nnx][nny] > cc:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc + 1

    if visited[DH][DW] == float("inf"):
        print(-1)
    else:
        print(visited[DH][DW])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())

sh += 1
sw += 1
gh += 1
gw += 1

S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [[float('inf')]*(W+4) for _ in range(H+4)]
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from collections import deque
d = deque()
visited[sh][sw] = 0
d.append((sh,sw,0))

while len(d)>0:
  h,w,cnt = d.popleft()
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    if S[h1][w1]=='.':
      if visited[h1][w1]>cnt:
        visited[h1][w1]=cnt
        d.append((h1,w1,cnt))
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    if S[h2][w2]=='.':
      if visited[h2][w2]>cnt+1:
        visited[h2][w2]=cnt+1
        d.append((h2,w2,cnt+1))
ans = visited[gh][gw] if visited[gh][gw]<float('inf') else -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import itertools

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

seen = [[-1] * w for _ in range(h)]
seen[sy][sx] = 0
que = collections.deque()
que.append((sy, sx))

cnt = 0
while True:
    if seen[gy][gx] != -1:
        break
    
    while que:
        py, px = que.popleft()
        for dy, dx in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            ny = py + dy
            nx = px + dx
            if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] == "." and seen[ny][nx] == -1:
                seen[ny][nx] = cnt
                que.append((ny, nx))
    
    flag = True
    d = [-2, -1, 0, 1, 2]
    for py in range(h):
        for px in range(w):
            if seen[py][px] == cnt:
                for i in range(5):
                    for j in range(5):
                        ny = py + d[i]
                        nx = px + d[j]
                        if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] == "." and seen[ny][nx] == -1:
                            seen[ny][nx] = cnt + 1
                            que.append((ny, nx))
                            flag = False
    cnt += 1
    if flag:
        break

print(seen[gy][gx])