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,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1,ls=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################
# Verified by
# https://atcoder.jp/contests/arc033/submissions/me
# https://atcoder.jp/contests/abc174/tasks/abc174_f
#
# speed up TIPS: delete update of el. non-use of getitem, setitem.
#
# Binary Indexed Tree
# Bit.add(i,x)    : add x at i-th value
# Bit.sum(i)      : get sum up to i-th value
# Bit.l_bound(w)  : get bound of index where x1+x2+...+xi<w

class Bit: # 1-indexed
    def __init__(self,n,init=None):
        self.size=n
        self.m=len(bin(self.size))-2
        self.arr=[0]*(2**self.m+1)
        self.el=[0]*(2**self.m+1)
        if init!=None:
            for i in range(len(init)):
                self.add(i,init[i])
                self.el[i]=init[i]

    def __str__(self):
        a=[self.sum(i+1)-self.sum(i) for i in range(self.size)]
        return str(a)
        
    def add(self,i,x):
        if not 0<i<=self.size:return NotImplemented
        self.el[i]+=x
        while i<=self.size:
            self.arr[i]+=x
            i+=i&(-i)
        return
    
    def sum(self,i):
        if not 0<=i<=self.size:return NotImplemented
        rt=0
        while i>0:
            rt+=self.arr[i]
            i-=i&(-i)
        return rt
    
    def __getitem__(self,key):
        return self.el[key]
        return self.sum(key+1)-self.sum(key)

    def __setitem__(self,key,value):
        self.add(key,value-self.sum(key+1)+self.sum(key))

    def l_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<=self.size and self.arr[x+k]<w:
                w-=self.arr[x+k]
                x+=k
            k>>=1
        return x+1
        
    def u_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<=self.size and self.arr[x+k]<=w:
                w-=self.arr[x+k]
                x+=k
            k>>=1
        return x+1
        
class Bit0(Bit): # 0-indexed
    def add(self,j,x):
        super().add(j+1,x)
    def l_bound(self,w):
        return max(super().l_bound(w)-1,0)
    def u_bound(self,w):
        return max(super().u_bound(w)-1,0)

class Multiset(Bit0):
    def __init__(self,max_v):
        super().__init__(max_v)
    def insert(self,x):
        super().add(x,1)
    def find(self,x):
        return super().l_bound(super().sum(x))
    def __str__(self):
        return str(self.arr)

def compress(L):
    dc={v:i for i,v in enumerate(sorted(set(L)))}
    return [dc[i] for i in L]


show_flg=False
show_flg=True

ans=0

h,w=LI()
sh,sw=LI()
gh,gw=LI()

w+=2
m=[1]*w
for i in range(h):
    s=input()
    m+=[1]+[i=='#'for i in s]+[1]
m+=[1]*w
h+=2
n=h*w
v=[-1]*w*h

dc=dict()
cn=0
def bfs(x):
    global cn
    q=[x]
    v[x]=x
    dc[x]=cn
    cn+=1
    while q:
        c=q.pop()
        for nx in [c+1,c-1,c+w,c-w]:
            if 0<=nx<n and m[nx]!=1 and v[nx]==-1:
                q+=nx,
                v[nx]=x
    return        
            
for i in range(n):
    if m[i]!=1 and v[i]==-1:
        bfs(i)

g=[set()for i in range(cn)]
nbw=[-2*w+1,-2*w+2,-w+1,-w+2,2,2*w+1,2*w+2,w+1,w+2,+2*w,-2*w,-2*w-1,-2*w-2,-w-1,-w-2,-2,2*w-1,2*w-2,w-1,w-2]
nb=[1,-1,w,-w]
d=[-1]*n
v=[0]*n
vw=[0]*n
q=deque([(sh*w+sw,0)])
v[sh*w+sw]=1
vw[sh*w+sw]=1
while q:
    i,dist=q.pop()
    if d[i]==-1:
        d[i]=dist
    else:
        d[i]=min(dist,d[i])
    if m[i]==1:
        continue
    for di in nb:
        nx=i+di
        if 0<=nx<n and m[nx]!=1 and d[nx]==-1:
            q.append((nx,d[i]))

    for di in nbw:
        nx=i+di
        if 0<=nx<n and m[nx]!=1 and d[nx]==-1:
            q.appendleft((nx,d[i]+1))
print(d[gh*w+gw])

Submission status: Time Limit Exceeded

Solution code:
# from: https://atcoder.jp/contests/abc176/submissions/16207543
from collections import deque
from numba import njit, b1, i4, i8, f8
import numpy as np
import sys

read = sys.stdin.read
readline = sys.stdin.readline

@njit((i8,i8,i8,i8,i8,i8,b1[:, :]), cache=True)
def solve(H,W,C_h,C_w,D_h,D_w,S):
  INF = int(1e7)
  dist = [[INF]*(W) for _ in range(H)]
  dist[C_h][C_w] = 0
  isinque = [[False]*(W) for _ in range(H)]
  que1 = [(C_h,C_w)]
  que2 = []
  i,j = 0,0

  move_a = [(1,0),(0,1),(-1,0),(0,-1)]
  move_b = [(-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 True:
    if i==len(que1) and j==len(que2):
      break;
    while i<len(que1):
      h,w = que1[i]
      i += 1
      isinque[h][w] = False
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          if isinque[nh][nw]==False:
            que1.append((nh,nw))
            isinque[nh][nw] = True
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          if isinque[nh][nw]==False:
            que2.append((nh,nw))
            isinque[nh][nw] = True
    while j<len(que2):
      h,w = que2[j]
      j += 1
      isinque[h][w] = False
      is_edge = False #here
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if not S[nh][nw]: is_edge = True #here
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          if isinque[nh][nw]==False:
            que1.append((nh,nw))
            isinque[nh][nw] = True
      if is_edge: #here
        for dh,dw in move_b:
          nh,nw = h+dh,w+dw
          if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]+1:
            dist[nh][nw] = dist[h][w]+1
            if isinque[nh][nw]==False:
              que2.append((nh,nw))
              isinque[nh][nw] = True
  print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

H,W = map(int,readline().split())
C_h,C_w = map(lambda x:int(x)-1,readline().split())
D_h,D_w = map(lambda x:int(x)-1,readline().split())
S = np.array([[c=='.' for c in readline()] for _ in range(H)])
solve(H,W,C_h,C_w,D_h,D_w,S)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]

seen = [[None] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw])

while q:
    th, tw = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1:
            continue
        if S[nh][nw] == '#':
            continue
        if seen[nh][nw] is not None and seen[nh][nw] <= seen[th][tw]:
            continue
        seen[nh][nw] = seen[th][tw]
        q.append([nh, nw])
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            if dh2 == 0 and dw2 == 0:
                continue
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1:
                continue
            if S[nh][nw] == '#':
                continue
            if seen[nh][nw] is not None and seen[nh][nw] <= seen[th][tw] + 1:
                continue
            seen[nh][nw] = seen[th][tw] + 1
            q.append([nh, nw])

if seen[Dh][Dw] is not None:
    print(seen[Dh][Dw])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]

seen = [[None] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw])

while q:
    th, tw = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1:
            continue
        if S[nh][nw] == '#':
            continue
        if seen[nh][nw] is not None and seen[nh][nw] <= seen[th][tw]:
            continue
        seen[nh][nw] = seen[th][tw]
        q.append([nh, nw])
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1:
                continue
            if S[nh][nw] == '#':
                continue
            if seen[nh][nw] is not None and seen[nh][nw] <= seen[th][tw]:
                continue
            seen[nh][nw] = seen[th][tw] + 1
            q.append([nh, nw])

if seen[Dh][Dw] is not None:
    print(seen[Dh][Dw])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
######### D 
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())
meiro = []
for i in range(H):
    meiro.append(list(map(str, input())))
    
walk = [(0,1),(1,0),(0,-1),(-1,0)]
warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)]+walk]

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


while q != deque():
#for _ in range(10):
    ph, pw = q.popleft()
    
    if meiro[ph][pw] != num:
        num += 1
    
    for h, w in walk:
        th = ph+h
        tw = pw+w
        
        if 0 <= th < H and 0 <= tw < W and meiro[th][tw] != '#' and meiro[th][tw] != meiro[ph][pw]:
            meiro[th][tw] = meiro[ph][pw]
            q.appendleft((th,tw))
    
    for h, w in warp:
        th = ph+h
        tw = pw+w
        
        if 0 <= th < H and 0 <= tw < W and meiro[th][tw] == '.':
            meiro[th][tw] = meiro[ph][pw] + 1
            q.append((th,tw))
    
if meiro[Dh][Dw] == '.':
    print(-1)
else:
    print(meiro[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

INF = float("INF")
cnt = [[INF]*W for _ in range(H)]

q = deque()
q.append([sy, sx])
cnt[sy][sx] = 0
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]

while q:
    y, x = q.popleft()
    for dy, dx in move:
        ny = y + dy
        nx = x + dx
        if ny < 0 or ny > H-1 or nx < 0 or nx > W-1:
            continue
        if maze[ny][nx] == "." and cnt[ny][nx] > cnt[y][x]:
            cnt[ny][nx] = cnt[y][x]
            q.appendleft([ny, nx])
    for i in range(-2, 2+1):
        for j in range(-2, 2+1):
            wy = y + i
            wx = x + j
            if wy < 0 or wy > H-1 or wx < 0 or wx > W-1:
                continue
            if maze[wy][wx] == "." and cnt[wy][wx] > cnt[y][x] + 1:
                cnt[wy][wx] = cnt[y][x] + 1
                q.append([wy, wx])

ans = cnt[gy][gx] if cnt[gy][gx] != INF else -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 参考: https://marco-note.net/abc-176-work-log/
from collections import deque

H, W                = map(int, input().split())
start_h, start_w    = map(int, input().split())
goal_h, goal_w      = map(int, input().split())
S                   = [input() for i in range(H)]

INF = 10 ** 12
cost = [[INF] * W for i in range(H)]

# 衝突判定
def wall_check(y, x):
    if(0 <= y < H and 0 <= x < W and S[y][x] == '.'):
        return True
    else:
        return False

# 上下左右
move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# ワープ魔法
# (-2, -2) ~ (2, 2) ※(0, 0)とmoveは除く
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + move]

dq = deque()
cost[start_h - 1][start_w - 1] = 0          # スタート地点のコストは0
dq.append((start_h - 1, start_w - 1, 0))    # (行, 列, コスト)

while dq:
    h, w, c = dq.popleft()  # 先頭を取り出し，削除
    # 歩いて移動
    for dy, dx in move:
        y, x = h + dy, w + dx
        # 歩いて行ける & コストが更新される場合
        if wall_check(y, x) and cost[y][x] > c:
            cost[y][x] = c
            # 先頭（左側）に要素を追加
            dq.appendleft((y, x, c))    
    # ワープ
    for dy, dx in warp:
        y, x = h + dy, w + dx
        # ワープで行ける & コストが更新される場合
        if wall_check(y, x) and cost[y][x] > c + 1:
            cost[y][x] = c + 1
            dq.appendleft((y, x, c + 1))

if(cost[goal_h - 1][goal_w - 1] != INF):
    print(cost[goal_h - 1][goal_w - 1])
else:
    print('-1')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

INF = float("INF")
cnt = [[INF]*W for _ in range(H)]

q = deque()
q.append([sy, sx])
cnt[sy][sx] = 0
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]

while q:
    y, x = q.popleft()
    for dy, dx in move:
        ny = y + dy
        nx = x + dx
        if ny < 0 or ny > H-1 or nx < 0 or nx > W-1:
            continue
        if maze[ny][nx] == "." and cnt[ny][nx] > cnt[y][x]:
            cnt[ny][nx] = cnt[y][x]
            q.appendleft([ny, nx])
        for i in range(-2, 2+1):
            for j in range(-2, 2+1):
                wy = y + i
                wx = x + j
                if wy < 0 or wy > H-1 or wx < 0 or wx > W-1:
                    continue
                if maze[wy][wx] == "." and cnt[wy][wx] > cnt[y][x]:
                    cnt[wy][wx] = cnt[y][x] + 1
                    q.append([wy, wx])

ans = -1 if cnt[gy][gx] == INF else cnt[gy][gx]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import product


def bfs(S):
    x, y = S
    dist = [[10 ** 9] * w for _ in range(h)]
    dist[y][x] = 0
    que = deque([S])

    while len(que) > 0:
        x, y = que.popleft()
        near_a = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        num = product([-2, -1, 0, 1, 2], repeat=2)
        near_b = [(x + dx, y + dy) for dx, dy in num]

        for i, j in near_a:
            if (0 <= i < w and 0 <= j < h and
                    dist[j][i] > dist[y][x] and s[j][i] == '.'):
                dist[j][i] = dist[y][x]
                que.append((i, j))
        for i, j in near_b:
            if (0 <= i < w and 0 <= j < h and
                    dist[j][i] > dist[y][x] + 1 and s[j][i] == '.'):
                dist[j][i] = dist[y][x] + 1
                que.append((i, j))
    return dist


h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [input() for _ in range(h)]

ans = bfs((Cw - 1, Ch - 1))[Dh - 1][Dw - 1]
print(-1 if ans == 10 ** 9 else ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int,input().split())
start = tuple(map(int, input().split()))
goal = tuple(map(int, input().split()))
visited = {(i, j): False for i in range(1, h + 1) for j in range(1, w + 1)}
maze = {}
for i in range(h):
    row = input()
    for j in range(len(row)):
        maze[(i+1, j+1)] = row[j]

def check_bound(coordinate):
    if (1 <= coordinate[0] & coordinate[0] <= h) & (1<= coordinate[1] & coordinate[1] <= w):
        return True
    else:
        return False




def add(cor1, cor2):
    return (cor1[0] + cor2[0], cor1[1] + cor2[1])


def walk(start):
    visited[start] = True
    for dir in [(1,0), (-1, 0), (0, 1), (0, -1)]:
        cor = add(start, dir)
        if check_bound(cor):
            if (not visited[cor]) & (maze[cor] == '.'):
                walk(cor)


def warp(start):
    for jump in [(i, j) for i in range(-2, 3) for j in range(-2, 3)]:
        cor = add(start, jump)
        if check_bound(cor):
            if (not visited[cor]) & (maze[cor] == '.'):
                walk(cor)

walk(start)
warp_count = 0
while (not visited[goal]) & (warp_count < h * w):
    prev_visited = visited.copy()
    for cor in prev_visited.keys():
        if prev_visited[cor]:
            warp(cor)
    
    warp_count += 1
    

if visited[goal]:
    print(warp_count)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from queue import deque

def main():
  h, w = map(int, input().strip().split())
  c_h, c_w = map(int, input().strip().split())
  d_h, d_w = map(int, input().strip().split())
  maze = [list(input().strip()) for _ in range(h)]
  visited = [[0] * w for _ in range(h)]
  
  def bfs():
    dq = deque([(c_h-1, c_w-1, 0)])
    while dq:
      (ih, iw, cnt) = dq.pop()
      if visited[ih][iw]:
        continue
      visited[ih][iw] = 1
      
      if ih == d_h-1 and iw == d_w-1:
        return cnt
      
      for dh in range(-2, 3):
        for dw in range(-2, 3):
          if not (0 <= ih + dh < h and 0 <= iw + dw < w) \
             or visited[ih + dh][iw + dw] == 1 \
             or maze[ih + dh][iw + dw] == '#':
            continue
          if (dh, dw) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            dq.append((ih + dh, iw + dw, cnt))
          else:
            dq.appendleft((ih + dh, iw + dw, cnt+1))
      
    return -1
  print(bfs())
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

D = [(-1, 0), (0, -1), (1, 0), (0, 1)]
dist = [[float("inf")] * w for _ in range(h)]
dist[sx - 1][sy - 1] = 0
q = deque()
q.append((sx - 1, sy - 1))
while q:
    X, Y = q.popleft()
    d = dist[X][Y]
    for dx, dy in D:
        nx, ny = X + dx, Y + dy
        if nx < 0 or ny < 0 or nx >= h or ny >= w:
            continue
        if M[nx][ny] == "#":
            continue
        if dist[nx][ny] <= d:
            continue
        dist[nx][ny] = d
        q.appendleft((nx, ny))
    for c in range(-2, 3):
        for r in range(-2, 3):
            nx, ny = X + c, Y + r
            if nx < 0 or ny < 0 or nx >= h or ny >= w:
                continue
            if M[nx][ny] == "#":
                continue
            if dist[nx][ny] <= d + 1:
                continue
            dist[nx][ny] = d + 1
            q.append((nx, ny))

ans = dist[gx - 1][gy - 1]
if ans == float("inf"):
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from numba import njit, b1, i4, i8, f8
import numpy as np
import sys

read = sys.stdin.read
readline = sys.stdin.readline

@njit((i8,i8,i8,i8,i8,i8,b1[:, :]), cache=True)
def solve(H,W,C_h,C_w,D_h,D_w,S):
  INF = int(1e7)
  dist = [[INF]*(W) for _ in range(H)]
  dist[C_h][C_w] = 0
  isinque = [[False]*(W) for _ in range(H)]
  que1 = [(C_h,C_w)]
  que2 = []
  i,j = 0,0

  move_a = [(1,0),(0,1),(-1,0),(0,-1)]
  move_b = [(-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 True:
    if i==len(que1) and j==len(que2):
      break;
    while i<len(que1):
      h,w = que1[i]
      i += 1
      isinque[h][w] = False
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          if isinque[nh][nw]==False:
            que1.append((nh,nw))
            isinque[nh][nw] = True
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          if isinque[nh][nw]==False:
            que2.append((nh,nw))
            isinque[nh][nw] = True
    while j<len(que2):
      h,w = que2[j]
      j += 1
      isinque[h][w] = False
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          if isinque[nh][nw]==False:
            que1.append((nh,nw))
            isinque[nh][nw] = True
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          if isinque[nh][nw]==False:
            que2.append((nh,nw))
            isinque[nh][nw] = True
  print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

H,W = map(int,readline().split())
C_h,C_w = map(lambda x:int(x)-1,readline().split())
D_h,D_w = map(lambda x:int(x)-1,readline().split())
S = np.array([[c=='.' for c in readline()] for _ in range(H)])
solve(H,W,C_h,C_w,D_h,D_w,S)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    from collections import deque

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [input() for _ in range(H)]
    max_num = 10**6
    fp = [[max_num] * W for _ in range(H)]

    que = deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                que.appendleft([ny, nx, w_num])
                fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            nw = w_num +1

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
                que.append([ny, nx, nw])
                fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from numba import njit, b1, i4, i8, f8
import numpy as np
import sys

read = sys.stdin.read
readline = sys.stdin.readline

@njit((i8,i8,i8,i8,i8,i8,b1[:, :]), cache=True)
def solve(H,W,C_h,C_w,D_h,D_w,S):
  INF = int(1e7)
  dist = [[0]*(W) for _ in range(H)]
  for i in range(H):
    for j in range(W):
      dist[i][j] = INF
  dist[C_h][C_w] = 0
  seen = [[False]*(W) for _ in range(H)]
  que1 = [(C_h,C_w)]
  que2 = []
  i,j = 0,0

  move_a = [(1,0),(0,1),(-1,0),(0,-1)]
  move_b = [(-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 True:
    if i==len(que1) and j==len(que2):
      break;
    while i<len(que1):
      h,w = que1[i]
      i += 1
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          que1.append((nh,nw))
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          que2.append((nh,nw))
    while j<len(que2):
      h,w = que2[j]
      j += 1
      for dh,dw in move_a:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]:
          dist[nh][nw] = dist[h][w]
          que1.append((nh,nw))
      for dh,dw in move_b:
        nh,nw = h+dh,w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] and dist[nh][nw] > dist[h][w]+1:
          dist[nh][nw] = dist[h][w]+1
          que2.append((nh,nw))
  print(dist[D_h][D_w] if dist[D_h][D_w]<INF else -1)

H,W = map(int,readline().split())
C_h,C_w = map(lambda x:int(x)-1,readline().split())
D_h,D_w = map(lambda x:int(x)-1,readline().split())
S = np.array([[c=='.' for c in readline()] for _ in range(H)])
solve(H,W,C_h,C_w,D_h,D_w,S)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = [int(item) for item in input().split()]
Ch, Cw = [int(item)-1 for item in input().split()]
Dh, Dw = [int(item)-1 for item in input().split()]
grid = [input() for _ in range(H)]
max_num = 10**6
fp = [[max_num for _ in range(W)] for _ in range(H)]

que = deque([[Ch, Cw, 0]])
fp[Ch][Cw] = 0

walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

while que:
    y, x, w_num = que.popleft()

    for dy, dx in walk:
        ny = y + dy
        nx = x + dx

        if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
            que.appendleft([ny, nx, w_num])
            fp[ny][nx] = w_num

    for dy, dx in warp:
        ny = y + dy
        nx = x + dx
        nw = w_num +1

        if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
            que.append([ny, nx, nw])
            fp[ny][nx] = nw

if fp[Dh][Dw] != max_num:
    print(fp[Dh][Dw])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    from collections import deque

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [input() for _ in range(H)]
    max_num = 10**6
    fp = [[max_num for _ in range(W)] for _ in range(H)]

    que = deque([[Ch, Cw, 0]])
    fp[Ch][Cw] = 0

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                que.appendleft([ny, nx, w_num])
                fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            nw = w_num +1

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
                que.append([ny, nx, nw])
                fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

if __name__ == "__main__":
    resolve()