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 deque
 
N,M=map(int,input().split())
starty,startx=map(int,input().split())
goaly,goalx=map(int,input().split())
startx-=1
starty-=1
goalx-=1
goaly-=1
 
 
S = [["" for j in range(M)] for i in range(N)]#2行3列の場合
#iがyｊがx
 
 
 
 
 
 
for i in range(N):
    tmp=input()
    for j in range(M):
        S[i][j]=tmp[j]
 
if N==1 and M==1:
    if S[0][0]=="#":
        print(-1)
        exit()
    else:
        print(0)
        exit()
 
 
 
seen=[[-1 for j in range(M)] for i in range(N)]
#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
 
 
dx=[1,0,-1,0]
dy=[0,1,0,-1]
ddx=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ddy=[2,1,0,-1,-2,2,1,-1,-2,2,-2,2,1,-1,-2,2,1,0,-1,-2]
 
 
def dfs(y,x):
 
    todox=deque()
    todoy=deque()
    seen[y][x]=0
    todox.append(x)
    todoy.append(y)
    count=0
    flug=True
    while flug==True:
        flug=False
        while len(todox) !=0:
            x=todox.popleft()
            y=todoy.popleft()
            for i in range(4):
                nx=x+dx[i]
                ny=y+dy[i]
                if nx>=0 and nx<M and ny>=0 and ny<N :
    
    
                            
                    if S[ny][nx]==".":
                        
                        
                        
                        if seen[ny][nx] ==-1:
                            #print("mohu",nx,ny)
                            seen[ny][nx] =seen[y][x]
                            todox.append(nx)
                            todoy.append(ny)
                        elif seen[ny][nx] >seen[y][x]:
                            seen[ny][nx] =seen[y][x]
                            todox.append(nx)
                            todoy.append(ny)
        for k in range(N):
            
            for j in range(M):
                if seen[k][j]==count:
                    for i in range(20):
                        nx=j+ddx[i]
                        ny=k+ddy[i]
                        if nx>=0 and nx<M and ny>=0 and ny<N :
                            if S[ny][nx]==".":
                                if seen[ny][nx] ==-1:
                                    #print("mohu",nx,ny)
                                    seen[ny][nx] =seen[k][j]+1
                                    todox.append(nx)
                                    todoy.append(ny)
                                elif seen[ny][nx] >seen[k][j]+1:
                                    seen[ny][nx] =seen[k][j]+1
                                    todox.append(nx)
                                    todoy.append(ny)
                    flug=True
                    
        count+=1

        
    return seen[goaly][goalx]
 
            
print(dfs(starty,startx))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
INF = float("inf")
import sys
input = sys.stdin.readline
from collections import*

def bfs():
    q = deque([(sx, sy)])
    dist = [[INF]*W for _ in range(H)]
    dist[sx][sy] = 0
    
    while q:
        x, y = q.popleft()
        if (x, y) == (gx, gy): return dist[gx][gy]
        for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
            if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                if c[nx][ny] == ".":
                    dist[nx][ny] = dist[x][y]
                    q.appendleft((nx, ny))
        for nx, ny in [(x-1, y-1), (x-1, y+1), (x+1, y+1), (x+1, y-1)]:
            if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                if c[nx][ny] == ".":
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))
        for nx in range(x-2, x+3):
            for ny in [y+2, y-2]:
                if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                    if c[nx][ny] == ".":
                        dist[nx][ny] = dist[x][y] + 1
                        q.append((nx, ny))
        for nx in [x+2, x-2]:
            for ny in range(y-1, y+2):
                if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                    if c[nx][ny] == ".":
                        dist[nx][ny] = dist[x][y] + 1
                        q.append((nx, ny))            
    return dist[gx][gy]

H, W = map(int, input().split())

cx, cy = map(int, input().split()); sx, sy = cx - 1, cy - 1
dx, dy = map(int, input().split()); gx, gy = dx - 1, dy - 1
c = [input()[:-1] for _ in range(H)]
ans = bfs()
print(ans if ans != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
import queue

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
#c->d

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

seen=[[0 for _ in range(w)] for _ in range(h)]
distance=[[10**7 for _ in range(w)] for _ in range(h)]

q=queue.Queue()

distance[ch][cw]=0
seen[ch][cw]=1
q.put([ch,cw])


while not q.empty():
  sth,stw=q.get()
  qi=queue.Queue()
  qi.put([sth,stw])
  ph=0
  pw=0
  wlis=[]
  while not qi.empty():
    ph,pw=qi.get()
    cntp=0
    for nearh,nearw in [[ph-1,pw],[ph+1,pw],[ph,pw-1],[ph,pw+1]]:
      if 0<=nearh<=h-1 and 0<=nearw<=w-1 and s[nearh][nearw]=="." and seen[nearh][nearw]==0:
        qi.put([nearh,nearw])
        seen[nearh][nearw]=1
        distance[nearh][nearw]=distance[ph][pw]
      if 0<=nearh<=h-1 and 0<=nearw<=w-1 and s[nearh][nearw]=="#":
        cntp+=1
    if cntp!=0:
      wlis.append([ph,pw])
  for i,j in wlis:
    for warph,warpw in [[i-2,j-2],[i-2,j-1],[i-2,j],[i-2,j+1],[i-2,j+2],
                        [i-1,j-2],[i-1,j-1],[i-1,j],[i-1,j+1],[i-1,j+2],
                        [i,j-2],[i,j-1],[i,j+1],[i,j+2],
                        [i+1,j-2],[i+1,j-1],[i+1,j],[i+1,j+1],[i+1,j+2],
                        [i+2,j-2],[i+2,j-1],[i+2,j],[i+2,j+1],[i+2,j+2]]:
      if 0<=warph<=h-1 and 0<=warpw<=w-1 and s[warph][warpw]==".":
        q.put([warph,warpw])
        seen[warph][warpw]=1
        distance[warph][warpw]=distance[i][j]+1

if distance[dh][dw]==10**7:
  print(-1)
else:
  print(distance[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())
CH -= 1
CW -= 1
DH -= 1
DW -= 1

mp = [input() for _ in range(H)]
ds = [[0,-1],[0,1],[-1,0],[1,0]]

memo1 = [[0]*W for _ in range(H)]

c = 0
for i in range(H):
  for j in range(W):
    if memo1[i][j] != 0:
      continue
    if mp[i][j] == '#':
      memo1[i][j] = -1
      continue
    h = deque([(i,j)])
    c += 1
    memo1[i][j] = c
    while h:
      t = h.popleft()
      for d in ds:
        if t[0]+d[0] >= 0 and t[0]+d[0] < H \
           and t[1]+d[1] >= 0 and t[1]+d[1] < W:
          if mp[t[0]+d[0]][t[1]+d[1]] == '.' and memo1[t[0]+d[0]][t[1]+d[1]] == 0:
            memo1[t[0]+d[0]][t[1]+d[1]] = c
            h.append((t[0]+d[0], t[1]+d[1]))
    
if memo1[CH][CW] == memo1[DH][DW]:
  print(0)
  exit()
    
ds = [[i,j] for i in range(-1,2) for j in range(-1,2)]
dic = {i:set([]) for i in range(1,c+1)}

for i in range(H):
  for j in range(W):
    if memo1[i][j] == -1:
      s = set([])
      for d in ds:
        if i+d[0] >= 0 and i+d[0] < H and j+d[1] >= 0 and j+d[1] < W:
          if memo1[i+d[0]][j+d[1]] > 0 and memo1[i+d[0]][j+d[1]] not in s:
            for u in s:
              dic[memo1[i+d[0]][j+d[1]]].add(u)
              dic[u].add(memo1[i+d[0]][j+d[1]])
            s.add(memo1[i+d[0]][j+d[1]])

s = memo1[CH][CW]
t = memo1[DH][DW]
  
lst = [10**9]*(c+1)
lst[s] = 0

h = deque([(s,0)])
while h:
  u = h.popleft()
  for v in dic[u[0]]:
    if lst[v] <= u[1]:
      continue
    lst[v] = lst[u[0]] + 1
    h.append((v,lst[v]))
    
    
if lst[t] == 10**9:
  print(-1)
else:
  print(lst[t])

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int,input().split())
sx, sy = map(int,input().split())
gx, gy = map(int,input().split())
S = [input() for i in range(h)]

sx-=1
sy-=1
gx-=1
gy-=1

A = [[-1,0],[1,0],[0,-1],[0,1]]
B = []
for i in range(-2,3):
    for j in range(-2,3):
        if i!= 0 or j!=0:
            B.append([i,j])
# print(B)

# O((V + E)log(V))
# Cは [[スタート頂点, ゴール頂点, 重み], ...] のリスト

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

for i in range(h):
    for j in range(w):
        if S[i][j] == ".":
            for a in A:
                ai = i+a[0]
                aj = j+a[1]
                if 0 <= ai < h and 0 <= aj < w and S[ai][aj] == ".":
                    M[i*w+j].append((ai*w+aj, 0))
            for b in B:
                bi = i+b[0]
                bj = j+b[1]
                if 0 <= bi < h and 0 <= bj < w and S[bi][bj] == ".":
                    M[i*w+j].append((bi*w+bj,1))


# for i in range(len(C)):

#     M[C[i][0]].append([C[i][1], C[i][2]])  # 無向グラフなら両方追加
#     M[C[i][1]].append([C[i][0], C[i][2]])  # 無向グラフなら両方追加

n = h*w

import heapq

D = [float("inf")] * n  # 頂点0からの距離
P = [-1] * n  # 頂点0からの最短距離において、そこの直前の頂点(経路復元に利用)
D[sx*w+sy] = 0
V = [0] * n  # その頂点のD[i]が最短距離と確定したら1
Q = []  # 優先度付きキュー
for v in range(n):
    heapq.heappush(Q, (D[v], v))

le = len(Q)
while le > 0:
    q = heapq.heappop(Q)
    u = q[1]
    du = q[0]
    if V[u] == 0:
        V[u] = 1
        le -= 1
        for i in range(len(M[u])):
            v = M[u][i][0]
            luv = M[u][i][1]
            # print(v)
            if V[v] == 0:
                alt = du + luv
                if D[v] > alt:
                    D[v] = alt
                    P[v] = u
                    heapq.heappush(Q, (alt, v))
# print(D)
ans = D[gx*w+gy]
if ans == float("inf"):
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline
 
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 = [input().rstrip() for _ in [0]*H]
 
INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()
 
q = []
heappush(q, (0, Ch*W+Cw))
 
dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
wps = [
    [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -1), (-1, 1)],
    [(2, 2), (2, -1), (2, 0), (2, 1), (2, 2), (1, -1), (1, 1)],
    [(-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (-1, 1), (1, 1)],
    [(-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2), (-1, -1), (1, -1)]
]
 
while q:
    d, ij = heappop(q)
    i, j = divmod(ij, W)
    used.add((i, j))
    if D[i][j] > d:
        D[i][j] = d
    else:
        continue
    if i == Dh and j == Dw:
        break
 
    for k, (di, dj) in enumerate(dirs):
        _i = i + di
        _j = j + dj
        if 0 <= _i < H and 0 <= _j < W:
            if (_i, _j) in used:
                continue
            if S[_i][_j] == '.':
                used.add((_i, _j))
                heappush(q, (d, _i*W+ _j))
            else:
                for di, dj in wps[k]:
                    _i = i + di
                    _j = j + dj
                    if 0 <= _i < H and 0 <= _j < W and (_i, _j) not in used and S[_i][_j] == '.':
                        heappush(q, (d+1, _i*W+ _j))
 
ans = D[Dh][Dw]
print(ans if ans < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
cx,cy=map(int,input().split())
cx+=1
cy+=1
dx,dy=map(int,input().split())
dx+=1
dy+=1
l=[]
l.append("#"*(w+4))
l.append("#"*(w+4))
for i in range(h):
    l.append("##"+input()+"##")
l.append("#"*(w+4))
l.append("#"*(w+4))
#input

"""
for i in l:
    print(*i)
"""

q=deque([[cx,cy]])
qq=deque([[cx,cy]])
s=[[-1 for i in j]for j in l]
s[cx][cy]=0

while len(qq)>0:
    while len(q)>0:
        x,y=q.popleft()
        for px,py in ((0,1),(0,-1),(1,0),(-1,0)):
            if l[x+px][py+y]=="." and s[x+px][y+py]==-1:
                s[x+px][y+py]=s[x][y]
                q.appendleft([x+px,y+py])
                qq.append([x+px,y+py])
    x,y=qq.popleft()
    for px in range(-2,3):
        for py in range(-2,3):
            if l[x+px][py+y]=="." and s[x+px][y+py]==-1:
                s[x+px][y+py]=s[x][y]+1
                q.append([x+px,y+py])
                qq.append([x+px,y+py])
"""
for i in s:
    print(*i)
"""

print(s[dx][dy])

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**10

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(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 [i,j] in [[-1,0],[1,0],[0,-1],[0,1]]:
                if lin[nx][ny] > lin[x][y]:
                    que.append((nx,ny))
                    lin[nx][ny] = lin[x][y]# 直接行ける
            else:
                if lin[nx][ny] > lin[x][y]+1:
                    que.append((nx,ny))
                    lin[nx][ny] = lin[x][y]+1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
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)

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

#print(dist)
#print(prev)

dist_mat=[[-1]*(W+4) for _ in range(H+4)]
queue=[(Ch+1,Cw+1)]
d=0
while queue:
  new_queue=set()

  while queue:
    ux,uy=queue.pop()
    if ux==Dh+1 and uy==Dw+1:
      print(d)
      sys.exit(0)
    dist_mat[ux][uy]=d
    
    for v,w in graph[(ux,uy)]:
      vx,vy=v
      if dist_mat[vx][vy]!=-1:
        continue
      if w==0:
        queue.append(v)
      else:
        new_queue.add(v)

  queue=list(new_queue)
  d+=1
#print(dist)

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1<<20)
h,w=[int(x) for x in input().split()]
ch,cw=[int(x) for x in input().split()]
dh,dw=[int(x) for x in input().split()]
ch-=1
cw-=1
dh-=1
dw-=1

s=[]
for _ in range(h):
    s.append(list(input()))

nxt=[[ch,cw,0]]
#再起
def rcl(y,x,now):
    
    if y==dh and x==dw:
        print(now)
        exit()
    
    if s[y][x]=='#':
        return
    
    s[y][x]='#'
    #5*5
    for i in range(-2,3):
        for j in range(-2,3):
            if i==0 and j==0:
                continue
            if y+i<0 or h<=y+i:
                continue
            if x+j<0 or w<=x+j:
                continue
            if s[y+i][x+j]!='#':
                nxt.append([y+i,x+j,now+1])
    # 四方を見る
    for i in range(4):
        yy,xx=-1,0
        if i==1:yy,xx=0,1
        if i==2:yy,xx=1,0
        if i==3:yy,xx=0,-1
        
        if y+yy<0 or h<=y+yy or x+xx<0 or w<=x+xx:
            continue
        if s[y+yy][x+xx]=='#':
            continue
        rcl(y+yy,x+xx,now)


while nxt:
    i=nxt.pop(0)
    if i[0]==dh and i[1]==dw:
        print(i[2])
        exit()
    rcl(i[0],i[1],i[2])
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

def input():
    return sys.stdin.readline()[:-1]

from collections import deque
import heapq
def main():
    H,W = list(map(int,input().split()))
    s1,s2 = list(map(int,input().split()))
    g1,g2 = list(map(int,input().split()))
    s1,s2 = s1-1,s2-1
    g1,g2 = g1-1,g2-1
    S = [input() for i in range(H)]

    def z(i,j):
        return i*W + j

    e_list = [[] for i in range(H*W)]

    for i in range(H):
        for j in range(W):
            if i!=H-1:
                if S[i][j]=="." and S[i+1][j]==".":
                    e_list[z(i,j)].append((z(i+1,j),0))
                    e_list[z(i+1,j)].append((z(i,j),0))
            if j!=W-1:
                if S[i][j]=="." and S[i][j+1]==".":
                    e_list[z(i,j)].append((z(i,j+1),0))
                    e_list[z(i,j+1)].append((z(i,j),0))

    for x in range(H*W):                
        i,j = x//W,x%W
        if S[i][j]==".":
            for y in range(25):
                i1,j1 = y//5,y%5
                i2 = i1 + i - 2
                j2 = j1 + j - 2
                if abs(j2-j)<=1 and i2==i:
                    continue
                if abs(i2-i)<=1 and j2==j:
                    continue
                if 0<=i2 and i2<=H-1 and 0<=j2 and j2<=W-1:
                    if S[i2][j2]=="#":
                        continue
                    e_list[z(i2,j2)].append((z(i,j),1))
                    e_list[z(i,j)].append((z(i2,j2),1))
    #dijkstra
    #you need to prepare e_list = [(orient,dist)]
    
    N=H*W    
    vi = z(s1,s2)
    INF = float('inf')
    min_d_list = [INF]*N
    min_d_list[vi] = 0
    prev_list = [-1]*N
    q = []
    for i in range(N):
        heapq.heappush(q,(min_d_list[i],i))
    
    while len(q)>0:
        d,v = heapq.heappop(q)
        for e in e_list[v]:
            v1,d1 = e
            if min_d_list[v1] > d+d1:
                min_d_list[v1] = d+d1
                prev_list[v1] = v
                heapq.heappush(q,(d+d1,v1))

    if min_d_list[z(g1,g2)]<=10**26:
        print(min_d_list[z(g1,g2)])
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

#input = sys.stdin.readline

########################################
def valid(a,b):
	#print(a,b)
	if 0<=a<=h-1 and 0<=b<=w-1 and arr[a][b] == ".":
		return True
	else:
		return False


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
arr = [list(input()) for i in range(h)]
#print(arr)
can_vis = []
dist = [[10**10]*w for i in range(h)]
q = deque()
ans = float("inf")
q.append((ch,cw))
dist[ch][cw] = 0
#print(dh,dw,ch,cw)
while q:
	#print(q.popleft())
	#print(q)
	curx , cury = q.popleft()
	#can_vis.append((curx,cury))
	for dx,dy in [[1,0],[0,1],[-1,0],[0,-1]]:
		if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
			dist[curx+dx][cury+dy] = dist[curx][cury]
			q.append((curx+dx, cury+dy))
	for dx in range(-2,3):
		for dy in range(-2,3):
			if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
				dist[curx+dx][cury+dy] = dist[curx][cury] + 1 
				q.append((curx+dx, cury+dy))


if dist[dh][dw] == 10**10:
	print(-1)
else:
	print(dist[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
cy, cx = map(int, input().split())
dy, dx = map(int, input().split())
cy -= 1
cx -= 1
dy -= 1
dx -= 1

S = [input() for _ in range(H)]

worps = [[float('inf')]*W for _ in range(H)]
used = [[False]*W for _ in range(H)]
q = deque([[cy, cx]])

worp = 0
while q:
    v = {}
    while q:
        y, x = q.popleft()
        used[y][x] = True
        worps[y][x] = min(worps[y][x], worp)

        for h in range(-2+y, 3+y):
            for w in range(-2+x, 3+x):
                if 0 <= h and h < H and 0 <= w and w < W and S[h][w] == ".":
                    v[(h, w)] = True

        for h, w in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            ny, nx = y+h, x+w
            if 0 <= ny and ny < H and 0 <= nx and nx < W:
                if not used[ny][nx] and S[ny][nx] == ".":
                    q.append([ny, nx])

    worp += 1
    for h, w in v.keys():
        if not used[h][w]:
            q.append([h, w])
            used[h][w] = True

ans = worps[dy][dx]
if ans != float('inf'):
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
Ch, Cw = [int(s) - 1 for s in input().split()]
Dh, Dw = [int(s) - 1 for s in input().split()]
S = [input() for _ in range(H)]

tree_check = [[0 for _ in range(W)] for _ in range(H)]


def tree(way_start):
    result = []
    while way_start:
        way = way_start.pop(0)
        y = way[0]
        x = way[1]
        tree_check[y][x] = 1
        result.append([y, x])
        if x - 1 >= 0:
            if S[y][x - 1] == '.':
                if tree_check[y][x - 1] == 0:
                    tree_check[y][x - 1] = 1
                    way_start.append([y, x - 1])
                    result.append([y, x - 1])
        if x + 1 < W:
            if S[y][x + 1] == '.':
                if tree_check[y][x + 1] == 0:
                    tree_check[y][x + 1] = 1
                    way_start.append([y, x + 1])
                    result.append([y, x + 1])
        if y - 1 >= 0:
            if S[y - 1][x] == '.':
                if tree_check[y - 1][x] == 0:
                    tree_check[y - 1][x] = 1
                    way_start.append([y - 1, x])
                    result.append([y - 1, x])
        if y + 1 < H:
            if S[y + 1][x] == '.':
                if tree_check[y + 1][x] == 0:
                    tree_check[y + 1][x] = 1
                    way_start.append([y + 1, x])
                    result.append([y + 1, x])
    return result


def warp(warp_list):
    result = []
    for way in warp_list:
        h = way[0]
        w = way[1]
        if tree_check[h][w] == 1:
            for i in range(-2, 2 + 1):
                if 0 <= h + i < H:
                    for j in range(-2, 2 + 1):
                        if 0 <= w + j < W:
                            if tree_check[h + i][w + j] == 0:
                                if S[h + i][w + j] == '.':
                                    result.append([h + i, w + j])
    return result


way_tree = [[Ch, Cw]]
ans = 0
while way_tree:
    warp_point = tree(way_tree)
    if tree_check[Dh][Dw] == 0:
        ans += 1
        way_tree = warp(warp_point)
    else:
        break

if tree_check[Dh][Dw] == 0:
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:

from collections import deque


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

warp_list = [(-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)]

maze = []
warp_count = []
for _ in range(H):
    line = list([x for x in input()])
    maze.append(line)
    warp_count.append([10**9] * W)

queue = deque()
queue.appendleft((Ch, Cw, 0))

answer = 10**9
while queue:
    def maze_check(h, w, use_magic):
        if h < 0 or H <= h:
            return False
        if w < 0 or W <= w:
            return False
        if maze[h][w] == '#':
            return False
        if warp_count[h][w] <= use_magic:
            return False

        return True

    now_h, now_w, use_magic = queue.popleft()
    warp_count[now_h][now_w] = use_magic

    if now_h == Dh and now_w == Dw:
        if answer > use_magic:
            answer = use_magic

        continue

    # 上下左右に移動
    do_warp = True
    if maze_check(now_h+1, now_w, use_magic):
        queue.appendleft((now_h + 1, now_w, use_magic))
        do_warp = False
    if maze_check(now_h-1, now_w, use_magic):
        queue.appendleft((now_h - 1, now_w, use_magic))
        do_warp = False
    if maze_check(now_h, now_w+1, use_magic):
        queue.appendleft((now_h, now_w + 1, use_magic))
        do_warp = False
    if maze_check(now_h, now_w-1, use_magic):
        queue.appendleft((now_h, now_w - 1, use_magic))
        do_warp = False

    if do_warp:
        for y, x in warp_list:
            warp_h = now_h + y
            warp_w = now_w + x

            if maze_check(warp_h, warp_w, use_magic+1):
                queue.appendleft((warp_h, warp_w, use_magic+1))


if answer == 10**9:
    print(-1)
else:
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict
from itertools import combinations
INF = float('inf')

def dijkstra_al(s, n, ALcost, start_index = 0):
    '''
    ダイクストラ法 O(|E|log|V|)
    グラフを隣接リストで表す場合
    始点sから各頂点への最短距離
    n: 頂点の数、s: 始点
    cost存在しないときはinf
    start_index: 0のときvertexは0, 1, ..., n-1
                 1のときvertexは1, 2, ..., n
    '''
    import heapq


    fixed = [False] * (n + 1) # 重み確定したかどうか
    nfixed = 0 # 確定した数
    vertex_cost = [INF] * (n + 1)  # 始点sから各頂点への重み

    # 1. 始点に0を書き込む
    vertex_cost[s] = 0
    H = []  # (cost, vertex)のheap
    heapq.heappush(H, (0, s))

    while(H): # Hが空になるまで
        # 2. 未確定の地点の中からもっとも小さい値を持つ地点を1つ選び、その値を確定させる
        u_cost, u = heapq.heappop(H)
        if fixed[u]: continue  # 取り出した頂点がすでに決まっている（古い情報）
        fixed[u] = True
        nfixed += 1

        # 3. 2で確定した地点から直接繋がっていて、かつ未確定な地点に対し、
        #    重みを計算し、書き込まれている値より小さければ更新する
        # for v, edge_cost in ALcost[u]:
        for v in ALcost[u]:
            edge_cost = 1
            if fixed[v]: continue
            newcost = u_cost + edge_cost
            if newcost < vertex_cost[v]:
                vertex_cost[v] = newcost
                heapq.heappush(H, (newcost, v))

        # 4. 全ての地点が確定していれば終了。そうでなければ2に戻る
        if nfixed == n: break

    if start_index == 0:
        return vertex_cost[:n]
    else:
        return vertex_cost # index 0はダミー

H, W = [int(x) for x in input().split()]
sy, sx = [int(x) - 1 for x in input().split()]
gy, gx = [int(x) - 1 for x in input().split()]
S = [list(input()) for _ in range(H)]
grp = [[-1 for _ in range(W)] for _ in range(H)]

y = 0
x = 0
k = 0
for iy in range(H):
    for ix in range(W):
        if S[iy][ix] == '#' or grp[iy][ix] >= 0: continue
        que = deque([(iy, ix)])
        grp[iy][ix] = k
        while que:
            y, x = que.popleft()
            for dy, dx in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                ny = y + dy
                nx = x + dx
                if ny < 0 or H <= ny or nx < 0 or W <= nx:
                    continue
                if S[ny][nx] == '#' or grp[ny][nx] >= 0: # 行けないか訪問済み
                    continue
                grp[ny][nx] = k
                que.append((ny, nx))
        k += 1


AL = [[] for _ in range(k)]
E = defaultdict(bool)

for iy in range(H):
    for ix in range(W):
        if grp[iy][ix] < 0: continue

        que = deque([(iy, ix)])
        while que:
            y, x = que.popleft()
            for dy, dx in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                ny = y + dy
                nx = x + dx
                if ny < 0 or H <= ny or nx < 0 or W <= nx:
                    continue
                if S[ny][nx] == '#' or grp[ny][nx] >= 0:  # 行けないか訪問済み
                    continue
                grp[ny][nx] = k
                que.append((ny, nx))

w = min(3, W)
h = min(3, H)
for y in range(H - h + 1):
    for x in range(W - w + 1):
        dict = defaultdict(bool)
        for dy in range(h):
            for dx in range(w):
                ny = y + dy
                nx = x + dx
                if grp[ny][nx] >= 0:
                    dict[grp[ny][nx]] = True
        for a, b in combinations(dict.keys(), 2):
            if E[(a, b)] == True:  continue
            E[(a, b)] = True
            E[(b, a)] = True
            AL[a].append(b)
            AL[b].append(a)


cost = dijkstra_al(grp[sy][sx], k, AL)
ans = cost[grp[gy][gx]]
print(-1 if ans == INF else ans)