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:
#coding: utf-8
from collections import defaultdict, deque
import sys
import numpy as np

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


MAZE = []

for i in range(H):
    MAZE.append(list(input()))

dist = [[float('inf')] * W for _ in range(H)]

que = deque()
que.append((CH, CW, 0))

ret = -1

while len(que):
    h, w, cost = que.popleft()

    if h == DH and w == DW:
        ret = cost
        break

    for dh in reversed(range(-2, 3)):
        for dw in reversed(range(-2, 3)):
            if dh == 0 and dw == 0:
                continue
            nh = h + dh 
            nw = w + dw 
            if not (0 <= nh < H and 0 <= nw < W and MAZE[nh][nw] != '#'):
                continue

            if abs(dh) == 2 or abs(dw) == 2 or (abs(dh) == 1 and abs(dw) ==1):
                if dist[nh][nw] > cost + 1:
                    dist[nh][nw] = cost + 1
                    que.append((nh, nw, cost + 1))
            else:
                if dist[nh][nw] > cost:
                    dist[nh][nw] = cost
                    que.appendleft((nh, nw, cost))

#for i in range(H):
#    print (MAZE[i])
print(ret)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [0 for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        # print(M[h])
    ans = 0
    q = set([(Ch, Cw)])
    M[Ch][Cw] = '#'
    dhdw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while True:
        newq = set()
        while q:
            q_ = set()
            for h, w in q:
                # print('({}, {}) = {}'.format(h, w, ans))
                if h == Dh and w == Dw:
                    print(ans)
                    return True
                newq.add((h, w))
                for dh, dw in dhdw:
                    if 0 <= h+dh < H and 0 <= w+dw < W:
                        if M[h+dh][w+dw] == '#':
                            continue
                        q_.add((h+dh, w+dw))
                        M[h+dh][w+dw] = '#'
            q = q_

        if newq:
            for h, w in newq:
                lh = - min(2, h)
                hh = min(3, H - h) 
                for dh in range(lh, hh):
                    lw = - min(2, w)
                    hw = min(3, W - w)
                    for dw in range(lw, hw):
                        if M[h+dh][w+dw] == '.':
                            q.add((h+dh, w+dw))
                            M[h+dh][w+dw] = '#'
        # for h in range(H):
        #     print(M[h])
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
import numpy as np
from collections import deque
H,W = map(int, input().rstrip().split())
CH,CW = map(int, input().rstrip().split())
DH,DW = map(int, input().rstrip().split())
[CH,CW,DH,DW] = [CH-1,CW-1,DH-1,DW-1]
S = np.array([list(input().rstrip()) for i in range(H)])
M = H * W
Distance = np.ones((H,W))*M
Distance[CH,CW] = 0
[nowH,nowW] = [CH,CW]
q = deque([])
q.append([nowH,nowW])
for n in range(0,M):
  if len(q) != 0:
    [nowH,nowW] = q.popleft()
  else:
    break
  if [nowH,nowW] == [DH,DW]:
    break
  for i in range(-2,3):
    for j in range(-2,3):
      if nowH+i >= 0 and nowW+j >= 0 and nowH+i < H and nowW+j < W:
        dis = (abs(i) + abs(j))
        if dis >= 1:
          cost = min(2,dis) - 1
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              if dis == 1:
                q.appendleft([nowH+i,nowW+j])
              else:
                q.append([nowH+i,nowW+j])
              Distance[nowH+i,nowW+j] = Distance[nowH,nowW] + cost
            elif [nowH+i,nowW+j] in q and Distance[nowH,nowW] + cost < Distance[nowH+i,nowW+j]:
              q.remove([nowH+i,nowW+j])
              if dis == 1:
                q.appendleft([nowH+i,nowW+j])
              else:
                q.append([nowH+i,nowW+j])
              Distance[nowH+i,nowW+j] = Distance[nowH,nowW] + cost
              if [nowH+i,nowW+j] == [DH,DW]:
                break
if Distance[DH,DW] == M:
  print(-1)
else:
  print(int(Distance[DH,DW]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    from sys import stdin
    readline = stdin.readline

    from builtins import max, min, range

    INF = float('inf')

    H, W = map(int, readline().split())
    Ch, Cw = map(lambda x: int(x) - 1, readline().split())
    Dh, Dw = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    a = 0
    while q:
        warpq = []
        while q:
            h, w = q.popleft()
            warpq.append((h, w))
            if h - 1 >= 0 and t[h - 1][w] > a:
                q.append((h - 1, w))
                t[h - 1][w] = a
            if h + 1 < H and t[h + 1][w] > a:
                q.append((h + 1, w))
                t[h + 1][w] = a
            if w - 1 >= 0 and t[h][w - 1] > a:
                q.append((h, w - 1))
                t[h][w - 1] = a
            if w + 1 < W and t[h][w + 1] > a:
                q.append((h, w + 1))
                t[h][w + 1] = a

        if t[Dh][Dw] != INF:
            break

        a += 1
        for h, w in warpq:
            for i in range(max(0, h - 2), min(H, h + 3)):
                ti = t[i]
                for j in range(max(0, w - 2), min(W, w + 3)):
                    if ti[j] <= a:
                        continue
                    ti[j] = a
                    q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# ---------標準入力時--------------
h,w=map(int,readline().split())
ch, cw=map(int,readline().split())
dh, dw=map(int,readline().split())
m=list(map(lambda x: list(x.decode()), readlines()))
# ---------標準入力時--------------

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

ad = [(-1,0), (0,-1), (1,0), (0,1)]
warp = [(-2, -2),(-2, -1),(-2, 0),(-2, 1),(-2, 2),
 (-1, -2),(-1, -1),(-1, 1),(-1, 2),
 (0, -2),(0, 2),
 (1, -2),(1, -1),(1, 1),(1, 2),
 (2, -2),(2, -1),(2, 0),(2, 1),(2, 2)]

def bfs2():
    '''
    bfs1の移動の順番を変えただけ
    '''
    que=[]
    m[ch][cw]=str(0)
    que.append((ch,cw))
    
    while que!=[]:
        i, j=que.pop(0)

        # 隣接したマスへの移動
        for si, sj in ad:
            f=False
            #if valid(i+si, j+sj) and m[i+si][j+sj]!='#':
            if 0<=i+si<h and 0<=j+sj<w and m[i+si][j+sj]!='#': 
                if m[i+si][j+sj]=='.':
                    m[i+si][j+sj]=m[i][j]
                    f=True
                else:
                    if int(m[i+si][j+sj])>int(m[i][j]):
                        m[i+si][j+sj]=m[i][j]
                        f=True
            if f:
                que.append((i+si, j+sj))

        for si, sj in warp:
            f=False
            #if valid(i+si, j+sj) and m[i+si][j+sj]!='#':
            if 0<=i+si<h and 0<=j+sj<w and m[i+si][j+sj]!='#':
                if m[i+si][j+sj]=='.':
                    m[i+si][j+sj]=str(int(m[i][j])+1)
                    f=True
                else:
                    if int(m[i+si][j+sj])>int(m[i][j])+1:
                        m[i+si][j+sj]=str(int(m[i][j])+1)
                        f=True
            if f:
                que.append((i+si, j+sj))
###---------------------------------------

bfs2()

if m[dh][dw] == '.':
    print(-1)
else:
    print(m[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [0 for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        # print(M[h])
    ans = 0
    q = set([(Dh, Dw)])
    dhdw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    M[Dh][Dw] = '#'
    while True:
        newq = set()
        while q:
            q_ = set()
            for h, w in q:
                # print('({}, {}) = {}'.format(h, w, ans))
                if h == Ch and w == Cw:
                    print(ans)
                    return True
                newq.add((h, w))
                for dh, dw in dhdw:
                    if 0 <= h+dh < H and 0 <= w+dw < W:
                        if M[h+dh][w+dw] == '#':
                            continue
                        q_.add((h+dh, w+dw))
                        M[h+dh][w+dw] = '#'
            q = q_

        if newq:
            for h, w in newq:
                lh = - min(2, h)
                hh = min(3, H - h) 
                for dh in range(lh, hh):
                    lw = - min(2, w)
                    hw = min(3, W - w)
                    for dw in range(lw, hw):
                        if M[h+dh][w+dw] == '.':
                            q.add((h+dh, w+dw))
                            M[h+dh][w+dw] = '#'
        # for h in range(H):
        #     print(M[h])
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

if __name__ == '__main__':
    main()

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)] #マップ
vi=[ [-1 for _ in range(w)] for _ in range(h)]#visit
st=deque()
st2=deque()
st.append([ch-1,cw-1])
vi[ch-1][cw-1]=1
c=0

d=[[0,1],[-1,0],[1,0],[0,-1]]
d2=[[-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]]

while st or st2:
  while st:
    s2=0
    h1,w1=st.popleft()
    if dh-1==h1 and dw-1 ==w1:
      print(c)
      exit()
    for m in d:
      x=w1+m[1]
      y=h1+m[0]
      if 0<=y<h and 0<=x<w:
        if s[y][x]=="." and vi[y][x]==-1:
          st.append([y,x])
        elif s[y][x]=="#":s2=1
        vi[y][x]=1
    if s2==1: st2.append([h1,w1])

  while st2:
    h1,w1=st2.popleft()
    for m in d2:
      x=w1+m[1]
      y=h1+m[0]
      if 0<=y<h and 0<=x<w and vi[y][x]==-1 and s[y][x]==".":
        vi[y][x]=1
        st.append([y,x])
  c+=1
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    from sys import stdin
    readline = stdin.readline

    from builtins import max, min, range

    INF = float('inf')

    H, W = map(int, readline().split())
    Ch, Cw = map(lambda x: int(x) - 1, readline().split())
    Dh, Dw = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    while q:
        warpq = []
        while q:
            h, w = q.popleft()
            a = t[h][w]
            warpq.append((h, w))
            if h - 1 >= 0 and t[h - 1][w] > a:
                q.append((h - 1, w))
                t[h - 1][w] = a
            if h + 1 < H and t[h + 1][w] > a:
                q.append((h + 1, w))
                t[h + 1][w] = a
            if w - 1 >= 0 and t[h][w - 1] > a:
                q.append((h, w - 1))
                t[h][w - 1] = a
            if w + 1 < W and t[h][w + 1] > a:
                q.append((h, w + 1))
                t[h][w + 1] = a

        if t[Dh][Dw] != INF:
            break

        for h, w in warpq:
            for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
                ti = t[i]
                for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                    if ti[j] <= a + 1:
                        continue
                    ti[j] = a + 1
                    q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
def solve():
    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)]
    area_num = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                bfs(h,w,H,W,S,area_num)
                area_num += 1
    
    start_area_num = int(S[Ch][Cw])
    goal_area_num = int(S[Dh][Dw])

    G = defaultdict(set)

    for h in range(H):
        for w in range(W):
            from_area_num = S[h][w]
            if from_area_num == '#':
                continue
            from_area_num = int(from_area_num)

            for dh in range(-2,2+1):
                if h+dh < 0 or h+dh >= H:
                    continue
                for dw in range(-2, 2+1):
                    if w+dw < 0 or w+dw >= W:
                        continue
                    to_area_num = S[h+dh][w+dw]
                    if to_area_num == '#':
                        continue
                    to_area_num = int(to_area_num)
                    if from_area_num != to_area_num:
                        G[to_area_num].add(from_area_num)
                        G[from_area_num].add(to_area_num)
    
    area_num_count = area_num + 1
    visited = [False] * area_num_count
    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        visited[cur_area_num] = True
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                q.append((next_area_num,warp_cnt+1))
    else:
        print(-1)

def bfs(h,w,H,W,S,area_num):
    q = deque()
    d = ((0,1),(0,-1),(1,0),(-1,0))
    q.append((h,w))
    S[h][w] = area_num
    while len(q) > 0:
        now_h, now_w = q.popleft()

        for dh, dw in d:
            if 0 <= now_h + dh < H and 0 <= now_w + dw < W and S[now_h+dh][now_w+dw] == '.':
                q.append((now_h+dh, now_w+dw))
                S[now_h+dh][now_w+dw] = area_num


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    #ダイクストラ法
    import heapq
    def dijkstra_heap(st):
        infi=10**18
        #始点sから各頂点への最短距離
        d = [infi] * h*w
        d[st] = 0
        edgelist = [(0,st)]
        while edgelist:
            dist,idx = heapq.heappop(edgelist)
            x=idx//w
            y=idx%w
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=x+dx
                    ny=y+dy
                    if not (0<=nx<h and 0<=ny<w):
                        continue
                    if dx==0 and dy==0:
                        continue
                    if s[nx][ny]=="#":
                        continue
                    idx1=nx*w+ny
                    if abs(dx)+abs(dy)==1:
                        if d[idx1]>dist:
                            d[idx1]=d[idx]
                            heapq.heappush(edgelist,(d[idx1],idx1))
                    else:
                        if d[idx1]>dist+1:
                            d[idx1]=dist+1
                            heapq.heappush(edgelist,(d[idx1],idx1))
        return d


    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() for _ in range(h)]
    st=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(st)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [0 for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        # print(M[h])
    ans = 0
    q = set([(Dh, Dw)])
    dhdw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while True:
        newq = set()
        while q:
            q_ = set()
            for h, w in q:
                # print('({}, {}) = {}'.format(h, w, ans))
                if h == Ch and w == Cw:
                    print(ans)
                    return True
                M[h][w] = '#'
                newq.add((h, w))
                for dh, dw in dhdw:
                    if 0 <= h+dh < H and 0 <= w+dw < W:
                        if M[h+dh][w+dw] == '#':
                            continue
                        q_.add((h+dh, w+dw))
                        M[h+dh][w+dw] = '#'
            q = q_

        if newq:
            for h, w in newq:
                lh = - min(2, h)
                hh = min(3, H - h) 
                for dh in range(lh, hh):
                    lw = - min(2, w)
                    hw = min(3, W - w)
                    for dw in range(lw, hw):
                        if M[h+dh][w+dw] == '.':
                            q.add((h+dh, w+dw))
        # for h in range(H):
        #     print(M[h])
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
from collections import defaultdict, deque
import sys
import numpy as np

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


MAZE = []

for i in range(H):
    MAZE.append(list(input()))

can_walk = ((1, 0), (0, 1), (-1, 0), (0, -1))

dist = [[float('inf')] * W for _ in range(H)]

que = deque()
que.append((CH, CW, 0))

ret = -1

while len(que):
    h, w, cost = que.popleft()

    if h == DH and w == DW:
        ret = cost
        break

    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if dh == 0 and dw == 0:
                continue
            nh = h + dh 
            nw = w + dw 
            if not (0 <= nh < H and 0 <= nw < W and MAZE[nh][nw] != '#'):
                continue

            if abs(dh) == 2 or abs(dw) == 2 or (abs(dh) == 1 and abs(dw) ==1):
                if dist[nh][nw] > cost + 1:
                    dist[nh][nw] = cost + 1
                    que.append((nh, nw, cost + 1))
            else:
                if dist[nh][nw] > cost:
                    dist[nh][nw] = cost
                    que.appendleft((nh, nw, cost))

#for i in range(H):
#    print (MAZE[i])
print(ret)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
INF=float("inf")

H,W=map(int,readline().split())
Ch,Cw=map(int,readline().split())
Dh,Dw=map(int,readline().split())
Ch-=1
Cw-=1
Dh-=1
Dw-=1
maze=list(map(str,read().rstrip().decode().split()))

path=[[INF]*W for _ in range(H)]
walk=[(1,0),(0,-1),(-1,0),(0,1)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if not (i, j) in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s)) 
    for dx, dy in warp: 
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1)) 
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

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):
    for x in range(w):
        if s[y][x]=='.':
            s[y][x]=10000000


s[c[0]-1][c[1]-1]=0
que=deque([[c[0]-1,c[1]-1]])
temp=[(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)]
while que:
    y,x=que.popleft()
    for i,j in temp:
        if 0<=y+i<h and 0<=x+j<w and s[y+i][x+j]!="#":
            nexty,nextx=y+i,x+j
            dist=s[nexty][nextx]
            if i*i+j*j==1 and 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:
def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [0 for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        # print(M[h])
    ans = 0
    q = set([(Dh, Dw)])
    dhdw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while True:
        newq = set()
        while q:
            q_ = set()
            for h, w in q:
                # print('({}, {}) = {}'.format(h, w, ans))
                if h == Ch and w == Cw:
                    print(ans)
                    return True
                M[h][w] = '#'
                newq.add((h, w))
                for dh, dw in dhdw:
                    if 0 <= h+dh < H and 0 <= w+dw < W:
                        if M[h+dh][w+dw] == '#':
                            continue
                        q_.add((h+dh, w+dw))
                        M[h+dh][w+dw] = '#'
            q = q_

        if newq:
            for h, w in newq:
                for dh in range(-2, 3):
                    if not (0 <= h+dh < H):
                        continue
                    for dw in range(-2, 3):
                        if 0 <= w+dw < W:
                            if M[h+dh][w+dw] == '.':
                                q.add((h+dh, w+dw))
        # for h in range(H):
        #     print(M[h])
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    from sys import stdin
    readline = stdin.readline

    INF = float('inf')

    H, W = map(int, readline().split())
    Ch, Cw = map(lambda x: int(x) - 1, readline().split())
    Dh, Dw = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    while q:
        warpq = []
        while q:
            h, w = q.popleft()
            a = t[h][w]
            warpq.append((h, w))
            if h - 1 >= 0 and t[h - 1][w] > a:
                q.append((h - 1, w))
                t[h - 1][w] = a
            if h + 1 < H and t[h + 1][w] > a:
                q.append((h + 1, w))
                t[h + 1][w] = a
            if w - 1 >= 0 and t[h][w - 1] > a:
                q.append((h, w - 1))
                t[h][w - 1] = a
            if w + 1 < W and t[h][w + 1] > a:
                q.append((h, w + 1))
                t[h][w + 1] = a

        if t[Dh][Dw] != INF:
            break

        for h, w in warpq:
            for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
                ti = t[i]
                for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                    if ti[j] <= a + 1:
                        continue
                    ti[j] = a + 1
                    q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
from collections import defaultdict, deque
import sys
import numpy as np

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


MAZE = []

for i in range(H):
    MAZE.append(list(input()))

can_walk = ((1, 0), (0, 1), (-1, 0), (0, -1))

dist = [[float('inf')] * W for _ in range(H)]

que = deque()
que.append((CH, CW, 0))

ret = -1

while len(que):
    h, w, cost = que.popleft()

    if dist[h][w] <= cost:
        continue

    dist[h][w] = cost

    if h == DH and w == DW:
        ret = cost
        break

    for dh, dw in can_walk:
        nh = h + dh 
        nw = w + dw 
        if 0 <= nh < H and 0 <= nw < W and MAZE[nh][nw] != '#':
            que.appendleft((nh, nw, cost))

    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if dh == 0 and dw == 0:
                continue

            nh = h + dh 
            nw = w + dw 
            if not (0 <= nh < H and 0 <= nw < W and MAZE[nh][nw] != '#'):
                continue
            if abs(dh) == 2 or abs(dw) == 2 or (abs(dh) == 1 and abs(dw) ==1):
                que.append((nh, nw, cost + 1))
            else:
                que.appendleft((nh, nw, cost))

#for i in range(H):
#    print (MAZE[i])
print(ret)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
import numpy as np
from collections import deque
H,W = map(int, input().rstrip().split())
CH,CW = map(int, input().rstrip().split())
DH,DW = map(int, input().rstrip().split())
[CH,CW,DH,DW] = [CH-1,CW-1,DH-1,DW-1]
S = np.array([list(input().rstrip()) for i in range(H)])
M = 10 ** 9
Distance = np.ones((H,W))*M
Distance[CH,CW] = 0
[nowH,nowW] = [CH,CW]
q0 = deque([])
q0.append([nowH,nowW])
q1 = deque([])
for n in range(0,M):
  if len(q0) != 0:
    [nowH,nowW] = q0.popleft()
  elif len(q1) != 0:
    [nowH,nowW] = q1.popleft()
  else:
    break
  if [nowH,nowW] == [DH,DW]:
    break
  for i in range(-2,3):
    for j in range(-2,3):
      if nowH+i >= 0 and nowW+j >= 0 and nowH+i < H and nowW+j < W:
        if (abs(i) + abs(j)) == 1:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              q0.append([nowH+i,nowW+j])
            elif [nowH+i,nowW+j] in q1:
              q0.append([nowH+i,nowW+j])
              q1.remove([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW],Distance[nowH+i,nowW+j])
        elif (abs(i) + abs(j)) >= 2:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              q1.append([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW]+1,Distance[nowH+i,nowW+j])       
if Distance[DH,DW] == M:
  print(-1)
else:
  print(int(Distance[DH,DW]))