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:
h,w=[int(x) for x in input().split()]
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())

l=[]
for i in range(h):
  s=[x for x in input()]
  l.append(s)


done=[[float('inf') for i in range(w)] for j in range(h)]
move=[[-1,0],[1,0],[0,1],[0,-1]]
m1=[]
for i in range(-2,3):
  for j in range(-2,3):
    if i==0 and j==0:
      continue
    else:
      m1.append([i,j])

def bfs(x,y):
  ans=float('inf')
  que=[[x,y,0]]

  while(que):
    nx,ny,cnt = que.pop(0)
    done[ny][nx]=cnt

    if nx==dw-1 and ny==dh-1:
      ans=min(ans,cnt)

    for dx,dy in move:
      mx,my = nx+dx,ny+dy
      if 0<=mx<w and 0<=my<h and (cnt<done[my][mx]):
        if l[my][mx]==".":
          done[my][mx]=cnt
          que.append([mx,my,cnt])

        elif l[my][mx]=="#":
          for i,j in m1:
            if 0<=nx+i<w and 0<=ny+j<h and l[ny+j][nx+i]=="." and cnt+1<done[ny+j][nx+i]:
              done[ny+j][nx+i]=cnt+1
              que.append([nx+i,ny+j,cnt+1])
      
  return ans


ans1=bfs(cw-1,ch-1)

if ans1==float('inf'):
  print(-1)
else:
  print(ans1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque

H, W = map(int, input().split())
Cy, Cx = map(int, input().split())
Dy, Dx = map(int, input().split())
Cy, Cx, Dy, Dx = Cy - 1, Cx - 1, Dy - 1, Dx - 1
grid = []
for i in range(H):
    grid.append(input())


def is_grid(y, x):
    if 0 <= y < H and 0 <= x < W:
        return True
    else:
        return False


INF = 10 ** 6
cost = [[INF] * W for _ in range(H)]

now_stack = deque()
now_stack.append([Cy, Cx])  # 今の頂点から連結な点集合
next_stack = deque()
cnt = 0  # 現在のワープ回数
while cost[Dy][Dx] == INF:
    # print(cost, cnt, "aaa", now_stack)
    while now_stack:  # 連結の点を追加していく、かつ現在の点から+-2 以内をnext_stack にいれる
        k = now_stack.popleft()
        # print(k)
        for i in range(-2, 3):
            for j in range(-2, 3):
                if is_grid(k[0] + i, k[1] + j):
                    cost[k[0] + i][k[1] + j] = min(cost[k[0] + i][k[1] + j], cnt + 1)
        if grid[k[0]][k[1]] == ".":
            # print(k[0], k[1])
            for mv in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
                if (
                    is_grid(k[0] + mv[0], k[1] + mv[1])
                    and grid[k[0] + mv[0]][k[1] + mv[1]] == "."
                    and cost[k[0] + mv[0]][k[1] + mv[1]] > cnt
                ):
                    cost[k[0] + mv[0]][k[1] + mv[1]] = cnt
                    #print(cnt, 2)
                    now_stack.append([k[0] + mv[0], k[1] + mv[1]])
                    #print(cnt, 3)
    cnt += 1
    if next_stack:
        v = next_stack.popleft()
        now_stack.append(v)
print(cost[Dy][Dx])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = 1e9+7

h,w = map(int,input().split())
ch,cw = map(int,input().split())  
dh,dw = map(int,input().split())
maze = [[INF]*(w+4) for _ in range(h+4)]


for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == '.':
            maze[i+2][j+2] = -1

cnt = 0

maze[ch+1][cw+1] = cnt
qh,qw = deque(),deque()
qh.append(ch+1)
qw.append(cw+1)

mqh,mqw = deque(),deque()
flag = False

while True:
    while True:
        if len(qh) == 0:
            break

        nh,nw = qh.popleft(),qw.popleft()
        mqh.append(nh)
        mqw.append(nw)
        dir_h,dir_w = [1,-1,0,0],[0,0,1,-1]
        for i in range(4):
            if maze[nh+dir_h[i]][nw+dir_w[i]] == -1:
                maze[nh+dir_h[i]][nw+dir_w[i]] = cnt
                qh.append(nh+dir_h[i])
                qw.append(nw+dir_w[i])
    
    if maze[dh+1][dw+1] != -1:
        flag = True
        break

    cnt += 1
    while True:
        if len(mqh) == 0:
            break

        nh,nw = mqh.popleft(),mqw.popleft()
        for i in range(5):
            for j in range(5):
                if maze[nh-2+i][nw-2+j] == -1:
                    maze[nh-2+i][nw-2+j] = cnt
                    qh.append(nh-2+i)
                    qw.append(nw-2+j)

    if len(qh) == 0:
        break

if flag:
    print(maze[dh+1][dw+1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
import heapq
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

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

def main():
    from builtins import int, map
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Ch, Cw = Ch - 1, Cw - 1
    Dh, Dw = Dh - 1, Dw - 1
    S = [list(input()) for _ in range(H)]
    counter = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                counter += 1
    # for row in S: print(*row)

    # DFSする (近隣への移動はコスト0，ワープ(5x5-grid)はコスト1)
    dist = defaultdict(lambda: float("inf"))
    dist[Ch, Cw] = 0

    while True:
        visited = set({(Ch, Cw)})
        queue = []
        heapq.heappush(queue, (0, (Ch, Cw)))
        while queue:
            d, (h, w) = heapq.heappop(queue)
            if dist[h, w] < d:
                continue
            
            dist[h, w] = d
            visited.add((h, w))
            # print(queue)

            if dist[h, w] < d:
                continue

            if (h, w) == (Dh, Dw):
                break

            for i in range(4):
                dhi, dwi = dh[i], dw[i]
                nh, nw = h + dhi, w + dwi
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                    if (nh, nw) not in visited:
                        nd = d + 0
                        heapq.heappush(queue, (nd, (nh, nw)))
            
            # 5x5-grid
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nnh, nnw = h + ddh, w + ddw
                    if 0 <= nnh < H and 0 <= nnw < W and S[nnh][nnw] != '#':
                        if (nnh, nnw) not in visited:
                            nd = d + 1
                            heapq.heappush(queue, (nd, (nnh, nnw)))

        break

    if dist[Dh, Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh, Dw])

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

Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

grid = [list(input()) for s in range(H)]

search = [[float('inf')] * W for _ in range(H)]
visit = [[False] * W for _ in range(H)]
dq = deque([])

dq.append((Ch, Cw))
search[Ch][Cw] = 0
visit[Ch][Cw] = True

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]

while dq:
    cur_row, cur_col = dq.popleft()
    cur_step = search[cur_row][cur_col]

    dq_in = deque([])
    dq_in.append((cur_row, cur_col))

    warp_can = []
    while dq_in:
        r, c = dq_in.popleft()

        flag = False
        for dir_y, dir_x in direction:
            new_row = r + dir_x
            new_col = c + dir_y

            if new_row < 0 or new_row >= H or new_col < 0 or new_col >= W:
                continue

            if visit[new_row][new_col]:
                continue

            if grid[new_row][new_col] == '#':
                if not flag:
                    warp_can.append((r, c))
                    flag = True
            else:
                search[new_row][new_col] = cur_step
                dq_in.append((new_row, new_col))

        visit[r][c] = True

    next_island = []
    for w_row, w_col in warp_can:
        for r in range(-2, 3):
            x_row = w_row + r
            for c in range(-2, 3):
                if r == 0 and c == 0:
                    continue

                x_col = w_col + c

                if x_row < 0 or x_row >= H or x_col < 0 or x_col >= W:
                    continue


                if grid[x_row][x_col] == '#':
                    continue



                if visit[x_row][x_col]:
                    continue

                next_island.append((x_row, x_col))

    for x, y in next_island:
        dq.append((x, y))
        search[x][y] = min(cur_step + 1, search[x][y])


if search[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(search[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())
maze_ini = []
for h in range(H):
    maze_ini.append(list(input()))
    
maze = maze_ini
maze[CH-1][CW-1] = "s"
maze[DH-1][DW-1] = "g"

INF = 10**8

d = [[INF for w in range(W)] for h in range(H)] # 各点までの最短距離配列
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
#     →,↑,←,↓

ddx = [0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1]
ddy = [2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1, 0, 1, 2, 2]


from collections import deque
queue = deque([])

queue.append((DW-1, DH-1))
d[DH-1][DW-1] = 0

while len(queue):
    p = queue.popleft()
    if p == (CW-1, CH-1):
        break

    # 4方向を探索
    for i in range(4):
        nx = p[0] + dx[i]
        ny = p[1] + dy[i]
        
        if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] != '#':
            queue.append((nx, ny))
            d[ny][nx] = min(d[ny][nx], d[p[1]][p[0]])
        
        elif  0 <= nx < W and 0 <= ny < H and maze[ny][nx] == '#':
            # ワープ
            for i in range(16):
                nx = p[0] + ddx[i]
                ny = p[1] + ddy[i]

                if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] != '#' and d[ny][nx] > d[p[1]][p[0]]:
                    queue.append((nx, ny))
                    d[ny][nx] = d[p[1]][p[0]] + 1
            
if d[CH-1][CW-1] == INF:
    print(-1)
else:
    print(d[CH-1][CW-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = list(map(int,input().split(' ')))
sy,sx = list(map(int,input().split(' ')))
gy,gx = list(map(int,input().split(' ')))
maze = [[None]*w]*h
for i in range(h):
    maze[i] = list(input())

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

d = [[float("inf")] * w for i in range(h)]
warp = [[float("inf")] * w for i in range(h)]

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


que = deque([])

que.append((sy,sx))

d[sy][sx] = 0
warp[sy][sx] = 0


while que:
    p = que.popleft()

    if p[0] == gy and p[1] == gx:
        break

    for i in range(4):
        ny = p[0] + dy[i]
        nx = p[1] + dx[i]

        if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] != "#" and d[ny][nx] == float("inf"):

            que.append((ny, nx))

            if warp[p[0]][p[1]] < warp[ny][nx]:
                warp[ny][nx] = warp[p[0]][p[1]]
            d[ny][nx] = d[p[0]][p[1]] + 1
    for i,j in [[-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]]:
        ny = p[0]+i
        nx = p[1]+j
        if 0 <= nx < w and 0 <= ny < h:

            if maze[ny][nx] != "#":
                if d[ny][nx] == float("inf"):
                    que.append((ny, nx))
                    warp[ny][nx] = warp[p[0]][p[1]] + 1
                if not d[ny][nx] == float("inf"):
                    if warp[p[0]][p[1]]+1 < warp[ny][nx]:
                        warp[ny][nx] = warp[p[0]][p[1]] + 1
                        que.append((ny, nx))
if not warp[gy][gx] == float("inf"):
    print(warp[gy][gx])
else:
    print(-1)

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


        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 == c0) and (_wIndex == c1):
                    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:
                            status[_hIndex][_wIndex] = tmpIndex
                            q.append((_hIndex, _wIndex, tmpIndex))
                        else:
                            if status[_hIndex][_wIndex] > tmpIndex:
                                status[_hIndex][_wIndex] = tmpIndex
                                q.append((_hIndex, _wIndex, tmpIndex))

                        if (_hIndex == d0) and (_wIndex == d1):
                            break

    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:
from collections import *
H,W = map(int,input().split())
CH,CW = map(int,input().split())
DH,DW = map(int,input().split())
S = 2*[(W+4)*["#"]]+[2*["#"]+list(input())+2*["#"] for h in range(H)]+2*[(W+4)*["#"]]
S[CH+1][CW+1] = 0
P = [[CH+1,CW+1]]
Q = deque([[CH+1,CW+1]])
D1 = [[1,0],[-1,0],[0,1],[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]]
ans = 0

while P:
  P = []
  while Q:
    edge = 0
    y,x = Q.popleft()
    for dy,dx in D1:
      if S[y+dy][x+dx]==".":
        S[y+dy][x+dx] = S[y][x]
        Q.append([y+dy,x+dx])
      elif S[y+dy][x+dx]=="#" and edge==0:
        edge+=1
        P.append([y,x])

  if S[DH+1][DW+1]!=".":
    print(S[DH+1][DW+1])
    exit()
  else:
    ans+=1
    for y,x in P:
      for dy,dx in D2:
        if S[y+dy][x+dx]==".":
          S[y+dy][x+dx] = ans
          Q.append([y+dy,x+dx])

if S[DH+1][DW+1]==".":
  print(-1)
else:
  print(S[DH+1][DW+1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=''
for _ in range(h):
    board+=input().replace('\n','')
uf=UnionFind(h*w)
for y in range(h):
    for x in range(w):
        v=y*w+x
        if board[v]=='#':
            continue
        if y+1<h and board[v+w]=='.':
            uf.Unite(v,v+w)
        if x+1<w and board[v+1]=='.':
            uf.Unite(v,v+1)
edges=[[] for _ in range(h*w+1)]
checked=set()
for y in range(h):
    for x in range(w):
        if board[y*w+x]=='#':
            continue
        for dy in [-2,-1,0,1,2]:
            if y+dy<0 or y+dy>=h:
                continue
            for dx in [-2,-1,0,1,2]:
                if x+dx<0 or x+dx>=w:
                    continue
                if board[(y+dy)*w+(x+dx)]=='#':
                    continue
                r1=uf.FindRoot(y*w+x)
                r2=uf.FindRoot((y+dy)*w+x+dx)
                if (r1,r2) in checked:
                    continue
                if r1!=r2:
                    edges[r1].append(r2)
                    checked.add((r1,r2))
q=collections.deque()
q.append(((uf.FindRoot((sy-1)*w+(sx-1))),0))
checked=[False]*(h*w+1)
ans=10**18
goal=uf.FindRoot((gy-1)*w+(gx-1))
while len(q)!=0:
    v,times=q.popleft()
    if v==goal:
        ans=min(ans,times)
    checked[v]=True
    for u in edges[v]:
        if checked[u]==False:
            q.append((u,times+1))
if ans==10**18:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
AtCoder :: Beginner Contest 176 :: D - Wizard in Maze 
https://atcoder.jp/contests/abc176/tasks/abc176_d
"""
import sys
import heapq
from math import inf


def warp_neighbors(wizard_h, wizard_w, H, W, maze):
    neighbors = []
    for off_h in range(-2, 3, 1):
        for off_w in range(-2, 3, 1):
            h0 = wizard_h+off_h
            w0 = wizard_w+off_w
            # Don't jump to same spot.
            if h0 == wizard_h and w0 == wizard_w:
                continue
            if h0 >= H or h0 < 0 or w0 >= W or w0 < 0:
                continue
            if maze[h0][w0] == '.':
                neighbors.append((h0, w0))
    return neighbors


def walk_neighbors(wizard_h, wizard_w, H, W, maze):
    neighbors = []
    offs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
    for off_h, off_w in offs:
        h0 = wizard_h+off_h
        w0 = wizard_w+off_w
        if h0 >= H or h0 < 0 or w0 >= W or w0 < 0:
            continue
        if maze[h0][w0] == '.':
            neighbors.append((h0, w0))
    return neighbors


def main():
    """Main program."""
    H, W = (int(i) for i in sys.stdin.readline().split())
    wizard_h, wizard_w = (int(i) for i in sys.stdin.readline().split())
    dest_h, dest_w = (int(i) for i in sys.stdin.readline().split())
    # Convert to zero-based
    wizard_h -= 1
    wizard_w -= 1
    dest_h -= 1
    dest_w -= 1

    maze = [sys.stdin.readline().strip() for _ in range(H)]
    dist = [[inf for w in range(W)] for h in range(H)]
    dist[wizard_h][wizard_w] = 0
    mdist = [[abs(dest_h-h)+abs(dest_w-w) for w in range(W)] for h in range(H)]

    queue = [(0, 0, wizard_h, wizard_w)]
    while queue:
        _, _, h0, w0 = heapq.heappop(queue)

        for h1, w1 in walk_neighbors(h0, w0, H, W, maze):
            if dist[h1][w1] > dist[h0][w0]:
                dist[h1][w1] = dist[h0][w0]
                heapq.heappush(queue, (mdist[h1][w1], dist[h1][w1], h1, w1))
                
        for h2, w2 in warp_neighbors(h0, w0, H, W, maze):
            if dist[h2][w2] > dist[h0][w0] + 1:
                dist[h2][w2] = dist[h0][w0] + 1
                heapq.heappush(queue, (mdist[h2][w2], dist[h2][w2], h2, w2))


    if dist[dest_h][dest_w] == inf:
        print(-1)
    else:
        print(dist[dest_h][dest_w])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10


def main():
	H, W = MAP()
	Ch, Cw = MAP()
	Dh, Dw = MAP()
	S = [input() for _ in range(H)]

	cnt = [[INF]*W for _ in range(H)]
	cnt[Ch-1][Cw-1] = 0

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

	q = deque([(Ch-1, Cw-1, 0)])
	while q:
		y, x, c = q.popleft()
		if cnt[y][x] != c:
			continue
		flg = True
		for i in range(24):
			if i == 4 and flg:
				break
			ny = y + dy[i]
			nx = x + dx[i]
			if ny < 0 or nx < 0 or H <= ny or W <= nx:
				continue
			elif i < 4:
				if S[ny][nx] == "." and c < cnt[ny][nx]:
					cnt[ny][nx] = c
					q.append((ny, nx, c))
				elif S[ny][nx] == "#":
					flg = False
			elif 4 <= i and S[ny][nx] == "." and c+1 < cnt[ny][nx]:
				cnt[ny][nx] = c+1
				q.append((ny, nx, c+1))


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

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]:
                    if dx[i] == 2:
                        if a[ny][nx-1] == ".":
                            continue
                    if dx[i] == -2:
                        if a[ny][nx+1] == ".":
                            continue
                    if dy[i] == 2:
                        if a[ny-1][nx] == ".":
                            continue
                    if dy[i] == -2:
                        if a[ny+1][nx] == ".":
                            continue
                    if dx[i] == 1 and dy[i] == 1:
                        if a[ny-1][nx] == "." or a[ny][nx-1] == ".":
                            continue
                    if dx[i] == 1 and dy[i] == -1:
                        if a[ny+1][nx] == "." or a[ny][nx-1] == ".":
                            continue
                    if dx[i] == -1 and dy[i] == 1:
                        if a[ny-1][nx] == "." or a[ny][nx+1] == ".":
                            continue
                    if dx[i] == -1 and dy[i] == -1:
                        if a[ny+1][nx] == "." or a[ny][nx+1] == ".":
                            continue
                            
                    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:
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 = set()
  d[sh][sw]=0
  
  while queue:
    h,w = queue.popleft()
    now.add((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.add((nh,nw))
      d[nh][nw]=d[h][w]
      if nh == Dh and nw == Dw:return d
    if queue: continue
    for h,w in now:
      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
          if nh == Dh and nw == Dw:return d
          queue.append((nh,nw))
    now = set()
    #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:
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())

cy -= 1
cx -= 1
gy -= 1
gx -= 1

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

q = deque()
# x, y, 累積移動距離, ブロック通過数, ワープ利用数
q.append((cx, cy, 0, 0, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, c, d, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    # print(x, y, c, d, e)
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            q.appendleft((nx, ny, c+1, d, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            # print("warp", dx, dy)
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "#":
                if nx == gx and ny == gy:
                    ans = min(ans, e+1)
                    continue
                # print("warp append")
                q.appendleft((nx, ny, c+1, d, e+1))

print(-1 if ans == float("inf") else ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


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


def main():
    INF = 10**7
    h, w = [int(i) for i in input().split()]
    c_h, c_w = [int(i) for i in input().split()]
    d_h, d_w = [int(i) for i in input().split()]
    grid = [["#"] * (w + 2)]
    for _ in range(h):
        line = ["#"] + list(input()) + ["#"]
        grid.append(line)
    grid.append(["#"] * (w + 2))
    warp_count = [[INF] * (w + 2) for _ in range(h + 2)]
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    warps = []
    for x in range(-2, 3):
        for y in range(-2, 3):
            if x == 0 and y == 0:
                continue
            if (x, y) not in directions:
                warps.append((x, y))

    stack = []
    warp_count[c_h][c_w] = 0
    stack.append((c_h, c_w, 0))

    while stack:
        _h, _w, warp = stack.pop()
        warp_count[_h][_w] = warp

        cnt = 0
        # walk
        for _a, _b in directions:
            if grid[_h + _a][_w + _b] != "#" and warp_count[_h + _a][_w + _b] > warp:
                cnt += 1
                stack.append((_h + _a, _w + _b, warp))

        if cnt == 4:  # 4方向行けるときにワープは不要
            continue

        # warp
        for x, y in warps:
            if _h + x < 0 or _h + x > h or _w + y < 0 or _w + y > w:
                continue
            elif grid[_h + x][_w + y] == "#":
                continue

            if warp_count[_h + x][_w + y] > warp + 1:
                stack.append((_h + x, _w + y, warp + 1))

    if warp_count[d_h][d_w] == INF:
        print(-1)
    else:
        print(warp_count[d_h][d_w])
    return


if __name__ == "__main__":
    main()