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

    se = set()

    for i,j in zip(dx,dy):
        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 lin[nx][ny] > lin[x][y]:
                se.add((nx,ny))
                lin[nx][ny] = lin[x][y]# 直接行ける
    
    # 魔法の力をもってすれば行ける
    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 lin[nx][ny] > lin[x][y]+1:
                se.add((nx,ny))
                lin[nx][ny] = lin[x][y]+1

    que += se

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

Submission status: Time Limit Exceeded

Solution code:
import sys, math, re
from functools import lru_cache
from collections import deque
sys.setrecursionlimit(500000)
MOD = 10**9+7

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

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    H, W = mi()
    Ch, Cw = mi()
    Dh, Dw = mi()
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    S = [input() for i in range(H)]
    

    d = deque([(Ch, Cw)])
    visited = [[math.inf]*W for i in range(H)]
    visited[Ch][Cw] = 0

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

    while d:
        now_h, now_w = d.pop()
        check[now_h][now_w] = True

        # 行けるとこリスト
        nexts = []
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == j == 0:
                    continue
                if 0 <= now_h+i < H and 0 <= now_w+j < W:
                        nexts.append((now_h+i, now_w+j))


        for next in nexts:
            next_h, next_w = next

            # 壁の場合はskip
            if S[next_h][next_w] == '#':
                continue

            if abs(now_h-next_h)+abs(now_w-next_w) == 1:
                visited[next_h][next_w] = min(visited[next_h][next_w], visited[now_h][now_w])
            else:
                visited[next_h][next_w] = min(visited[next_h][next_w], visited[now_h][now_w]+1)

            if not check[next_h][next_w]:
                d.appendleft(next)

    ans = visited[Dh][Dw]
    if ans != math.inf:
        print(ans)
    else:
        print(-1)
        

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
map = []
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visit = [[-1]*w for i in range(h)]
visit[sy - 1][sx - 1] = 0
warp = []
cnt = 0

for i in range(-2, 3):
    for j in range(-2, 3):
        warp.append([i, j])

for i in range(h):
    s = input()
    map.append(s)

route = deque([[sy - 1, sx - 1]])

while route:
    while route:
        y, x = route.popleft()
        for i, j in move:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] == visit[y][x]:
                        continue
                    visit[k][l] = visit[y][x]
                    route.append([k, l])
    wroute = deque([])
    for i in range(w):
        for j in range(h):
            if visit[j][i] == cnt:
                wroute.append([j, i])
    while wroute:
        y, x = wroute.popleft()
        for i, j in warp:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] != -1:
                        continue
                    visit[k][l] = visit[y][x] + 1
                    route.append([k, l])
    cnt += 1

print(visit[gy - 1][gx - 1])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
class UnionFind:
    def __init__(self, n):
        self.setSize = [1] * n
        self.numSets = n
        self.rank = [0] * n
        self.p = [i for i in range(n)]
    def findSet(self, i):
        if self.p[i] == i:
            return i
        else:
            self.p[i] = self.findSet(self.p[i])
            return self.p[i]
    def isSameSet(self, i, j):
        return self.findSet(i) == self.findSet(j)
    def unionSet(self, i, j):
        if not self.isSameSet(i, j):
            self.numSets -= 1
            x = self.findSet(i)
            y = self.findSet(j)
            if self.rank[x] > self.rank[y]:
                self.p[y] = x
                self.setSize[x] += self.setSize[y]
            else:
                self.p[x] = y
                self.setSize[y] += self.setSize[x]
                if self.rank[x] == self.rank[y]:
                    self.rank[y] += 1
    def numDisjointSets(self):
        return self.numSets
    def sizeOfSet(self, i):
        return self.setSize[self.findSet(i)]


h, w = [int(i) for i in input().split()]
ch, cw = [int(i)-1 for i in input().split()]
dh, dw = [int(i)-1 for i in input().split()]
A = [input() for i in range(h)]
uf = UnionFind(h*w)
twoonemap = dict()
counter = 0
for i in range(h):
    for j in range(w):
        twoonemap[(i,j)] = counter
        counter += 1
for i in range(h):
    for j in range(w):
        if A[i][j] == '.':
            if j+1 < w and A[i][j+1] == '.':
                uf.unionSet( twoonemap[(i,j)], twoonemap[(i, j+1)])
            if i+1 < h and A[i+1][j] == '.':
                uf.unionSet( twoonemap[(i,j)], twoonemap[(i+1, j)])

source_set = uf.findSet(twoonemap[(ch, cw)])
target_set = uf.findSet(twoonemap[(dh, dw)])

repre_class = defaultdict(int)
for i in range(h):
    for j in range(w):
        repre_class[(i, j)] = uf.findSet(twoonemap[(i,j)])

if source_set == target_set:
    print(0)
    # now find the distance between the disjoint component
else:
    g = defaultdict(set)
    for i in range(h):
        for j in range(w):
            if A[i][j] == '.':
                first_set = repre_class[(i, j)]#uf.findSet(twoonemap[(i,j)])
                for k1 in range(i-2, i+3):
                    for k2 in range(j-2, j+3):
                        if 0<= k1 < h and 0<= k2 < w and A[k1][k2] == '.':
                            second_set = repre_class[(k1, k2)]#uf.findSet(twoonemap[(k1,k2)])
                            if first_set != second_set:
                                g[first_set].add(second_set)
                                g[second_set].add(first_set)

    dist = [-1] *  (h*w)
    q = deque()
    q.append(source_set)  # set
    dist[source_set] = 0
    while q:
        w = q.popleft()
        for v in g[w]:
            if dist[v] == -1:
                q.append(v)
                dist[v] = dist[w] + 1
    print(dist[target_set])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)

from collections import deque

MOVE_DIRECTIONS = ((0, 1), (1, 0), (-1, 0), (0, -1))
WARP_DIRECTIONS = ((2, 2), (1, 2), (0, 2), (-1, 2), (-2, 2), (2, 1), (1, 1), (-1, 1), (-2, 1), (2, 0), (-2, 0), (2, -1), (1, -1), (-1, -1), (-2, -1), (2, -2), (1,-2), (0, -2), (-1, -2), (-2, -2))

def bfs(a,b,dh,dw):
    ans = float('inf')
    q = deque([(a,b,0)])
    
    while q:
        p = q.popleft()
        cx,cy,move_count = p[0],p[1],p[2]
        blocked = 0
        for mx, my in MOVE_DIRECTIONS:
            nx = cx + mx
            ny = cy + my
            if nx >= 0 and nx <= H - 1 and ny >= 0 and ny <= W - 1:
                if searched[nx][ny] > move_count:
                    if nx == dh and ny == dw:
                        if move_count == 0:
                            return 0
                        else:
                            ans = min(ans,move_count)
                            searched[nx][ny] = move_count
                    elif S[nx][ny] == '.':
                        q.append((nx,ny,move_count))
                        searched[nx][ny] = move_count
                    else:
                        blocked += 1
        if blocked > 0:
            for mx, my in WARP_DIRECTIONS:
                nx = cx + mx
                ny = cy + my
                if nx >= 0 and nx <= H - 1 and ny >= 0 and ny <= W - 1:
                    if searched[nx][ny] > move_count + 1:
                        if nx == dh and ny == dw:
                            ans = min(ans,move_count+1)
                            searched[nx][ny] = move_count + 1
                        elif S[nx][ny] == '.':
                            q.append((nx,ny,move_count+1))
                            searched[nx][ny] = move_count + 1
    if ans == float('inf'):
        return -1
    else:
        return ans

H,W,Ch,Cw,Dh,Dw,*S = open(0).read().split()
H = int(H)
W = int(W)
Ch = int(Ch)
Cw = int(Cw)
Dh = int(Dh)
Dw = int(Dw)
searched = [[float('inf')] * W for _ in range(H)]
print(bfs(Ch-1,Cw-1,Dh-1,Dw-1))

Submission status: Time Limit Exceeded

Solution code:
import sys, math

# input = sys.stdin.readline

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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


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


uf = UnionFind(H*W)
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            uf.parents[W*i+j] = math.inf
            continue
        if i != H-1 and S[i + 1][j] == '.':
            uf.union(W*i + j, W*(i+1) + j)
        if j != W-1 and S[i][j+1] == '.':
            uf.union(W*i + j, W*i + j + 1)

groupidx = {k: v for v, k in enumerate(uf.roots())}
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            S[i][j] = -1
        else:
            S[i][j] = groupidx[uf.find(W*i+j)]


groups = list(range(len(uf.roots())))
can_reach = [[False]*len(groups) for _ in range(len(groups))]
for i in range(H):
    for j in range(W):
        if S[i][j] == -1:
            continue
        g = []
        for s in S[i:i+3]:
            g += s[max(0, j-2):j+3]
        g = set(g)
        if -1 in g:
            g.remove(-1)
        for k in g:
            can_reach[S[i][j]][k] = True
            can_reach[k][S[i][j]] = True

can_reach_ = {}
for i in range(len(groups)):
    can_reach_[i] = [j for j, k in enumerate(can_reach[i]) if k]
ans = 0
s = S[Ch-1][Cw-1]
g = S[Dh-1][Dw-1]
if s==g:
    print(0)
    sys.exit()

reached = [s]
searched = [False]*len(groups)
ans = 0
while len(reached)>0:
    new_reached = []
    ans += 1
    for p in reached:
        searched[p] = True
    for p in reached:
        for k in can_reach_[p]:
            if k == g:
                print(ans)
                sys.exit()
            if not searched[k]:
                new_reached.append(k)
    reached = list(set(new_reached))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

def input():
    return sys.stdin.readline().strip()

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

    def bfs(x,y):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
            for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx < 0 or sx >= W or sy < 0 or sy >= H:
                    continue
                if S[sy][sx] == '#':
                    continue
                if S[sy][sx] == '.':
                    S[sy][sx] = S[y][x]
                    que.append((sx,sy))        
                else:
                    if S[sy][sx] > S[y][x]:
                        S[sy][sx] = S[y][x]
                        que.append((sx,sy)) 
            for dx in range(-2,3):
                for dy in range(-2,3):
                    if (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1),(0,0)):
                        continue
                    sx = x + dx
                    sy = y + dy
                    if sx < 0 or sx >= W or sy < 0 or sy >= H:
                        continue
                    if S[sy][sx] == '#':
                        continue
                    if S[sy][sx] == '.':
                        S[sy][sx] = S[y][x] + 1
                        que.append((sx,sy))
                    else:
                        if S[sy][sx] > S[y][x] + 1:
                            S[sy][sx] = S[y][x] + 1
                            que.append((sx,sy))     
    bfs(Cw-1,Ch-1)
    print(S[Dh-1][Dw-1] if S[Dh-1][Dw-1] != '.' else '-1')

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque

H, W = [int(i) for i in input().split()]
C = tuple([int(i) - 1 for i in input().split()])
D = tuple([int(i) - 1 for i in input().split()])
S = []
for i in range(H):
  s = list(input())
  S.append(s)
  
  
# 領域を計算
def dfs(arr, h, w):
  arr[h][w] = "#"
  region = set([tuple([h, w])])
  for i, j in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
      nh = h + i
      nw = w + j
      if 0 <= nh and 0 <= nw and nh < H and nw < W and arr[nh][nw] == ".":
        region |= dfs(arr, nh, nw)
  return region

regions = []
field = copy.deepcopy(S)

for h in range(H):
  for w in range(W):
    if field[h][w] == ".":
      region = dfs(field, h, w);
      regions.append(region)

s_reg = -1
g_reg = -1

for i in range(len(regions)):
  if C in regions[i]:
    s_reg = i
  if D in regions[i]:
    g_reg = i

count = 0
d = deque()
arrived = set()
arrived_pos = set()
d.append(s_reg)
arrived.add(s_reg)

while d:
  pos = d.popleft()
  if pos == g_reg:
    break
  # ワープできる領域を計算
  for p in regions[pos]:
    for h in range(-2, 3):
      for w in range(-2, 3):
        ph = p[0] + h
        pw = p[1] + w
        if pw < 0 or W <= pw or ph < 0 or H <= ph:
          # 欄外
          continue
        if tuple([ph, pw]) in arrived_pos:
          continue
        arrived_pos.add(tuple([ph, pw]))
        for i in range(len(regions)):
          if i not in arrived:
            if tuple([ph, pw]) in regions[i]:
              arrived.add(i)
              d.append(i)
  count += 1
  
if g_reg not in arrived:
  print(-1)
else:
  print(count)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
from heapq import _heapify_max, _heappop_max
import heapq

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)

"""
method:
    heapify(x): ヒープに変換
    heappush(heap, item): itemをheapにpush
    heappop(heap): heapから最小値を取得 空の場合はIndexError
note:
    max heapにする場合は、prefix: _ とsuffix: _maxをつければ良い
"""

def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    inf = 10**7
    dp = [[inf]*w for _ in range(h)]
    s = [list(input()) for _ in range(h)]
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    dxy = list(zip(dx, dy))
    
    rx = (2, 1, 0, -1, -2)
    ry = (2, 1, 0, -1, -2)
    
    dp[ch-1][cw-1] = 0
    
    q = []
    heappush(q, (0, ch-1, cw-1))
    while q:
        cnt = 0
        cost, px, py = heappop(q)
        for xi, yj in dxy:
            x = px + xi
            y = py + yj
            if x >= h or y >= w or x < 0 or y < 0 or s[x][y] == "#":
                continue
            cnt += 1
            if dp[x][y] > cost:
                dp[x][y] = cost
                heappush(q, (cost, x, y))
        if cnt != 4:
            cost += 1
            for di in rx:
                x = px + di
                if x >= h or x < 0:
                    continue
                sx = s[x]
                dpx = dp[x]
                for dj in ry:
                    y = py + dj
                    if y >= w or y < 0 or sx[y] == "#":
                        continue
                    if dpx[y] > cost:
                        dpx[y] = cost
                        heappush(q, (cost, x, y))
    if dp[dh-1][dw-1] == inf:
        print(-1)
    else:
        print(dp[dh-1][dw-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
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())
S = []
for i in range(H):
  S.append(input())


from collections import deque

def bfs(sh,sw):
  queue = deque([(sh,sw)])
  d = [[None]*W for _ in range(H)]
  now = deque()
  d[sh][sw]=0
  
  while queue:
    h,w = queue.popleft()
    now.append((h,w))
    for nh,nw in [(h-1,w),(h+1,w),(h,w-1),(h,w+1)]:
      if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and d[nh][nw] is None) == False: continue
      queue.append((nh,nw))
      now.append((nh,nw))
      d[nh][nw]=d[h][w]

    if queue: continue
    while now:
      h,w = now.popleft()
      for i in range(-2,3):
        for j in range(-2,3):
          if i==0 and abs(j)<=1: continue
          if j == 0 and abs(i)<=1: continue
          nh,nw = h-i,w-j
          if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and d[nh][nw] is None) == False: continue
          d[nh][nw] = d[h][w]+1
          queue.append((nh,nw))
    #print(queue)
  return d

d = bfs(Ch,Cw)
if d[Dh][Dw] == None: 
  print(-1)
  exit()
print(d[Dh][Dw])

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=[""]
for i in range(h):
    S.append("#"+input())
        
V=[[999999 for i in range(w+1)] for q in range(h+1)]

V[ch][cw]=0
que=[(ch,cw)]
head=0

def calc(nx,ny):
    if S[nx][ny]==".":
        return 0
    else:
        return 1

while len(que)>head:
    now=que[head]
    head+=1
    x=now[0]
    y=now[1]
    if S[x][y]==".":
        for nex in  ((x+1,y+1),(x-1,y-1),(x-1,y+1),(x+1,y-1)):
            nx=nex[0]
            ny=nex[1]
            if 0<nx<=h and 0<ny<=w:
                flg=calc(nx,ny)
                if flg==1 and V[x][y]+flg<V[nx][ny]:
                    V[nx][ny]= V[x][y]+flg
                    que.append((nx,ny))
        for nex in ((x+1,y),(x-1,y),(x,y+1),(x,y-1)):
            nx=nex[0]
            ny=nex[1]
            if 0<nx<=h and 0<ny<=w:
                flg=calc(nx,ny)
                if V[x][y]+flg<V[nx][ny]:
                    V[nx][ny]= V[x][y]+flg
                    que.append((nx,ny))
    else:
        for nex in ((x+1,y+1),(x-1,y-1),(x-1,y+1),(x+1,y-1),(x+1,y),(x-1,y),(x,y+1),(x,y-1)):
            nx=nex[0]
            ny=nex[1]
            if 0<nx<=h and 0<ny<=w:
                flg=calc(nx,ny)*1000000
                if flg==0 and V[x][y]+flg<V[nx][ny]:
                    V[nx][ny]= V[x][y]+flg
                    que.append((nx,ny))

if V[dh][dw]==999999:
    print(-1)
else:
    print(V[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
from sys import stdin
input=stdin.readline
n,m=map(int,input().split())
a,b=map(int,input().split())
x,y=map(int,input().split())
x=x-1
y=y-1
arr=[]
from math import inf
for i in range(n):
    arr.append(list(input().strip()))
def isvalid(x,y):
    if x<0 or y<0 or x>=n or y>=m or arr[x][y]=="#" or vis[x][y]==1:
        return False
    return True
vis=[[0]*m for i in range(n)]
stack=[[0,a-1,b-1]]
heapify(stack)
if x==a-1 and y==b-1 and arr[x][y]=="#":
    print(-1)
    quit()
mi=inf
while(stack):
    cost,xx,yy=heappop(stack)
    if xx==x and yy==y:
        mi=min(mi,cost)
    vis[xx ][yy] = 1
    for i in range(-2,3,1):
        for j in range(-2, 3, 1):
            if isvalid(xx+i,yy+j):
                if -1<=i<=1 and -1<=j<=1 and i!=j:

                    heappush(stack,[cost,xx+i,yy+j])
                else:
                    heappush(stack, [cost+1, xx + i, yy + j])
if mi==inf:
    print(-1)
else:
    print(mi)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
C0, C1 = map(int, input().split())
D0, D1 = map(int, input().split())

ARR = []

for i in range(H):
    ARR.append(input())


def calculate(h, w, c0, c1, d0, d1, arr):
    c0 = c0 - 1
    c1 = c1 - 1
    d0 = d0 - 1
    d1 = d1 - 1

    status = []
    for i in range(H):
        tmp = []
        for j in range(W):
            tmp.append(-1)
        status.append(tmp)

    q = deque()

    q.append((c0, c1, 0))

    while len(q) > 0:
        hIndex, wIndex, index = q.popleft()


        if status[hIndex][wIndex] == -1:
            status[hIndex][wIndex] = index
        else:
            if status[hIndex][wIndex] > index:
                status[hIndex][wIndex] = index
            else:
                continue

        for _hIndex in range(hIndex - 2, hIndex + 3):
            for _wIndex in range(wIndex - 2, wIndex + 3):
                if (_hIndex == hIndex) and (_wIndex == wIndex):
                    continue
                if (_hIndex >= 0 and _hIndex < h) and (_wIndex >= 0 and _wIndex < w):
                    if arr[_hIndex][_wIndex] == '.':
                        if status[_hIndex][_wIndex] == 0:
                            continue
                        if (_hIndex == hIndex) and (_wIndex == (wIndex - 1)):
                            tmpIndex = index
                        elif (_hIndex == hIndex) and (_wIndex == (wIndex + 1)):
                            tmpIndex = index
                        elif (_wIndex == wIndex) and (_hIndex == (hIndex - 1)):
                            tmpIndex = index
                        elif (_wIndex == wIndex) and (_hIndex == (hIndex + 1)):
                            tmpIndex = index
                        else:
                            tmpIndex = index + 1

                        if status[_hIndex][_wIndex] == -1:
                            q.append((_hIndex, _wIndex, tmpIndex))
                        elif status[_hIndex][_wIndex] > tmpIndex:
                            q.append((_hIndex, _wIndex, tmpIndex))

    if status[d0][d1] >= 0:
        print(status[d0][d1])
    else:
        print(-1)



calculate(H, W, C0, C1, D0, D1, ARR)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    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()]
    S = [input().strip() for _ in range(H)]

    warp = ((-2, -2), (-2, -2), (-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))

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

    q = collections.deque()
    visited[CH][CW] = 0
    q.append((CH, CW))
    while q:
        cx, cy = q.popleft()
        cc = visited[cx][cy]

        # 隣接
        kabe_cnt = 0
        for nx, ny in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            nnx = cx + nx
            nny = cy + ny
            if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                if S[nnx][nny] == ".":
                    if visited[nnx][nny] > cc:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc
                else:
                    kabe_cnt += 1

        # ワープ
        if kabe_cnt > 0:
            for nx, ny in warp:
                nnx = cx + nx
                nny = cy + ny
                if 0 <= nnx <= H - 1 and 0 <= nny <= W - 1:
                    if S[nnx][nny] == "." and visited[nnx][nny] > cc + 1:
                        q.append((nnx, nny))
                        visited[nnx][nny] = cc + 1

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

h,w = map(int,input().rstrip().split())
sy,sx = map(int,input().rstrip().split())
gy,gx = map(int,input().rstrip().split())
a = [list(input().rstrip())for _ in range(h)]

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

dx=[1,0,-1,0,  2,1,0,-1,-2,  2,1,-1,-2,  2,-2,  2,1,-1,-2,  2,1,0,-1,-2]
dy=[0,1,0,-1,  2,2,2,2,2,  1,1,1,1,  0,0,  -1,-1,-1,-1,  -2,-2,-2,-2,-2]
m = len(dx)

def bfs():
    d = [[float("inf")]*w for _ in range(h)]
    q = deque([])
    q.append((sx,sy))
    d[sy][sx] = 0 #warp回数
    goal = False

    while q:
        p = q.pop()
        
        #print((p[0],p[1]),d[p[1]][p[0]])
        if p[0] == gx and p[1] == gy:
            goal = True

        for i in range(m):
            nx = p[0]+dx[i]
            ny = p[1]+dy[i]
            if i < 4:
                if 0<=nx<w and 0<=ny<h and a[ny][nx] != "#" and d[p[1]][p[0]] < d[ny][nx]:
                    q.append((nx,ny))
                    d[ny][nx] = d[p[1]][p[0]]
            else:
                if 0<=nx<w and 0<=ny<h and a[ny][nx] != "#" and d[p[1]][p[0]] < d[ny][nx]:
                    q.append((nx,ny))
                    d[ny][nx] = d[p[1]][p[0]] + 1

    if goal == False:
        return -1
    else:
        return d[gy][gx]
        
print(bfs())

Submission status: Time Limit Exceeded

Solution code:

from collections import deque
import numpy as np
import sys
sys.setrecursionlimit(10**8)

def bfs(a,b):
    if a == dh+1 and b == dw+1:
        print(s[a,b])
        exit(0) 

    if s[a+1,b]=='.': 
        q.append([a+1,b])
        s[a+1,b]=int(s[a,b])
    elif [a,b] not in wq:
            wq.append([a,b])
    if s[a,b+1]=='.':
        q.append([a,b+1])
        s[a,b+1]=int(s[a,b])
    elif [a,b] not in wq:
            wq.append([a,b])
    if s[a-1,b]=='.':
        q.append([a-1,b])
        s[a-1,b]=int(s[a,b])
    elif [a,b] not in wq:
            wq.append([a,b])
    if s[a,b-1]=='.':
        q.append([a,b-1])
        s[a,b-1]=int(s[a,b])
    elif [a,b] not in wq:
            wq.append([a,b])
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.pop(0)
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return

def worp(a,b):
    for ii in range(-2,3):
        for jj in range(-2,3):
            if s[a+ii,b+jj]=='.':
                q.append([a+ii,b+jj])
                s[a+ii,b+jj]=int(s[a,b])+1
    if len(q)>0:
        temp=q.popleft()
        bfs(temp[0],temp[1])
    elif len(wq)>0:
        temp=wq.pop(0)
        worp(temp[0],temp[1])
    else:
        print(-1)
        exit(0)
    return   

H,W=map(int, input().split())
ch,cw=map(int, input().split())
dh,dw=map(int, input().split())
s=np.array([list(input()) for _ in range(H)],dtype=object)
q = deque([])
wq= []

hbmp=['#']*(W)
s=np.vstack((hbmp,hbmp,s,hbmp,hbmp))
vbmp=[['#']]*(H+4)
s=np.hstack((vbmp,vbmp,s,vbmp,vbmp))

ch,cw=ch+1,cw+1
s[ch,cw]=int(0)

bfs(ch,cw)