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 io import StringIO
import unittest

def resolve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = []
    for h in range(H):
        Sh =  list(input())
        S.append(Sh)

    que = {(Ch-1,Cw-1)}
    jump_que = set()
    goal = (Dh-1, Dw-1)
    # searched=set()
    searched = [[False for i in range(W)] for i in range(H)]
    jump =0

    while(True):
        while(len(que)):
            tmp = que.pop()
            if tmp ==goal:
                print(jump)

                return

            searched[tmp[0]][tmp[1]] = True
            nxts=get_around(S,H,W,tmp[0],tmp[1], searched)
            # print(f'nxts: {nxts}')
            que=que|nxts
            jump_nxts = get_jump_around(S, H, W, tmp[0], tmp[1], searched)
            # print(f'jump_nxts: {jump_nxts}')
            jump_que = jump_que | jump_nxts
            # print(f'jump_que: {jump_que}')

        jump=jump+1
        que=jump_que
        jump_que = set()
        if len(que)==0:
            print('-1')
            return


def get_around(S,H,W, h,w, searched):
    hm = h-1
    hp =h+1
    wm = w-1
    wp= w+1
    nxt=set()
    if hm>=0 and S[hm][w]=='.' and not searched[hm][w]:
        nxt.add((hm,w))

    if hp<H and S[hp][w]=='.'and not searched[hp][w]:

        nxt.add((hp,w))
    if wm>=0 and S[h][wm]=='.'and not searched[h][wm]:
        nxt.add((h,wm))

    if wp<W and S[h][wp]=='.'and not searched[h][wp]:
        nxt.add((h,wp))
    return nxt

def get_jump_around(S,H,W, h,w, searched):
    hm = max(h-2,0)
    hp =min(h+2,H-1)
    wm = max(w-2,0)
    wp= min(w+2,W-1)
    nxt=set()
    # print(hm,hp,wm,wp)
    for h in range(hm,hp+1):
        for w in range(wm, wp + 1):
            if S[h][w]=='.' and not searched[h][w]:
                nxt.add((h, w))

    return nxt


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(output,out)

    def test_入力例_1(self):
        input = """4 4
1 1
4 4
..#.
..#.
.#..
.#.."""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4 4
1 4
4 1
.##.
####
####
.##."""
        output = """-1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """4 4
2 2
3 3
....
....
....
...."""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """4 5
1 2
2 5
#.###
####.
#..##
#..##"""
        output = """2"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()

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

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

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

ans[ch-1][cw-1]=0

qu = deque([])
qu.append([cw-1,ch-1])
while qu:
  zahyou=qu.popleft()
  x=zahyou[0]
  y=zahyou[1]
  count=[0,0,0,0]
  count2=0
  for i in range(4):
    if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h:
      if maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):
        qu.append([x+dx[i],y+dy[i]])
        ans[y+dy[i]][x+dx[i]] = ans[y][x]
        count[i]=1
        count2+=1
  if count2<3 or (count==[1,0,0,1] or count==[1,1,0,0] or count==[0,1,1,0] or count==[0,0,1,1]):
    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        if 0<=i<w and 0<=j<h:
          if maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
            ans[j][i]=(ans[y][x]+1)
            qu.append([i,j])

print(ans[dh-1][dw-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
from collections import deque

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")

INF = float("inf")

H,W = LI()
C = LI()
D = LI()
maze = [list(_S()) for i in range(H)]

def bfs(H,W,C,D,maze):
    ans = -1
    # すべてのマスを INF で初期化
    d = [[INF] * W for i in range(H)]
    
    sx = C[0]-1
    sy = C[1]-1
    gx = D[0]-1
    gy = D[1]-1

    # スタート地点をキューに入れ、ワープ数を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    que2 = deque([])

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    while que: 
        while que:
            p = que.popleft()       
            # 取り出してきた状態がゴールなら探索をやめる
            if p[0] == gx and p[1] == gy:
                ans = d[p[0]][p[1]]
                print(ans)
                exit()
            que2.append((p[0], p[1]))
            # 移動4方向をループ
            for i in range(4):
                # 移動した後の点を (nx, ny) とする
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]

                # 移動可否判定、d[nx][ny] == INF であれば訪れたことがない
                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and d[nx][ny] == INF:
                    # 移動できるならキューに入れ、その点のワープ回数を p までのワープ回数で確定する
                    que.append((nx, ny))
                    d[nx][ny] = d[p[0]][p[1]]
                    
        # print('after que: ',d)
        # dx = [-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0, 1, 1,  1,  1, 2, 2, 2,  2, 2]
        # dy = [-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, 2, 1, -1, -2, 2, 1, 0, -1, -2]
        while que2:
            # キューの先頭を取り出す
            p = que2.popleft()
            # for i in range(20):
            for dxi in range(-2,3):
                for dyi in range(-2,3):
                    nx = p[0] + dxi
                    ny = p[1] + dyi
                    if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and d[nx][ny] == INF:
                        # 移動できるならキューに入れ、その点のワープ回数を p からのワープ回数 +1 で確定する
                        que.append((nx, ny))
                        d[nx][ny] = d[p[0]][p[1]]+1  
        # print('after que2: ',d)  
    return

bfs(H,W,C,D,maze)
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W = map(int,input().split())
C_pos=list(map(lambda x:int(x)-1,input().split()))
D_pos=list(map(lambda x:int(x)-1,input().split()))
Grid=[[c for c in input()] for _ in range(H)]

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

DX=[0,0,1,-1]

Q=deque()
Q.append((C_pos[0],C_pos[1]))
Dist[C_pos[0]][C_pos[1]]=0

while Q:
    cx,cy = Q.pop()

    for dx,dy in zip(DX,reversed(DX)):
        nx=cx+dx
        ny=cy+dy

        if 0<=nx<H and 0<=ny<W and Grid[nx][ny]=="." and Dist[nx][ny]>Dist[cx][cy]:
            Dist[nx][ny]=Dist[cx][cy]
            Q.append((nx,ny))


    for dx in range(-2,3):
        for dy in range(-2,3):
            nx=cx+dx
            ny=cy+dy
            if dx==0 and dy==0:
                continue

            if 0<=nx<H and 0<=ny<W and Grid[nx][ny]=="." and Dist[nx][ny]==float("inf"):
                Dist[nx][ny]=Dist[cx][cy]+1
                Q.appendleft((nx,ny))


ans=Dist[D_pos[0]][D_pos[1]]
if ans==float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000) 
input = sys.stdin.readline
from collections import deque
from heapq import heapify, heappop, heappush
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)]
Q = deque([])
Q.append([0,C])
while Q:
  score,z = heappop(Q)
  x = z[0];y=z[1]
 
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    #print(nx,ny)
    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]
      heappush(Q,[score,u])
  #print(reach)
 
  for i in range(5): #0~4
    for j in range(5):
      mx = x-2 + i
      my = y-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]
      #print(v,p,"X")
      heappush(Q,[score+1,p])
#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:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
g = [[] for _ in range(H*W)]
for _ in range(H):
    maze.append(readline().rstrip().decode('utf-8'))
for h in range(H):
    for w in range(W):
        if maze[h][w] == ".":
            for i in range(3):
                for j in range(5):
                    if i == 2 and j == 2:
                        continue
                    if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                        if maze[h+i-2][w+j-2] == ".":
                            #h*W+w,(h+i-2)*W+w+j-2
                            fr,go = h*W+w,(h+i-2)*W+w+j-2
                            if abs(i-2)+abs(j-2) <= 1:
                                g[fr].append((0,go))
                                g[go].append((0,fr))
                            else:
                                g[fr].append((1,go))
                                g[go].append((1,fr))

#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge): #s:始点,g:グラフ
    #始点sから各頂点への最短距離
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) #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] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)
 
res = dijkstra_heap(sh*W+sw,g)
 
if res[gh*W+gw] == float("inf"):
    print(-1)
else:
    print(res[gh*W+gw])

Submission status: Time Limit Exceeded

Solution code:
import sys


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2
    now = ch*W + cw
    goal = dh*W + dw
    q = [now]
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[now] = 0

    while q:
        same_area = []
        while q:
            x = q.pop()
            same_area.append(x)
            for d in [-W, -1, 1, W]:
                if S[x+d] == '.' and dist[x+d] > dist[x]:
                    q.append(x+d)
                    dist[x+d] = dist[x]
        
        for x in same_area:
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in range(-2, 3):
                    xx = x + dy + dx
                    if 0 <= xx < W*H and dist[xx] > dist[x] and S[xx] == '.':
                        q.append(xx)
                        dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
g = [[] for _ in range(H*W)]
for _ in range(H):
    maze.append(readline().rstrip().decode('utf-8'))
for h in range(H):
    for w in range(W):
        if maze[h][w] == ".":
            for i in range(5):
                for j in range(5):
                    if i == 2 and j == 2:
                        continue
                    if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                        if maze[h+i-2][w+j-2] == ".":
                            #h*W+w,(h+i-2)*W+w+j-2
                            fr,go = h*W+w,(h+i-2)*W+w+j-2
                            if abs(i-2)+abs(j-2) <= 1:
                                g[fr].append((0,go))
                                #g[go].append((0,fr))
                            else:
                                g[fr].append((1,go))
                                #g[go].append((1,fr))

#ダイクストラ法通常版
#O(ElogV)
import heapq
def dijkstra_heap(s,edge): #s:始点,g:グラフ
    #始点sから各頂点への最短距離
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) #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] #vに頂点を代入
        d[v] = minedge[0] #その頂点のコストに重みを代入
        used[v] = False #vには最小距離が入っていることが証明できる(ヒープキューを使用しているため)
        for e in edge[v]: #頂点vから伸びている辺の先をヒープキューに入れてく
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d #回しきったらreturn(たどり着けなかった頂点はinf.)
 
res = dijkstra_heap(sh*W+sw,g)
 
if res[gh*W+gw] == float("inf"):
    print(-1)
else:
    print(res[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())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

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

ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    count=[0,0,0,0]
    count2=0
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h:
        if maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):
          qu.append([x+dx[i],y+dy[i]])
          ans[y+dy[i]][x+dx[i]] = ans[y][x]
          count[i]=1
          count2+=1
    if count2<3 or (count==[1,0,0,1] or count==[1,1,0,0] or count==[0,1,1,0] or count==[0,0,1,1]):
      for i in range(x-2,x+3):
        for j in range(y-2,y+3):
          if 0<=i<w and 0<=j<h:
            if maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
              ans[j][i]=(ans[y][x]+1)
              qu.append([i,j])

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

S=[]
for i in range(H):
  s=list(input())
  S.append([-1 if i =="." else -2 for i in s])

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

while dq:
  a=dq.pop()
  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 and abs(i-2)+abs(j-2)==1 and (S[a[0]-2+i][a[1]-2+j]==-1 or S[a[0]-2+i][a[1]-2+j]>S[a[0]][a[1]]):
        S[a[0]-2+i][a[1]-2+j]=S[a[0]][a[1]]
        dq.appendleft((a[0]-2+i,a[1]-2+j))
      elif a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W and (S[a[0]-2+i][a[1]-2+j]==-1 or S[a[0]-2+i][a[1]-2+j]>S[a[0]][a[1]]+1):
        S[a[0]-2+i][a[1]-2+j]=S[a[0]][a[1]]+1
        dq.append((a[0]-2+i,a[1]-2+j))

print(S[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W = mapint()
ch, cw = mapint()
dh, dw = mapint()
maze = [list(input()) for _ in range(H)]

dirc = set([(-1, 0), (1, 0), (0, -1), (0, 1)])
from collections import deque
from heapq import heappop, heappush
Q = [(0, (ch-1)*(10**4)+cw-1)]

dist = [[10**18]*W for _ in range(H)]
dist[ch-1][cw-1] = 0
ans = 10**18
while Q:
    d, yx = heappop(Q)
    y, x = divmod(yx, 10**4)
    if d>dist[y][x]:
        continue
    dist[y][x] = d
    if y==dh-1 and x==dw-1:
        ans = d
        break
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            ny, nx = y+dy, x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if maze[ny][nx]=='#':
                continue
            if (dy, dx) in dirc:
                if dist[ny][nx]>d:
                    heappush(Q, (d, ny*(10**4)+nx))
            else:
                if dist[ny][nx]>d+1:
                    heappush(Q, (d+1, ny*(10**4)+nx))
if ans>=10**17:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
 
dx = [-1,0,1,0]
dy = [0,-1,0,1]
 
def bfs(ch,cw):
    q = [queue.Queue() for _ in range(1000000)]#queue.Queue()
    
    S[ch][cw] = 0
    q[S[ch][cw]].put([ch,cw])
    
    counter = 0
    
    while True:
        if q[counter].empty():
          counter += 1
          if q[counter].empty():
              break
        p = q[counter].get()
        
        if p[0]==dh and p[1]==dw:
            break
        
        for i in range(4):
            next_p = [p[0]+dx[i],p[1]+dy[i]]
            if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                continue
            if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]:
                S[next_p[0]][next_p[1]] = S[p[0]][p[1]]
                q[counter].put(next_p)
                
                
        for i in range(-2,3):
            for j in range(-2,3):
                if (i == 0 and j == 0) or (i==-1 and j==0)or(i==1 and j==0)or(i==0 and j==-1)or (i==0 and j==1):
                    continue
                next_p = [p[0]+i,p[1]+j]
                if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                    continue
                if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]+1:
                    S[next_p[0]][next_p[1]] = S[p[0]][p[1]]+1
                    q[counter+1].put(next_p)
                    
            
    return 
        
h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch -= 1
cw -= 1
dh,dw = map(int,input().split())
dh -= 1
dw -= 1
S = [list(input()) for _ in range(h)]
 
for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            S[i][j] = float('inf')
        else:
            S[i][j] = -1
 
 
bfs(ch,cw)
if S[dh][dw] != float('inf'):
    print(S[dh][dw])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


h,w=map(int,input().split())
c=list(map(int,input().split()))
d=list(map(int,input().split()))
s=[list(input()) for _ in range(h)]


for y in range(h):
    s[y]=[10000000 if s[y][x]=="." else s[y][x] for x in range(w)]


s[c[0]-1][c[1]-1]=0
que=deque([[c[0]-1,c[1]-1]])
while que:
    y,x=que.popleft()
    for i,j in [(1,0),(0,1),(-1,0),(0,-1),(2,2),(2,1),(2,0),(2,-1),(2,-2),(1,2),(1,1),(1,-1),(1,-2),(0,2),(0,-2),(-1,2),(-1,1),(-1,-1),(-1,-2),(-2,2),(-2,1),(-2,0),(-2,-1),(-2,-2)]:
        if 0<=y+i<h and 0<=x+j<w:
            nexty,nextx=y+i,x+j
            dist=s[nexty][nextx]
            if dist!='#':
                if i*i+j*j==1:
                    if dist>s[y][x]:
                        s[nexty][nextx]=s[y][x]
                        que.append([nexty,nextx])
                elif dist>s[y][x]+1:
                    s[nexty][nextx]=s[y][x]+1
                    que.append([nexty,nextx])

if s[d[0]-1][d[1]-1]==10000000:
    print(-1)
else:
    print(s[d[0]-1][d[1]-1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 15 17:00:46 2020

@author: saito
"""

# %% import phase
from collections import deque

# %% define phase

def check(s, x, y, o, cnt, h, w):
    for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        if x+i>=0 and y+j>=0 and \
            x+i<=h-1 and y+j<=w-1 and\
            s[x+i][y+j] == '.':
            o.append([x+i, y+j, cnt])
            s[x+i][y+j] = str(cnt)
    return o, s

def wcheck(s, x, y, o, cnt, h, w):
    for i in range(5):
        a = i-2
        for j in range(5):
            b = j-2
            if x+a>=0 and y+b>=0 and \
            x+a<=h-1 and y+b<=w-1 and\
            s[x+a][y+b] == '.':
#            if s[x+a][y+b] == '.':
                if [x+a, y+b] not in o:
                    o.append([x+a, y+b, cnt+1])    
    return o
    
def bfs(s, x, y, dh, dw, h, w):
    cnt = 0
    f = deque()
    wf = deque()
    wf.append([x, y, cnt])
    while wf:
        [x, y, ncnt] = wf.popleft()
        if s[x][y] == '.':
            cnt = ncnt
            s[x][y] = str(cnt)
            f.append([x, y, cnt])
#            print('--------')
#            for si in s:
#                print(si)
#            print('--------')
            while f:
                [x, y, cnt] = f.popleft()
    #            if [x, y, cnt+1] in wf:
    #                wf.remove([x, y, cnt+1])
                if [x, y] == [dh, dw]:
#                    print('--------')
#                    for si in s:
#                        print(si)
#                    print('--------')
                    wf.clear()
                    return cnt
                f, s = check(s, x, y, f, cnt, h, w)
                wf = wcheck(s, x, y, wf, cnt, h, w)
    return -1

    
    

# %% input phase
h, w = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
ch -= 1
cw -= 1
dh, dw = list(map(int, input().split()))
dh -= 1
dw -= 1
s = [[] for _ in range(h)]
for i in range(h):
    s[i] = list(input())

# %% process phase
ans = bfs(s, ch, cw, dh, dw, h, w)

    

# %%output phase
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import collections
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

Chw = list(map(int, input().split()))
Dhw = list(map(int, input().split()))

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

mazeArray = np.zeros((H+6, W+6), dtype = 'int64')

for i in range(H+6):
    for j in range(W+6):
        if(i < 3 or i > H+2):
            mazeArray[i][j] = -1
        
        elif(j < 3 or j > W+2):
            mazeArray[i][j] = -1
        
        else:
            if(Ss[i - 3][j-3] == "#"):
                mazeArray[i][j] = -1
            else:
                mazeArray[i][j] = 100000

#前準備完了

H_que = collections.deque()
W_que = collections.deque()

H_que.append(Chw[0])
W_que.append(Chw[1])

mazeArray[Chw[0]+2][Chw[1]+2] = 0

#print(mazeArray)

for _ in range(10**5):
    H_iti = H_que.popleft() + 2
    W_iti = W_que.popleft() + 2

    #上移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti - 1][W_iti]):
        mazeArray[H_iti - 1][W_iti] = mazeArray[H_iti][W_iti]

        H_que.appendleft(H_iti - 3)
        W_que.appendleft(W_iti - 2)

    elif(mazeArray[H_iti - 1][W_iti] == -1):
        for i in range(H_iti-2, H_iti):
            for j in range(W_iti -2, W_iti + 3):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)
                
    #下移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti + 1][W_iti]):
        mazeArray[H_iti + 1][W_iti] = mazeArray[H_iti][W_iti]

        H_que.appendleft(H_iti - 1)
        W_que.appendleft(W_iti - 2)
        
    elif(mazeArray[H_iti+1][W_iti] == -1):
        for i in range(H_iti+1, H_iti+3):
            for j in range(W_iti -2, W_iti + 3):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)

    #左移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti][W_iti - 1]):
        mazeArray[H_iti][W_iti - 1] = mazeArray[H_iti][W_iti]

        H_que.appendleft(H_iti - 2)
        W_que.appendleft(W_iti - 3)

    elif(mazeArray[H_iti][W_iti-1] == -1):
        for i in range(H_iti-2, H_iti+3):
            for j in range(W_iti -2, W_iti):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)

    #右移動
    if(mazeArray[H_iti][W_iti] < mazeArray[H_iti][W_iti + 1]):
        mazeArray[H_iti][W_iti + 1] = mazeArray[H_iti][W_iti]

        H_que.appendleft(H_iti - 2)
        W_que.appendleft(W_iti - 1)

    elif(mazeArray[H_iti][W_iti-1] == -1):
        for i in range(H_iti-2, H_iti+3):
            for j in range(W_iti +1, W_iti + 3):
                if(mazeArray[H_iti][W_iti] < mazeArray[i][j]):
                    mazeArray[i][j] = mazeArray[H_iti][W_iti] + 1

                    H_que.append(i - 2)
                    W_que.append(j - 2)

    if(len(H_que) == 0):
        break

#print(mazeArray)

if(mazeArray[Dhw[0]+2][Dhw[1]+2] == 100000):
    print(-1)

else:
    print(mazeArray[Dhw[0]+2][Dhw[1]+2])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import heapq

def main():
	h,w=MI()
	ch,cw=MI()
	dh,dw=MI()
	ch+=1
	cw+=1
	dh+=1
	dw+=1

	S=[["#"]*(w+4)]
	S.append(["#"]*(w+4))
	for _ in range(h):
		S.append(["#"]*2+list(RD())+["#"]*2)
	S.append(["#"]*(w+4))
	S.append(["#"]*(w+4))

	#print(S)

	Q=[[0,ch,cw]]
	heapq.heapify(Q)
	S[ch][cw]=0

	#print(Q)

	while Q:
		#print(Q)
		d,x,y=heapq.heappop(Q)

		if S[x][y]<d:
			continue

		for xx,yy in [[0,1],[0,-1],[1,0],[-1,0]]:
			if S[x+xx][y+yy]==".":
				S[x+xx][y+yy]=d
				heapq.heappush(Q,[d,x+xx,y+yy])
			elif S[x+xx][y+yy]=="#":
				continue
			elif S[x+xx][y+yy]>d:
				S[x+xx][y+yy]=d
				heapq.heappush(Q,[d,x+xx,y+yy])

		for xxx in range(-2,3):
			for yyy in range(-2,3):
					if S[x+xxx][y+yyy]==".":
						S[x+xxx][y+yyy]=d+1
						heapq.heappush(Q,[d+1,x+xxx,y+yyy])


	#print(S[2:-2])

	print(-1 if S[dh][dw]=="." else S[dh][dw])


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [list(input()) for i in range(H)]
 
res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
count = 0
 
que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0
 
while (que or que_warp):
    while (que):
        if count > 0:
            que_warp.append(que[0])
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    que_warp.append((nx,ny))
        que.pop(0)
 
    count += 1
 
    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
        que_warp.pop(0)
 
print (res_S[Dh-1][Dw-1])