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:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline
    warp_up = [
        (-2, -2),
        (-1, -2),
        (0, -2),
        (1, -2),
        (2, -2),
        (-2, -1),
        (-1, -1),
        (1, -1),
        (2, -1),
    ]
    warp_do = [
        (2, 2),
        (1, 2),
        (0, 2),
        (-1, 2),
        (-2, 2),
        (2, 1),
        (1, 1),
        (-1, 1),
        (-2, 1),
    ]
    warp_ri = [
        (2, -2),
        (2, -1),
        (2, 0),
        (2, 1),
        (2, 2),
        (1, -2),
        (1, -1),
        (1, 1),
        (1, 2),
    ]
    warp_le = [
        (-2, 2),
        (-2, 1),
        (-2, 0),
        (-2, -1),
        (-2, -2),
        (-1, 2),
        (-1, 1),
        (-1, -1),
        (-1, -2),
    ]

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    c = [input().rstrip() for _ in range(h)]
    cw -= 1
    ch -= 1
    dw -= 1
    dh -= 1
    c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
    d1 = deque([[cw, ch]])
    d2 = deque([])

    for cnt in range(30000):
        for _ in range(100000):
            for _ in range(len(d1)):
                now_x, now_y = d1.popleft()
                for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                    x, y = now_x + next_x, now_y + next_y
                    if 0 <= x < w and 0 <= y < h:
                        if x == dw and y == dh:
                            print(cnt)
                            exit()
                        c_xy = c[y][x]
                        if c_xy == "#":
                            next = [next_x, next_y]
                            if next == [1, 0]:
                                warp = warp_ri.copy()
                            elif next == [0, 1]:
                                warp = warp_do.copy()
                            elif next == [-1, 0]:
                                warp = warp_le.copy()
                            elif next == [0, -1]:
                                warp = warp_up.copy()
                            for next_x, next_y in warp:
                                x, y = now_x + next_x, now_y + next_y
                                if 0 <= x < w and 0 <= y < h:
                                    if c[y][x] not in "#=!":
                                        c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                                        d2.append([x, y])
                        elif c_xy != "=":
                            c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                            d1.append([x, y])
        else:
            if [dw, dh] in d2:
                print(cnt + 1)
                exit()
            if not d2:
                print(-1)
                exit()
            d1 = d2.copy()
            d2.clear()


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import itertools

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


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


h, w = MI()
Ch, Cw = MI()
Dh, Dw = MI()

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

dxy = ((0, 1), (0, -1), (1, 0), (-1, 0), (0, 0))
wxy = tuple(
    (x, y)
    for x, y in itertools.product([-2, -1, 0, 1, 2], repeat=2)
    if (x, y) not in dxy
)
dxy = ((0, 1), (0, -1), (1, 0), (-1, 0))

wq = {(Ch + 1, Cw + 1)}
cost = 0
while wq:
    q = wq
    passed = []
    while q:
        qq = []
        for y, x in q:
            if y == Dh + 1 and x == Dw + 1:
                print(cost)
                exit()
            passed.append((y, x))
            S[y][x] = "#"
            for dy, dx in dxy:
                ny, nx = y + dy, x + dx
                if S[ny][nx] == "#":
                    continue
                # if ny == Dh + 1 and nx == Dw + 1:
                #     print(cost)
                #     exit()
                qq.append((ny, nx))
                # S[ny][nx] = "#"
        q = qq

    # print(cost, set(passed))
    wq = set()
    for y, x in passed:
        for dy, dx in wxy:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == "#":
                continue
            wq.add((ny, nx))

    cost += 1

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque()
d.append((Ch, Cw))
flag = True
ans = 0
s = set()

while True:
  while flag:
    flag = False
    for _ in range(len(d)):
      Th, Tw = d.popleft()
      for i,j in [(1,0),(-1,0),(0,1),(0,-1),(0,0)]:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        temp = (Th + i, Tw + i)
        if (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
          # print(_p)
          if not(i == 0 and j == 0):
            flag = True
  if (Dh,Dw) in d:
    print(ans)
    exit()
  else:
    s |= set(d)
    temps = set(d)
    d = deque()
    for Th,Tw in temps:
      for i in [-2,-1,0,1,2]:
        for j in [-2,-1,0,1,2]:
          _h = Th + i
          _w = Tw + j
          _p = (_h, _w)
          temp = (Th + i, Tw + i)
          if (not (_p) in temps) and (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
            d.append(_p)
    if len(d) == 0:
      print('-1')
      exit()
    ans += 1

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import itertools

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


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


h, w = MI()
Ch, Cw = MI()
Dh, Dw = MI()

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

dxy = ((0, 1), (0, -1), (1, 0), (-1, 0), (0, 0))
wxy = tuple(
    (x, y)
    for x, y in itertools.product([-2, -1, 0, 1, 2], repeat=2)
    if (x, y) not in dxy
)
dxy = ((0, 1), (0, -1), (1, 0), (-1, 0))

wq = {(Ch + 1, Cw + 1)}
cost = 0
while wq:
    q = list(wq)
    passed = []
    while q:
        qq = []
        for y, x in q:
            if y == Dh + 1 and x == Dw + 1:
                print(cost)
                exit()
            passed.append((y, x))
            S[y][x] = "#"
            for dy, dx in dxy:
                ny, nx = y + dy, x + dx
                if S[ny][nx] == "#":
                    continue
                # if ny == Dh + 1 and nx == Dw + 1:
                #     print(cost)
                #     exit()
                qq.append((ny, nx))
                # S[ny][nx] = "#"
        q = qq

    # print(cost, set(passed))
    wq = set()
    for y, x in passed:
        for dy, dx in wxy:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == "#":
                continue
            wq.add((ny, nx))

    cost += 1

print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline
    warp_up = [
        (-2, -2),
        (-1, -2),
        (0, -2),
        (1, -2),
        (2, -2),
        (-2, -1),
        (-1, -1),
        (1, -1),
        (2, -1),
    ]
    warp_do = [
        (2, 2),
        (1, 2),
        (0, 2),
        (-1, 2),
        (-2, 2),
        (2, 1),
        (1, 1),
        (-1, 1),
        (-2, 1),
    ]
    warp_ri = [
        (2, -2),
        (2, -1),
        (2, 0),
        (2, 1),
        (2, 2),
        (1, -2),
        (1, -1),
        (1, 1),
        (1, 2),
    ]
    warp_le = [
        (-2, 2),
        (-2, 1),
        (-2, 0),
        (-2, -1),
        (-2, -2),
        (-1, 2),
        (-1, 1),
        (-1, -1),
        (-1, -2),
    ]

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    c = [input().rstrip() for _ in range(h)]
    cw -= 1
    ch -= 1
    dw -= 1
    dh -= 1
    c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
    d1 = deque([[cw, ch]])
    d2 = deque([])

    for cnt in range(40000):
        for _ in range(40000):
            for _ in range(len(d1)):
                now_x, now_y = d1.popleft()
                for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                    x, y = now_x + next_x, now_y + next_y
                    if 0 <= x < w and 0 <= y < h:
                        if x == dw and y == dh:
                            print(cnt)
                            exit()
                        c_xy = c[y][x]
                        if c_xy == "#":
                            next = [next_x, next_y]
                            if next == [1, 0]:
                                warp = warp_ri.copy()
                            elif next == [0, 1]:
                                warp = warp_do.copy()
                            elif next == [-1, 0]:
                                warp = warp_le.copy()
                            elif next == [0, -1]:
                                warp = warp_up.copy()
                            for next_x, next_y in warp:
                                x, y = now_x + next_x, now_y + next_y
                                if 0 <= x < w and 0 <= y < h:
                                    if c[y][x] not in "#=!":
                                        c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                                        d2.append([x, y])
                        elif c_xy != "=":
                            c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                            d1.append([x, y])
        else:
            if [dw, dh] in d2:
                print(cnt + 1)
                exit()
            if not d2:
                print(-1)
                exit()
            d1 = d2.copy()
            d2.clear()


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

h, w = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
dh, dw = list(map(int, input().split()))
s = [list(input()) for _ in range(h)]

def check_range(x, y):
    return (0 <= x < h) and (0 <= y < w)

heap = [(0, ch - 1, cw - 1)]
inf = 1000000000
dist = [[inf for i in range(w)] for _ in range(h)]

while len(heap):
    if dist[dh - 1][dw - 1] != inf:
        break

    d, x, y = heapq.heappop(heap)

    if dist[x][y] != inf:
        continue
    if dist[x][y] < d:
        continue

    dist[x][y] = d
    #print(d, x, y)

    # 移動A
    for dx, dy in [(0, -1), (0, +1), (-1, 0), (+1, 0)]:
        nx, ny = x + dx, y + dy
        if check_range(nx, ny) and s[nx][ny] == '.' and dist[nx][ny] == inf:
            item = (d, nx, ny)
            heapq.heappush(heap, item)

    # 移動B
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            nx, ny = x + dx, y + dy
            if check_range(nx, ny) and s[nx][ny] != '#' and dist[nx][ny] == inf:
                item = (d + 1, nx, ny)
                heapq.heappush(heap, item)

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

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())
A=[]
for i in range(H):
  d=list(input())
  A.append(d)
D=[[10**8]*W for i in range(H)]
dy=[-1,1,0,0]
dx=[0,0,1,-1,]
ey=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ex=[0,1,2,-1,-2,1,2,-1,-2,2,-2,1,2,-1,-2,0,1,2,-1,-2]
for h in range(H):
  for w in range(W):
    if A[h][w]=='#':
      D[h][w]=10**5
from collections import deque
import sys
sys.setrecursionlimit(10**7) 
def bfs(y,x):
  q=deque()
  q.append((y,x))
  
  while len(q):
    y,x=q.popleft()
    cnt=0
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W:
        if A[ny][nx]=='.' and D[y][x]<D[ny][nx]:
          q.appendleft((ny,nx))
          D[ny][nx]=D[y][x]

    for i in range(20):
      my=y+ey[i]
      mx=x+ex[i]
      if 0<=my<H and 0<=mx<W:
        if A[my][mx]=='.' and D[my][mx]==10**8:
          q.append((my,mx))
          D[my][mx]=D[y][x]+1
            
D[Ch-1][Cw-1]=0
bfs(Ch-1,Cw-1)
if D[Dh-1][Dw-1]==10**8:
  print(-1)
else:
  print(D[Dh-1][Dw-1])

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, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
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 ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
sy, sx = MAP()
gy, gx = MAP()
sx += 1
sy += 1
gx += 1
gy += 1
S = ["#"*(W+4)]*2+["##"+input()+"##" for _ in range(H)]+["#"*(W+4)]*2
dist = [[10**6]*(W+4) for _ in range(H+4)]
dist[sy][sx] = 0
q = deque()
q.append((sy, sx, 0))

while q:
    y, x, cnt = q.popleft()
    if dist[y][x] != cnt:
        continue
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            ny = y+dy
            nx = x+dx
            if abs(dx)+abs(dy) > 1:
                if S[ny][nx] == "." and dist[ny][nx] >  dist[y][x]+1:
                    dist[ny][nx] = cnt + 1
                    q.append((ny, nx, cnt+1))
            else:
                if S[ny][nx] == "." and dist[ny][nx] > dist[y][x]:
                    dist[ny][nx] = cnt
                    q.appendleft((ny, nx, cnt))
# print(*dist, sep="\n")
print(dist[gy][gx] if dist[gy][gx] != 10**6 else -1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline
    warp_up = [
        (-2, -2),
        (-1, -2),
        (0, -2),
        (1, -2),
        (2, -2),
        (-2, -1),
        (-1, -1),
        (1, -1),
        (2, -1),
    ]
    warp_do = [
        (2, 2),
        (1, 2),
        (0, 2),
        (-1, 2),
        (-2, 2),
        (2, 1),
        (1, 1),
        (-1, 1),
        (-2, 1),
    ]
    warp_ri = [
        (2, -2),
        (2, -1),
        (2, 0),
        (2, 1),
        (2, 2),
        (1, -2),
        (1, -1),
        (1, 1),
        (1, 2),
    ]
    warp_le = [
        (-2, 2),
        (-2, 1),
        (-2, 0),
        (-2, -1),
        (-2, -2),
        (-1, 2),
        (-1, 1),
        (-1, -1),
        (-1, -2),
    ]

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    c = [input().rstrip() for _ in range(h)]
    cw -= 1
    ch -= 1
    dw -= 1
    dh -= 1
    c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
    d1 = deque([[cw, ch]])
    d2 = deque([])

    for cnt in range(50000):
        for _ in range(50000):
            for _ in range(len(d1)):
                now_x, now_y = d1.popleft()
                for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                    x, y = now_x + next_x, now_y + next_y
                    if 0 <= x < w and 0 <= y < h:
                        if x == dw and y == dh:
                            print(cnt)
                            exit()
                        c_xy = c[y][x]
                        if c_xy == "#":
                            next = [next_x, next_y]
                            if next == [1, 0]:
                                warp = warp_ri.copy()
                            elif next == [0, 1]:
                                warp = warp_do.copy()
                            elif next == [-1, 0]:
                                warp = warp_le.copy()
                            elif next == [0, -1]:
                                warp = warp_up.copy()
                            for next_x, next_y in warp:
                                x, y = now_x + next_x, now_y + next_y
                                if 0 <= x < w and 0 <= y < h:
                                    if c[y][x] not in "#=!":
                                        c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                                        d2.append([x, y])
                        elif c_xy != "=":
                            c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                            d1.append([x, y])
        else:
            if [dw, dh] in d2:
                print(cnt + 1)
                exit()
            if not d2:
                print(-1)
                exit()
            d1 = d2.copy()
            d2.clear()


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
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque()
d.append((Ch, Cw))
flag = True
ans = 0
s = set()

while True:
  while flag:
    flag = False
    for _ in range(len(d)):
      Th, Tw = d.popleft()
      for i,j in [(1,0),(-1,0),(0,1),(0,-1),(0,0)]:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        temp = (Th + i, Tw + i)
        if (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
          # print(_p)
          if not(i == 0 and j == 0):
            flag = True
  if (Dh,Dw) in d:
    print(ans)
    exit()
  else:
    s |= set(d)
    temps = set(d)
    d = deque()
    for Th,Tw in s:
      for i in [-2,-1,0,1,2]:
        for j in [-2,-1,0,1,2]:
          _h = Th + i
          _w = Tw + j
          _p = (_h, _w)
          temp = (Th + i, Tw + i)
          if (not (_p) in temps) and (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
            d.append(_p)
    if len(d) == 0:
      print('-1')
      exit()
    ans += 1

Submission status: Time Limit Exceeded

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

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx,0))
count=0
while len(q)!=0:
  y,x,score=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>score:
      scores[y+dy][x+dx]=score
      q.append((y+dy,x+dx,score))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>score+1:
        scores[y+dy][x+dx]=score+1
        q.appendleft((y+dy,x+dx,score+1))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = set()
stock = []
setmada = [start]
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in setmada:
			stock.append((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if k in yukaset:
					if k not in settansaku:
						setmada.append(k)
						settansaku.add(k)
	
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					setmada.append(k)
					settansaku.add(k)
	
	stock = []
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline
    warp_up = [
        (-2, -2),
        (-1, -2),
        (0, -2),
        (1, -2),
        (2, -2),
        (-2, -1),
        (-1, -1),
        (1, -1),
        (2, -1),
    ]
    warp_do = [
        (2, 2),
        (1, 2),
        (0, 2),
        (-1, 2),
        (-2, 2),
        (2, 1),
        (1, 1),
        (-1, 1),
        (-2, 1),
    ]
    warp_ri = [
        (2, -2),
        (2, -1),
        (2, 0),
        (2, 1),
        (2, 2),
        (1, -2),
        (1, -1),
        (1, 1),
        (1, 2),
    ]
    warp_le = [
        (-2, 2),
        (-2, 1),
        (-2, 0),
        (-2, -1),
        (-2, -2),
        (-1, 2),
        (-1, 1),
        (-1, -1),
        (-1, -2),
    ]

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    c = [input().rstrip() for _ in range(h)]
    cw -= 1
    ch -= 1
    dw -= 1
    dh -= 1
    c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
    d1 = deque([[cw, ch]])
    d2 = deque([])

    for cnt in range(100000):
        for _ in range(100000):
            for _ in range(len(d1)):
                now_x, now_y = d1.popleft()
                for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                    x, y = now_x + next_x, now_y + next_y
                    if 0 <= x < w and 0 <= y < h:
                        if x == dw and y == dh:
                            print(cnt)
                            exit()
                        c_xy = c[y][x]
                        if c_xy == "#":
                            next = [next_x, next_y]
                            if next == [1, 0]:
                                warp = warp_ri.copy()
                            elif next == [0, 1]:
                                warp = warp_do.copy()
                            elif next == [-1, 0]:
                                warp = warp_le.copy()
                            elif next == [0, -1]:
                                warp = warp_up.copy()
                            for next_x, next_y in warp:
                                x, y = now_x + next_x, now_y + next_y
                                if 0 <= x < w and 0 <= y < h:
                                    if c[y][x] not in "#=!":
                                        c[y] = c[y][:x] + "!" + c[y][x + 1 :]
                                        d2.append([x, y])
                        elif c_xy != "=":
                            c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                            d1.append([x, y])
        else:
            if [dw, dh] in d2:
                print(cnt + 1)
                exit()
            if not d2:
                print(-1)
                exit()
            d1 = d2.copy()
            d2.clear()


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
narr = lambda d, f: narr(d[:-1], lambda: [f() for _ in range(d[-1])]) if d else f() # narr((2,3), int)
mod = 1000000007
sys.setrecursionlimit(1000000)

H, W = rl()
C = rl()
D = rl()
M = []
for i in range(H):
	s = rs()
	M.append(s)

start = tuple([C[0]-1, C[1]-1])
end = tuple([D[0]-1, D[1]-1])

queue = deque()
queue.append((start, 0))
visited = narr((H, W), lambda: float('inf'))
visited[start[0]][start[1]] = 0

ds = [(1,0),(-1,0),(0,1),(0,-1)]
while queue:
	n, d = queue.popleft()
	if n == end:
		print(d)
		exit()
	i, j = n
	if visited[i][j] != d:
		continue
	nd = d
	for di, dj in ds:
		ni, nj = i+di, j+dj
		if not (0 <= ni < H and 0 <= nj < W): continue
		if M[ni][nj] == '#': continue
		if nd < visited[ni][nj]:
			queue.appendleft(((ni,nj), nd))
			visited[ni][nj] = nd
	nd = d+1
	for di in range(-2, 3):
		for dj in range(-2, 3):
			if (di, dj) == (0,0): continue
			ni, nj = i+di, j+dj
			if not (0 <= ni < H and 0 <= nj < W): continue
			if M[ni][nj] == '#': continue
			if nd < visited[ni][nj]:
				queue.append(((ni,nj), nd))
				visited[ni][nj] = nd
print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import itertools

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


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


h, w = MI()
Ch, Cw = MI()
Dh, Dw = MI()

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

dxy = ((0, 1), (0, -1), (1, 0), (-1, 0), (0, 0))
wxy = tuple(
    (x, y)
    for x, y in itertools.product([-2, -1, 0, 1, 2], repeat=2)
    if (x, y) not in dxy
)
dxy = ((0, 1), (0, -1), (1, 0), (-1, 0))

wq = [(Ch + 1, Cw + 1)]
cost = 0
while wq:
    q = list(set(wq))
    wq = []
    passed = []
    while q:
        qq = []
        for y, x in q:
            if y == Dh + 1 and x == Dw + 1:
                print(cost)
                exit()
            passed.append((y, x))
            S[y][x] = "#"
            for dy, dx in dxy:
                ny, nx = y + dy, x + dx
                if S[ny][nx] == "#":
                    continue
                # if ny == Dh + 1 and nx == Dw + 1:
                #     print(cost)
                #     exit()
                qq.append((ny, nx))
                # S[ny][nx] = "#"
        q = qq

    # print(cost, set(passed))
    for y, x in passed:
        for dy, dx in wxy:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == "#":
                continue
            wq.append((ny, nx))

    cost += 1

print(-1)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = set()
stock = []
setmada = [start]
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			stock.append((i, j))
			setmada.append((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if k in yukaset:
					if k not in settansaku:
						setmada.append(k)
						settansaku.add((i, j))
	
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					setmada.append(k)
	
	stock = []
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque()
d.append((Ch, Cw))
flag = True
ans = 0

while True:
  while flag:
    flag = False
    for _ in range(len(d)):
      Th, Tw = d.popleft()
      for i,j in [(1,0),(-1,0),(0,1),(0,-1),(0,0)]:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        temp = (Th + i, Tw + i)
        if (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
          # print(_p)
          if not(i == 0 and j == 0):
            flag = True
  if (Dh,Dw) in d:
    print(ans)
    exit()
  else:
    l = set(d)
    d = deque()
    for Th,Tw in l:
      for i in [-2,-1,0,1,2]:
        for j in [-2,-1,0,1,2]:
          _h = Th + i
          _w = Tw + j
          _p = (_h, _w)
          temp = (Th + i, Tw + i)
          if (not (_p) in l) and (not (_p) in d) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
            d.append(_p)
    if len(d) == 0:
      print('-1')
      exit()
    ans += 1