Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import *

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=list(sys.stdin)

ans=-1
hp=[(0,si,sj)]
dirs=[-2,-1,0,1,+2]
dist=[[float('inf')]*W for _ in range(H)]
dist[si][sj]=0
while hp:
    k,i,j=heappop(hp)
    if i==ti and j==tj:
        ans=k
        break
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='#':
                continue
            if (abs(di)==1 and dj==0) or (di==0 and abs(dj)==1):
                nk=k
            else:
                nk=k+1
            if nk>=dist[ni][nj]:
                continue
            dist[ni][nj]=nk
            heappush(hp,(nk,ni,nj))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import *
from pprint import pprint

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=list(sys.stdin)

ans=-1
hp=[(0,si,sj)]
dx=[-2,-1,0,1,+2]
dy=[-2,-1,0,1,+2]
dist=[[float('inf')]*W for _ in range(H)]
dist[si][sj]=0
while hp:
    k,i,j=heappop(hp)
    if i==ti and j==tj:
        ans=k
        break
    for ci in dy:
        for cj in dx:
            if ci==cj==0:
                continue
            ni,nj=i+ci,j+cj
            if not (0<=ni<H and 0<=nj<W):
                continue
            if A[ni][nj]=='#':
                continue
            if (abs(ci)==1 and cj==0) or (ci==0 and abs(cj)==1):
                x=k
            else:
                x=k+1
            if x>=dist[ni][nj]:
                continue
            dist[ni][nj]=x
            heappush(hp,(x,ni,nj))


#pprint(dist)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m,d=zip(*eval('(input(),[I]*w),'*h))
q=deque([(s-1,t-1,1)])
while q:
 y,x,c=q.popleft()
 for i in range(y-2,y+3):
  for j in range(x-2,x+3):
   if h>i>-1<j<w<I==d[i][j]!=m[i][j]>'#':d[y][x]=c;abs(y-i)+abs(x-j)<2!=q.appendleft((i,j,c));q.append((i,j,c+1))
print(d[f-1][g-1]%I-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m,d=zip(*eval('(input(),[I]*w),'*h))
q=deque([(s-1,t-1,1)])
while q:
 y,x,c=q.popleft()
 for i in range(y-2,y+3):
  for j in range(x-2,x+3):
   if h>i>-1<j<w<d[i][j]!=m[i][j]>'#':d[y][x]=c;abs(y-i)+abs(x-j)<2!=q.appendleft((i,j,c));q.append((i,j,c+1))
print(d[f-1][g-1]%I-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

indice = lambda s: int(s)-1 

H, W = map(int, input().split())
ch, cw = map(indice, input().split())
dh, dw = map(indice, input().split())

world = np.array([[1 if s == '.' else 0 for s in input()] for _ in range(H)])
row, col = np.where(world == 1)
available = {(r, c) for r, c in zip(row, col)}

q = deque()
q.append((ch, cw, 0))
available.discard((ch, cw, 0))
# 01-BFS
res = -1
while q:
    h, w, dist = q.popleft()
    if h == dh and w == dw:
        res = dist
        break

    # 距離0の動き
    A_move = [(1, 0), (-1, 0), (0, 0), (0, 1), (0, -1)]
    for dx, dy in A_move:
        if (h+dx, w+dy) in available:
            available.discard((h+dx, w+dy))
            q.appendleft((h+dx, w+dy, dist))

    B_move = [(dx, dy) for dx in (-2, -1, 0, 1, 2) for dy in (-2, -1, 0, 1, 2)]
    for dx, dy in B_move:
        if (h+dx, w+dy) in available:
            q.append((h+dx, w+dy, dist+1))

print(res)

Submission status: Time Limit Exceeded

Solution code:
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())
tizu=[]
d=deque()
d.appendleft([ch,cw])
cost=[[-1 for i in range(w)]for j in range(h)]
dx=[1,0,-1,0,-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
dy=[0,1,0,-1,-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
for i in range(h):
    tizu.append(input())
cost[ch][cw]=0
while(d):
    x,y=d.popleft()
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        ####行ったことある、かつ、コストが手前より高い
        if(nx<0 or ny<0 or nx>=h or ny>=w):
            continue
        if(cost[nx][ny]>-1 and cost[nx][ny]<=cost[x][y]):
            continue
        if(tizu[nx][ny]=='.'):
            cost[nx][ny]=cost[x][y]
            d.appendleft([nx,ny])
    
    for i in range(4,24):
        nx=x+dx[i]
        ny=y+dy[i]
        if(nx<0 or ny<0 or nx>=h or ny>=w):
            continue
        if(cost[nx][ny]>-1):
            continue
        if(tizu[nx][ny]=='.'):
            cost[nx][ny]=cost[x][y]+1
            d.append([nx,ny])

print(cost[dh][dw])

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

move = ((1, 0), (-1, 0), (0, 1), (0, -1))
que = deque([(Ch-1, Cw-1, 0)])

visited = [[-1] * W for _ in range(H)]
while que:
    ci, cj, d = que.popleft()
    if visited[ci][cj] == -1:
        visited[ci][cj] = d

    for di, dj in move:
        ni, nj = ci + di, cj + dj
        if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj] != -1:
            continue
        if S[ni][nj] == '.':
            visited[ni][nj] = d
            que.appendleft((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] != -1:
                continue
            if S[ni][nj] == '.':
                que.append((ni, nj, d+1))


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

Submission status: Time Limit Exceeded

Solution code:
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())
tizu=[]
d=deque()
d.appendleft([ch,cw])
cost=[[-1 for i in range(w)]for j in range(h)]
dx=[1,0,-1,0,-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
dy=[0,1,0,-1,-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
for i in range(h):
    tizu.append(input())
cost[ch][cw]=0
while(d):
    x,y=d.popleft()
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        ####行ったことある、かつ、コストが手前より高い
        if(nx<0 or ny<0 or nx>=h or ny>=w):
            continue
        if(cost[nx][ny]>-1 and cost[nx][ny]<=cost[x][y]):
            continue
        if(tizu[nx][ny]=='.'):
            cost[nx][ny]=cost[x][y]
            d.appendleft([nx,ny])
    
    for i in range(4,24):
        nx=x+dx[i]
        ny=y+dy[i]
        if(nx<0 or ny<0 or nx>=h or ny>=w):
            continue
        if(cost[nx][ny]>-1 and cost[nx][ny]<=cost[x][y]):
            continue
        if(tizu[nx][ny]=='.'):
            cost[nx][ny]=cost[x][y]+1
            d.append([nx,ny])

print(cost[dh][dw])

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))
que = deque([(Ch-1, Cw-1, 0)])

visited = [[-1] * W for _ in range(H)]
while que:
    ci, cj, d = que.popleft()
    if visited[ci][cj] == -1:
        visited[ci][cj] = d

    for di, dj in move:
        ni, nj = ci + di, cj + dj
        if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj] != -1:
            continue
        if S[ni][nj] == '.':
            visited[ni][nj] = d
            que.appendleft((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] != -1:
                continue
            if S[ni][nj] == '.':
                que.append((ni, nj, d+1))


# print(visited)
if visited[Dh-1][Dw-1] == -1:
    print(-1)
else:
    print(visited[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())
S = [input() for _ in range(H)]

move = ((1, 0), (-1, 0), (0, 1), (0, -1))
que = deque([(Ch-1, Cw-1, 0)])

visited = [[-1] * W for _ in range(H)]
while que:
    ci, cj, d = que.popleft()
    if visited[ci][cj] == -1:
        visited[ci][cj] = d

    for di, dj in move:
        ni, nj = ci + di, cj + dj
        if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj] != -1:
            continue
        if S[ni][nj] == '.':
            que.appendleft((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] != -1:
                continue
            if S[ni][nj] == '.':
                que.append((ni, nj, d+1))


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

Submission status: Time Limit Exceeded

Solution code:
f=lambda:map(int,input().split())
h,w=f()
ch,cw=f()
dh,dw=f()
g=[[*input()] for _ in range(h)]
from collections import *
q=deque([(0,ch-1,cw-1)])
while q:
  d,x,y=q.popleft()
  if g[x][y]=='.': g[x][y]=d
  for dx in range(-2,3):
    for dy in range(-2,3):
      j=abs(dx)+abs(dy)
      nx,ny=x+dx,y+dy
      if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and j:
        if j>1: q.append((d+1,nx,ny))
        else: q.appendleft((d,nx,ny))
a=g[dh-1][dw-1]
print([a,-1][a=='.'])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w=map(int,input().split())
cy,cx=map(int,input().split())
gy,gx=map(int,input().split())
inf=float('inf')
maze=[]
for _ in range(h):
  s=list(input())
  for i in range(w):
    if s[i]=='.':
      s[i]=inf
  maze.append(s)
  
def solve(maze,cy,cx,gy,gx):
  [sy,sx]=[cy-1,cx-1]
  qu=deque([[sy,sx]])
  maze[sy][sx]=0
  T=0
  while qu:
    y,x=qu.popleft()
    t=maze[y][x]
      
    for i in ([1,0],[0,1],[-1,0],[0,-1]):
      ny=y-i[0]
      nx=x-i[1]
      if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!='#':
        if maze[ny][nx]>t:
          maze[ny][nx]=t
          qu.appendleft([ny,nx])
    for j in range(-2,3):
      for k in range(-2,3):
        ny=y-j
        nx=x-k
        if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!='#':
          if maze[ny][nx]>t:
            maze[ny][nx]=t+1
            qu.append([ny,nx])
            
  return maze[gy-1][gx-1]
  
if solve(maze,cy,cx,gy,gx)==inf:
  print(-1)
  
else:
  print(solve(maze,cy,cx,gy,gx))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
from collections import deque
import math
h,w=map(int,input().split())
sx,sy=map(int,input().split())
sx-=1
sy-=1
gx,gy=map(int,input().split())
gx-=1
gy-=1
grid=[]
for i in range(h):
    arr=list(input())
    grid.append(arr)
dist=[[math.inf]*w for _ in range(h)]
q=deque()
q.append([sx,sy])
dist[sx][sy]=0
k=[[0,1],[0,-1],[1,0],[-1,0]]

while q:
    x,y=q.popleft()
    d=dist[x][y]
    for i,j in k:
        nx,ny=x+i,y+j
        if  nx<0 or nx>=h or ny<0 or ny>=w:
            continue
        if grid[nx][ny]=="#":
            continue
        if dist[nx][ny]<=d:
            continue
        dist[nx][ny]=d
        q.appendleft([nx,ny])
    
    for ei in range(-2,3):
        for ej in range(-2,3):
            nx,ny=x+ei,y+ej
            if  nx<0 or nx>=h or ny<0 or ny>=w:
                continue
            if grid[nx][ny]=="#":
                continue
            if dist[nx][ny]<=d+1:
                continue
            dist[nx][ny]=d+1
            q.append([nx,ny])

if dist[gx][gy]==math.inf:
    print(-1)
else:
    print(dist[gx][gy])

Submission status: Time Limit Exceeded

Solution code:
INF=10**6
f=lambda:map(int,input().split())
h,w=f()
ch,cw=f()
dh,dw=f()
g=[input() for _ in range(h)]
d=[[INF]*w for _ in range(h)]
d[ch-1][cw-1]=0
from collections import *
q=deque([(0,ch-1,cw-1)])
while q:
  td,tx,ty=q.popleft()
  if d[tx][ty]<td: continue
  for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:
    nx,ny=tx+dx,ty+dy
    if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and d[nx][ny]>td:
      d[nx][ny]=td
      q.appendleft((td,nx,ny))
  for dx in range(-2,3):
    for dy in range(-2,3):
      nx,ny=tx+dx,ty+dy
      if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and d[nx][ny]>td+1:
        d[nx][ny]=td+1
        q.append((td+1,nx,ny))
a=d[dh-1][dw-1]
print([-1,a][a<INF])

Submission status: Time Limit Exceeded

Solution code:
INF=10**6
f=lambda:map(int,input().split())
h,w=f()
ch,cw=f()
ch-=1
cw-=1
dh,dw=f()
dh-=1
dw-=1
g=[input() for _ in range(h)]
from collections import *
def grid_01_bfs(x,y):
  d=[[INF]*w for _ in range(h)]
  d[x][y]=0
  q=deque([(0,x,y)])
  while q:
    td,tx,ty=q.popleft()
    if d[tx][ty]<td: continue
    for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:
      nx,ny=tx+dx,ty+dy
      if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and d[nx][ny]>td:
        d[nx][ny]=td
        q.appendleft((d[nx][ny],nx,ny))
    for dx in range(-2,3):
      for dy in range(-2,3):
        nx,ny=tx+dx,ty+dy
        if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and d[nx][ny]>td+1:
          d[nx][ny]=td+1
          q.append((d[nx][ny],nx,ny))
  return d
a=grid_01_bfs(ch,cw)[dh][dw]
print([-1,a][a<INF])

Submission status: Time Limit Exceeded

Solution code:
INF=10**9
f=lambda:map(int,input().split())
h,w=f()
ch,cw=f()
ch-=1
cw-=1
dh,dw=f()
dh-=1
dw-=1
g=[input() for _ in range(h)]
from heapq import *
def dijkstra_grid(x,y):
  d=[[INF]*w for _ in range(h)]
  d[x][y]=0
  q=[(0,x,y)]
  while q:
    td,tx,ty=heappop(q)
    if d[tx][ty]<td: continue
    for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:
      nx,ny=tx+dx,ty+dy
      if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and d[nx][ny]>td:
        d[nx][ny]=td
        heappush(q,(td,nx,ny))
    for dx in range(-2,3):
      for dy in range(-2,3):
        nx,ny=tx+dx,ty+dy
        if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and d[nx][ny]>td+1:
          d[nx][ny]=td+1
          heappush(q,(td+1,nx,ny))
  return d
a=dijkstra_grid(ch,cw)[dh][dw]
print([-1,a][a<INF])

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

def to_idx(x, y):
    return w*x+y
def from_idx(idx):
    return (idx//w, idx-idx//w*w)

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
mat = []
for _ in range(h):
    s = input()
    mat.append(s)

union_find = UnionFind(h*w)
for i in range(h):
    for j in range(w):
        c = mat[i][j]
        if c == "#":
            continue
        for d_id in range(4):
            dx = [-1, 0, 1, 0][d_id]
            dy = [0, 1, 0, -1][d_id]
            if i + dx < 0 or h <= i + dx or j + dy < 0 or w <= j + dy:
                continue
            dc = mat[i+dx][j+dy]
            if dc == ".":
                union_find.union(to_idx(i, j), to_idx(i+dx, j+dy))
roots = [i for i in union_find.roots() if mat[from_idx(i)[0]][from_idx(i)[1]] == "."]
root_dict = {v: i for i, v in enumerate(roots)}

island_num = len(root_dict.keys())
warp_mat = [[0 for _ in range(island_num)] for _ in range(island_num)]
for i in range(h):
    for j in range(w):
        c = mat[i][j]
        c_idx = to_idx(i, j)
        if c == "#":
            continue
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if i + dx < 0 or h <= i + dx or j + dy < 0 or w <= j + dy:
                    continue
                dc = mat[i+dx][j+dy]
                dc_idx = to_idx(i+dx, j+dy)
                if dc == "#":
                    continue
                if union_find.find(c_idx) != union_find.find(dc_idx):
                    c_root_idx = root_dict[union_find.find(c_idx)]
                    dc_root_idx = root_dict[union_find.find(dc_idx)]
                    warp_mat[c_root_idx][dc_root_idx] = 1
                    warp_mat[dc_root_idx][c_root_idx] = 1
start = root_dict[union_find.find(to_idx(ch-1, cw-1))]
goal = root_dict[union_find.find(to_idx(dh-1, dw-1))]

def dfs(c, g, cost, reached):
    if c == g:
        print(cost)
        exit()
    reached[c] = True
    for i, v in enumerate(warp_mat[c]):
        if v == 1 and not reached[i]:
            dfs(i, g, cost+1, reached[::])

dfs(start, goal, 0, [False for _ in range(island_num)])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
def d_wizard_in_maze():
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Start_row, Start_col = [int(i) - 1 for i in input().split()]
    Goal_row, Goal_col = [int(i) - 1 for i in input().split()]
    Grid = [input() for _ in range(H)]

    warp_count = [[-1] * W for i in range(H)]
    neighbor_4 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    neighbor_25 = [(i, j) for i in range(-2, 3) for j in range(-2, 3)]
    queue = deque([(Start_row, Start_col, 0)])  # コスト 0 の移動は左詰めする

    def can_walk(row, col):
        return 0 <= row < H and 0 <= col < W and Grid[row][col] == '.'

    def move(row, col, neighbor, cond, func):
        nonlocal warp_count
        for dr, dc in neighbor:
            nr, nc = row + dr, col + dc
            if can_walk(nr, nc):
                if eval(cond):
                    func((nr, nc, count + int(len(neighbor) == 25)))

    while(queue):
        row, col, count = queue.popleft()
        if warp_count[row][col] != -1:
            continue
        warp_count[row][col] = count

        move(row, col, neighbor_4, 'warp_count[nr][nc] == -1', queue.appendleft)
        move(row, col, neighbor_25, 'True', queue.append)

    return warp_count[Goal_row][Goal_col]

print(d_wizard_in_maze())

Submission status: Time Limit Exceeded

Solution code:
INF=10**9
f=lambda:map(int,input().split())
h,w=f()
ch,cw=f()
ch-=1
cw-=1
dh,dw=f()
dh-=1
dw-=1
g=[input() for _ in range(h)]
from heapq import *
def dijkstra_grid(x,y):
  d=[[INF]*w for _ in range(h)]
  d[x][y]=0
  q=[(0,x,y)]
  while q:
    td,tx,ty=heappop(q)
    for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:
      nx,ny=tx+dx,ty+dy
      if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and d[nx][ny]>td:
        d[nx][ny]=td
        heappush(q,(td,nx,ny))
    for dx in range(-2,3):
      for dy in range(-2,3):
        nx,ny=tx+dx,ty+dy
        if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and d[nx][ny]>td+1:
          d[nx][ny]=td+1
          heappush(q,(td+1,nx,ny))
  return d
a=dijkstra_grid(ch,cw)[dh][dw]
print([-1,a][a<INF])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
HW = input().split()
H, W = int(HW[0]), int(HW[1])
C = input().split()
Ch, Cw = int(C[0]), int(C[1])
D = input().split()
Dh, Dw = int(D[0]), int(D[1])
route = []
for h in range(H):
    route.append(input())

visited = [[False]*W for x in range(H)]
kouho = deque()
kouho.append([Ch-1, Cw-1])
warpkouho = deque()

def check_walk(a, b):
    if 0 <= a <= H-1 and 0 <= b <= W-1: 
        if visited[a][b] == False and route[a][b] == ".":
            kouho.append([a, b])
def check_warp(a, b, cwarp):
    if 0 <= a <= H-1 and 0 <= b <= W-1:
        if visited[a][b] == False and route[a][b] == ".":
            warpkouho.append([a, b, cwarp+1])

def wizard():
    warp = 1
    while True:
        if len(kouho) != 0:
            tmp = kouho.popleft()
        elif len(warpkouho) != 0:
            tmp = warpkouho.popleft()
            warp = tmp[2]
        else:
            break
        h = tmp[0]
        w = tmp[1]
        if visited[h][w] == False:
            visited[h][w] = warp
            check_walk(h-1, w)
            check_walk(h+1, w)
            check_walk(h, w-1)
            check_walk(h, w+1)
            for n in range(5):
                for m in range(5):
                  check_warp(h-2+n, w-2+m, warp)
        if h == Dh-1 and w == Dw-1:
            print(visited[h][w]-1)
            return
    print(-1)
wizard()

Submission status: Time Limit Exceeded

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

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
d = [INF] * (h*w)

stack = deque([(ch-1, cw-1, 0)])

nex = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
            continue
        else:
            nex.append((i,j))

while stack:
    curh, curw, cnt = stack.popleft()
    if d[curh * w + curw] <= cnt:
        continue
    else:
        d[curh * w + curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            stack.appendleft((nh, nw, cnt))
    for dh, dw in nex:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and  d[nh * w + nw] > cnt:
            stack.append((nh, nw, cnt+1))

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])

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 i in range(H)]

def BFS(x,y):
    weight = {(x,y):0}
    checklist = []
    checked = []
    checklist = deque([[0,x,y]])
    while(len(checked)<H*W and checklist):
        while(1):
            weight_node,node_x,node_y = checklist.popleft()
            if (node_x,node_y) not in checked:
                checked.append((node_x,node_y))
                break
        if node_x == dh-1 and node_y == dw-1:
            return weight_node
        for next_x in range(max(0,node_x-2),min(H,node_x+3)):
                for next_y in range(max(0,node_y-2),min(W,node_y+3)):
                    if next_x == node_x and next_y == node_y:
                        continue
                    elif s[next_x][next_y] == '.':
                        if (next_x,next_y) in [(node_x-1,node_y),(node_x+1,node_y),(node_x,node_y-1),(node_x,node_y+1)]:
                            if (next_x,next_y) not in checked:
                                if (next_x,next_y) not in weight or weight_node < weight[(next_x,next_y)]:
                                    checklist.appendleft([weight_node,next_x,next_y])
                        else:
                            weight_next_node = weight_node + 1
                            if (next_x,next_y) not in checked:
                                if (next_x,next_y) not in weight or weight_node < weight[(next_x,next_y)]:
                                    checklist.append([weight_next_node,next_x,next_y])
    return -1

print(BFS(ch-1,cw-1))

Submission status: Time Limit Exceeded

Solution code:
def d_wizard_in_maze():
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Start_row, Start_col = [int(i) - 1 for i in input().split()]
    Goal_row, Goal_col = [int(i) - 1 for i in input().split()]
    Grid = [input() for _ in range(H)]

    warp_count = [[-1] * W for i in range(H)]
    neighbor = {(-1, 0), (1, 0), (0, -1), (0, 1)}
    queue = deque([(Start_row, Start_col, 0)])  # コスト 0 の移動は左詰めする
    while(queue):
        row, col, count = queue.popleft()

        if warp_count[row][col] >= 0:
            continue

        warp_count[row][col] = count
        for dr in range(-2, 3):
            for dc in range(-2, 3):
                nr, nc = row + dr, col + dc
                if (0 <= nr < H and 0 <= nc < W and Grid[nr][nc] == '.'
                        and warp_count[row + dr][col + dc] < 0):
                    if (dr, dc) in neighbor:
                        queue.appendleft((nr, nc, count))
                    else:
                        queue.append((nr, nc, count + 1))
    return warp_count[Goal_row][Goal_col]

print(d_wizard_in_maze())

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())
Ch-=1
Cw-=1
Dh-=1
Dw-=1

S=[]
for i in range(H):
  s=list(input())
  S.append([10**10 if i =="." else -1 for i in s])
visit=[[False for i in range(W)] for j in range(H)]

dq = deque()
dq.append((Ch,Cw,0))
S[Ch][Cw]=0
counter=0

while dq:
  a=dq.popleft()
  if visit[a[0]][a[1]]==True:
    continue
  elif S[a[0]][a[1]]==counter:
    visit[a[0]][a[1]]=True
  elif a[2]==counter+1:
    visit[a[0]][a[1]]=True
    counter+=1
  for i in range(5):
    for j in range(5):
      if a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W:
        if abs(i-2)+abs(j-2)==1 and S[a[0]][a[1]]<S[a[0]-2+i][a[1]-2+j] and visit[a[0]-2+i][a[1]-2+j]==False:
          S[a[0]-2+i][a[1]-2+j]=counter
          dq.appendleft((a[0]-2+i,a[1]-2+j,counter))
        elif S[a[0]][a[1]]+1<S[a[0]-2+i][a[1]-2+j] and visit[a[0]-2+i][a[1]-2+j]==False:
          S[a[0]-2+i][a[1]-2+j]=counter+1
          dq.append((a[0]-2+i,a[1]-2+j,counter+1))
  #print(visit,counter,a,dq,"\n")
if S[Dh][Dw]==10**10:
  print(-1)
else:
  print(S[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
import collections

def is_not_road(x, y):
    return x < 0 or x >= h or y < 0 or y >= w or m[x][y] < 0

m = []
q = collections.deque()

h, w = list(map(int, input().split()))
cx, cy = list(map(lambda c: int(c) - 1, input().split()))
dx, dy = list(map(lambda c: int(c) - 1, input().split()))

for _ in range(h):
    s = input()
    m.append([0 if c == '.' else -1 for c in s])

q.append((cx, cy, 1))

while True:
    try:
        x, y, c = q.pop()
    except IndexError:
        break

    if is_not_road(x, y) or m[x][y] > 0 and m[x][y] <= c:
        continue
    m[x][y] = c

    q.append((x - 1, y, c))
    q.append((x + 1, y, c))
    q.append((x, y - 1, c))
    q.append((x, y + 1, c))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if abs(i) + abs(j) <= 1: continue
            q.appendleft((x + i, y + j, c + 1))

if m[dx][dy] > 0:
    print(m[dx][dy] - 1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(H) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]<d[(to_h, to_w)]:
            d[(to_h, to_w)]=d[(fro_h, fro_w)]
            q.appendleft((to_h, to_w))

    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]+1<d[(to_h, to_w)]:
            d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
            q.append((to_h, to_w))

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

Submission status: Time Limit Exceeded

Solution code:
import collections
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = [input() for _ in range(h)]

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

d = collections.deque()
d.append((ch, cw))
visit = set()
x = ch
y = cw
cost = [[-1]*w for _ in range(h)]
cost[ch][cw] = 0

while len(d) > 0:
    x, y = d.popleft()
    if (x, y) not in visit:
        visit.add((x, y))
    else:
        continue
    for i in range(5):
        for j in range(5):
            x_n = x+i-2
            y_n = y+j-2
            if x_n >= 0 and x_n < h and y_n >= 0 and y_n < w:
                if s[x_n][y_n] == '.' and (x_n, y_n) not in visit:
                    if pow(i-2, 2)+pow(j-2, 2) == 1:
                            d.appendleft((x_n, y_n))
                            cost[x_n][y_n] = cost[x][y]
                    else:
                        d.append((x_n, y_n))
                        if cost[x_n][y_n] == -1:
                            cost[x_n][y_n] = cost[x][y]+1

print(cost[dh][dw])