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:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

def main():
    H, W = LI()
    CH, CW = LI1()
    DH, DW = LI1()
    S = SR(H)
    dist = make_list(H, W, default=-1)

    q = deque()
    dist[CH][CW] = 0
    q.append((0, CH, CW))



    while q:
        d, y, x = q.popleft()

        for dx in range(-2, 2+1):
            for dy in range(-2, 2+1):
                newx, newy = x + dx, y + dy
                if newx >= 0 and newx < W and newy >= 0 and newy < H:
                    if S[newy][newx] == ".":
                        cost = int([dy, dx] not in dire)
                        if dist[newy][newx] == -1 or dist[newy][newx] > d + cost:
                            dist[newy][newx] = d + cost
                            if cost:
                                q.append((d + 1, newy, newx))
                            else:
                                q.appendleft((d, newy, newx))

    print(dist[DH][DW])







if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

# 入力
H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
maze = []
for i in range(H):
    maze.append(list(input()))

# コストをまとめる表
cost = [[float("inf")] * W for i in range(H)]

def bfs(que, c):
    # 幅優先探索を用いて、位置(init_x, init_y)から追加コストなしで辿り着けるマスを列挙

    next_que = deque([])

    while que:

        # キューの先頭を取り出す
        x, y = que.popleft()
        cost[x][y] = c

        # 取り出してきたキューがゴールなら探索をやめる
        if (x, y) == (D_h-1, D_w-1):
            return True, next_que

        moveA_vector = [(1,0),(-1,0),(0,1),(0,-1)]

        # 現在地から移動Aで到達可能で未探索の点をキューに追加
        # 移動4方向をループ
        for dx, dy in moveA_vector:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and cost[nx][ny] == float("inf"):
                que.append((nx, ny))
                # cost[nx][ny] = c この処理は先頭でやる

        # 現在地から移動Bで到達可能で未探索の点を次のコストのキューに追加
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if (dx, dy) not in moveA_vector:  # 5*5の範囲内でかつ移動Aで到達できない点 = 現在地から移動Bで到達可能な点
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and cost[nx][ny] == float("inf"):  # 到達可能で未探索の点
                        if ((nx, ny) not in next_que) and ((nx+1, ny) not in next_que) and ((nx-1, ny) not in next_que) and ((nx, ny+1) not in next_que) and ((nx, ny-1) not in next_que):
                            # next_queにすでに入っている点でなく、next_queにすでに入っている点から移動Aで到達できる点でもない
                            next_que.append((nx, ny))

    return False, next_que

c = 0
que = deque([])
que.append((C_h-1, C_w-1))
while True:
    f, que = bfs(que, c)
    if f:  # ゴールが見つかった
        print(c)
        sys.exit()
    if not que:  # queが空のとき、これ以上移動不可能（dequeなのでque==[]は誤り）
        break
    c += 1
print("-1")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

# 入力
H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
maze = []
for i in range(H):
    maze.append(list(input()))

# コストをまとめる表
cost = [[float("inf")] * W for i in range(H)]

def bfs(que, c):
    # 幅優先探索を用いて、位置(init_x, init_y)から追加コストなしで辿り着けるマスを列挙

    next_que = deque([])

    while que:

        # キューの先頭を取り出す
        x, y = que.popleft()
        cost[x][y] = c

        # 取り出してきたキューがゴールなら探索をやめる
        if (x, y) == (D_h-1, D_w-1):
            return True, next_que

        moveA_vector = [(1,0),(-1,0),(0,1),(0,-1)]

        # 現在地から移動Aで到達可能で未探索の点をキューに追加
        # 移動4方向をループ
        for dx, dy in moveA_vector:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and cost[nx][ny] == float("inf"):
                que.append((nx, ny))
                # cost[nx][ny] = c この処理は先頭でやる

        # 現在地から移動Bで到達可能で未探索の点を次のコストのキューに追加
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                if (dx, dy) not in moveA_vector:  # 5*5の範囲内でかつ移動Aで到達できない点
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and cost[nx][ny] == float("inf") and (nx, ny) not in next_que:
                        next_que.append((nx, ny))

    return False, next_que

c = 0
que = deque([])
que.append((C_h-1, C_w-1))
while True:
    f, que = bfs(que, c)
    if f:  # ゴールが見つかった
        print(c)
        sys.exit()
    if not que:  # queが空のとき、これ以上移動不可能（dequeなのでque==[]は誤り）
        break
    c += 1
print("-1")

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)


def main(input, print):
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    move2 = [(-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)]

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

    que = deque()
    path[Ch-1][Cw-1] = 0
    que.append((Ch-1, Cw-1))
    while que:
        y, x = que.pop()
        cnt = path[y][x]

        for i, j in move:
            nx = x+i
            ny = y+j
            if ny < 0 or nx < 0 or ny >= H or nx >= W:
                continue
            if table[ny][nx] == '#':
                continue
            if path[ny][nx] == -1 or path[ny][nx] > cnt:
                path[ny][nx] = cnt
                que.appendleft((ny, nx))

        for i, j in move2:
            nx = x+i
            ny = y+j
            if ny < 0 or nx < 0 or ny >= H or nx >= W:
                continue
            if table[ny][nx] == '#':
                continue
            if path[ny][nx] == -1 or path[ny][nx] > cnt+1:
                path[ny][nx] = cnt+1
                que.append((ny, nx))
    if(path[Dh-1][Dw-1] == -1):
        print(-1)
    else:
        print(path[Dh-1][Dw-1])


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)


def main(input, print):
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    move2 = [(-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)]

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

    que = deque()
    path[Ch-1][Cw-1] = 0
    que.append((Ch-1, Cw-1))
    while que:
        y, x = que.pop()
        cnt = path[y][x]

        for k in range(len(move)):
            i, j = move[k]
            nx = x+i
            ny = y+j
            if ny < 0 or nx < 0 or ny >= H or nx >= W:
                continue
            if table[ny][nx] == '#':
                continue
            if path[ny][nx] == -1 or path[ny][nx] > cnt:
                path[ny][nx] = cnt
                que.appendleft((ny, nx))

        for k in range(len(move2)):
            i, j = move2[k]
            nx = x+i
            ny = y+j
            if ny < 0 or nx < 0 or ny >= H or nx >= W:
                continue
            if table[ny][nx] == '#':
                continue
            if path[ny][nx] == -1 or path[ny][nx] > cnt+1:
                path[ny][nx] = cnt+1
                que.append((ny, nx))
    if(path[Dh-1][Dw-1] == -1):
        print(-1)
    else:
        print(path[Dh-1][Dw-1])


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)

INF = 10**10


def main(input, print):
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    move2 = [(-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)]

    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    table = [input() for _ in range(H)]
    path = [[INF] * W for _ in range(H)]

    que = deque()
    path[Ch-1][Cw-1] = 0
    que.append((Ch-1, Cw-1, 0))
    while que:
        y, x, cnt = que.pop()

        for i, j in move:
            nx = x+i
            ny = y+j
            if ny < 0 or nx < 0 or ny >= H or nx >= W or table[ny][nx] == '#' or path[ny][nx] <= cnt:
                continue
            path[ny][nx] = cnt
            que.appendleft((ny, nx, cnt))

        for i, j in move2:
            nx = x+i
            ny = y+j
            if ny < 0 or nx < 0 or ny >= H or nx >= W or table[ny][nx] == '#' or path[ny][nx] <= cnt + 1:
                continue
            path[ny][nx] = cnt+1
            que.appendleft((ny, nx, cnt+1))

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


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)

INF = 10**10


def main(input, print):
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    move2 = [(-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)]

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

    que = deque()
    path[Ch-1][Cw-1] = 0
    que.append((Ch-1, Cw-1))
    while que:
        y, x = que.pop()
        cnt = path[y][x]

        for i, j in move:
            nx = x+i
            ny = y+j
            if ny < 0 or nx < 0 or ny >= H or nx >= W or table[ny][nx] == '#' or path[ny][nx] <= cnt:
                continue
            path[ny][nx] = cnt
            que.appendleft((ny, nx))

        for i, j in move2:
            nx = x+i
            ny = y+j
            if ny < 0 or nx < 0 or ny >= H or nx >= W or table[ny][nx] == '#' or path[ny][nx] <= cnt + 1:
                continue
            path[ny][nx] = cnt+1
            que.appendleft((ny, nx))

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


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)


def main(input, print):
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    move2 = [(-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)]

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

    que = deque()
    path[Ch-1][Cw-1] = 0
    que.append((Ch-1, Cw-1))
    while que:
        y, x = que.pop()
        cnt = path[y][x]

        for k in range(len(move)):
            i, j = move[k]
            nx = x+i
            ny = y+j
            if ny < 0 or nx < 0 or ny >= H or nx >= W:
                continue
            if table[ny][nx] == '#':
                continue
            if path[ny][nx] == -1 or path[ny][nx] > cnt:
                path[ny][nx] = cnt
                que.appendleft((ny, nx))

        for k in range(len(move2)):
            i, j = move2[k]
            nx = x+i
            ny = y+j
            if ny < 0 or nx < 0 or ny >= H or nx >= W:
                continue
            if table[ny][nx] == '#':
                continue
            if path[ny][nx] == -1 or path[ny][nx] > cnt+1:
                path[ny][nx] = cnt+1
                que.appendleft((ny, nx))
    if(path[Dh-1][Dw-1] == -1):
        print(-1)
    else:
        print(path[Dh-1][Dw-1])


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)


def main(input, print):
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    move2 = [(-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)]

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

    que = deque()
    path[Ch-1][Cw-1] = 0
    que.append((Ch-1, Cw-1))
    while que:
        h, w = que.pop()
        cnt = path[h][w]

        for k in range(len(move)):
            i, j = move[k]
            if h+i < 0 or w+j < 0 or h+i >= H or w+j >= W:
                continue
            if table[h+i][w+j] == '#':
                continue
            if path[h+i][w+j] == -1 or path[h+i][w+j] > cnt:
                path[h+i][w+j] = cnt
                que.appendleft((h+i, w+j))

        for k in range(len(move2)):
            i, j = move2[k]
            if h+i < 0 or w+j < 0 or h+i >= H or w+j >= W:
                continue
            if table[h+i][w+j] == '#':
                continue
            if path[h+i][w+j] == -1 or path[h+i][w+j] > cnt:
                path[h+i][w+j] = cnt+1
                que.append((h+i, w+j))
    if(path[Dh-1][Dw-1] == -1):
        print(-1)
    else:
        print(path[Dh-1][Dw-1])


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)


def main(input, print):
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    move2 = [(-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)]

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

    que = deque()
    table[Ch-1][Cw-1] = 0
    que.append((Ch-1, Cw-1))
    while que:
        h, w = que.pop()
        cnt = table[h][w]

        for k in range(len(move)):
            i, j = move[k]
            if h+i < 0 or w+j < 0 or h+i >= H or w+j >= W:
                continue
            if table[h+i][w+j] == '#':
                continue
            if table[h+i][w+j] == '.' or table[h+i][w+j] > cnt:
                table[h+i][w+j] = cnt
                que.appendleft((h+i, w+j))

        for k in range(len(move2)):
            i, j = move2[k]
            if h+i < 0 or w+j < 0 or h+i >= H or w+j >= W:
                continue
            if table[h+i][w+j] == '#':
                continue
            if table[h+i][w+j] == '.' or table[h+i][w+j] > cnt+1:
                table[h+i][w+j] = cnt+1
                que.append((h+i, w+j))
    if(table[Dh-1][Dw-1] == '.'):
        print(-1)
    else:
        print(table[Dh-1][Dw-1])


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Time Limit Exceeded

Solution code:
def is_valid(x,y,H,W):
    return x > -1 and y > -1 and x < W and y < H

def dfs(stack, vis_set):
    new_set = set()
    while len(stack) > 0:
        cur_y, cur_x = stack.pop()
        good_count = 0
        for i in range(4):
            new_y, new_x = cur_y + move_y[i], cur_x + move_x[i]
            if is_valid(new_x, new_y, H,W) and grid[new_y][new_x] == "." and (new_y, new_x):
                good_count += 1
                if (new_y, new_x) not in vis_set:
                    vis_set.add((new_y, new_x))
                    stack.append((new_y, new_x))
        if good_count != 4:
            new_set.add((cur_y, cur_x))
    
    return new_set
    
H,W = map(int, input().split(' '))
sy, sx = map(int, input().split(' '))
ey, ex = map(int, input().split(' '))
sy -= 1
sx -= 1
ey -= 1
ex -= 1

grid = []

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


move_x = [0,0,1,-1]
move_y = [1,-1,0,0]
tp_x = [0,0,2,-2,1,1,-1,-1,2,2,-2,-2,1,1,-1,-1,2,2,-2,2]
tp_y = [2,-2,0,0,1,-1,1,-1,2,-2,2,-2,2,-2,2,-2,1,-1,1,-1]

stack = [(sy,sx)]
vis_set = set([(sy,sx)])
prev_length = 1
cur_tp = 0
while True:
    tp_set = dfs(stack, vis_set)
    if (ey, ex) in vis_set:
        print(cur_tp)
        break
    
    for cur_y, cur_x in tp_set:
        for i in range(20):
            new_y, new_x = cur_y + tp_y[i], cur_x + tp_x[i]
            if is_valid(new_x, new_y, H,W) and grid[new_y][new_x] == "." and (new_y, new_x) not in vis_set:
                stack.append((new_y, new_x))
                vis_set.add((new_y, new_x))

    cur_tp += 1

    if (ey, ex) in vis_set:
        print(cur_tp)
        break
    
    if prev_length == len(vis_set):
        print(-1)
        break

    prev_length = len(vis_set)

Submission status: Time Limit Exceeded

Solution code:
def is_valid(x,y,H,W):
    return x > -1 and y > -1 and x < W and y < H

def dfs(stack, vis_set):
    new_set = set()
    while len(stack) > 0:
        cur_y, cur_x = stack.pop()
        new_set.add((cur_y, cur_x))
        for i in range(4):
            new_y, new_x = cur_y + move_y[i], cur_x + move_x[i]
            if is_valid(new_x, new_y, H,W) and grid[new_y][new_x] == "." and (new_y, new_x) not in vis_set:
                vis_set.add((new_y, new_x))
                stack.append((new_y, new_x))
    
    return new_set
    
H,W = map(int, input().split(' '))
sy, sx = map(int, input().split(' '))
ey, ex = map(int, input().split(' '))
sy -= 1
sx -= 1
ey -= 1
ex -= 1

grid = []

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


move_x = [0,0,1,-1]
move_y = [1,-1,0,0]
tp_x = [0,0,2,-2,1,1,-1,-1,2,2,-2,-2,1,1,-1,-1,2,2,-2,2]
tp_y = [2,-2,0,0,1,-1,1,-1,2,-2,2,-2,2,-2,2,-2,1,-1,1,-1]

stack = [(sy,sx)]
vis_set = set([(sy,sx)])
prev_length = 1
cur_tp = 0
while True:
    tp_set = dfs(stack, vis_set)
    if (ey, ex) in vis_set:
        print(cur_tp)
        break
    
    for cur_y, cur_x in tp_set:
        for i in range(20):
            new_y, new_x = cur_y + tp_y[i], cur_x + tp_x[i]
            if is_valid(new_x, new_y, H,W) and grid[new_y][new_x] == "." and (new_y, new_x) not in vis_set:
                stack.append((new_y, new_x))
                vis_set.add((new_y, new_x))

    cur_tp += 1

    if (ey, ex) in vis_set:
        print(cur_tp)
        break
    
    if prev_length == len(vis_set):
        print(-1)
        break

    prev_length = len(vis_set)

Submission status: Time Limit Exceeded

Solution code:
def is_valid(x,y,H,W):
    return x > -1 and y > -1 and x < W and y < H

def dfs(stack, vis_set):
    new_set = set()
    while len(stack) > 0:
        cur_y, cur_x = stack.pop()
        new_set.add((cur_y, cur_x))
        for i in range(4):
            new_y, new_x = cur_y + move_y[i], cur_x + move_x[i]
            if is_valid(new_x, new_y, H,W) and grid[new_y][new_x] == "." and (new_y, new_x) not in vis_set:
                vis_set.add((new_y, new_x))
                stack.append((new_y, new_x))
    
    return new_set
    
H,W = map(int, input().split(' '))
sy, sx = map(int, input().split(' '))
ey, ex = map(int, input().split(' '))
sy -= 1
sx -= 1
ey -= 1
ex -= 1

grid = []

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


move_x = [0,0,1,-1]
move_y = [1,-1,0,0]
tp_x = [0,0,2,-2,1,1,-1,-1,2,2,-2,-2,1,1,-1,-1,2,2,-2,2]
tp_y = [2,-2,0,0,1,-1,1,-1,2,-2,2,-2,2,-2,2,-2,1,-1,1,-1]

stack = [(sy,sx)]
vis_set = set([(sy,sx)])
prev_length = 1
cur_tp = 0
while True:
    tp_set = dfs(stack, vis_set)
    if (ey, ex) in vis_set:
        print(cur_tp)
        break
    
    new_stack_set = set()
    for cur_y, cur_x in tp_set:
        for i in range(20):
            new_y, new_x = cur_y + tp_y[i], cur_x + tp_x[i]
            if is_valid(new_x, new_y, H,W) and grid[new_y][new_x] == "." and (new_y, new_x) not in vis_set:
                new_stack_set.add((new_y, new_x))
                vis_set.add((new_y, new_x))

    if (ey, ex) in vis_set:
        print(cur_tp+1)
        break
    
    stack = list(new_stack_set)
    if prev_length == len(vis_set) and len(stack) == 0:
        print(-1)
        break

    prev_length = len(vis_set)
    cur_tp += 1

Submission status: Time Limit Exceeded

Solution code:

import queue

H, W = list(map(int, input().split()))
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S = (S[0] - 1, S[1] - 1)
G = (G[0] - 1, G[1] - 1)

maze = []
for i in range(H):
    maze.append(input())

MAX = 1000001
cost_list = [[MAX] * W for i in range(H)]


to_walk = queue.Queue()
to_warp = queue.Queue()

walk_directions = ((0, 1), (0, -1), (1, 0), [-1, 0])
warp_directions = ((-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2),
                   (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2))


def walk(z):
    h, w = z
    cost = cost_list[h][w]
    for [p, q] in walk_directions:
        if (0 <= h + p < H) and (0 <= w + q < W):
            if maze[h + p][w + q] == ".":
                if cost_list[h + p][w + q] > cost:
                    cost_list[h + p][w + q] = cost
                    to_walk.put((h + p, w + q))
            else:
                to_warp.put([h, w])


def warp(z):
    h, w = z
    cost = cost_list[h][w] + 1
    for [p, q] in warp_directions:
        if (0 <= h + p < H) and (0 <= w + q < W):
            if maze[h + p][w + q] == "." and cost_list[h + p][w + q] > cost:
                cost_list[h + p][w + q] = cost
                to_walk.put((h + p, w + q))


to_walk.put(S)
cost_list[S[0]][S[1]] = 0

while True:
    while not to_walk.empty():
        walk(to_walk.get())
    while not to_warp.empty():
        warp(to_warp.get())
    if to_walk.empty() and to_warp.empty():
        break

if cost_list[G[0]][G[1]] == MAX:
    print(-1)
else:
    print(cost_list[G[0]][G[1]])

Submission status: Time Limit Exceeded

Solution code:

import queue

H, W = list(map(int, input().split()))
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S = [S[0] - 1, S[1] - 1]
G = [G[0] - 1, G[1] - 1]

maze = []
for i in range(H):
    maze.append(input())

MAX = 1000001
cost_list = [[MAX] * W for i in range(H)]


to_walk = queue.Queue()
to_warp = queue.Queue()

warp_directions = ((-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2),
                   (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2))


def walk(z):
    h, w = z
    cost = cost_list[h][w]
    for [p, q] in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        if (0 <= h + p < H) and (0 <= w + q < W):
            if maze[h + p][w + q] == ".":
                if cost_list[h + p][w + q] > cost:
                    cost_list[h + p][w + q] = cost
                    to_walk.put([h + p, w + q])
            else:
                to_warp.put([h, w])


def warp(z):
    h, w = z
    cost = cost_list[h][w] + 1
    for [p, q] in warp_directions:
        if (0 <= h + p < H) and (0 <= w + q < W):
            if maze[h + p][w + q] == "." and cost_list[h + p][w + q] > cost:
                cost_list[h + p][w + q] = cost
                to_walk.put([h + p, w + q])


to_walk.put(S)
cost_list[S[0]][S[1]] = 0

while True:
    while not to_walk.empty():
        walk(to_walk.get())
    while not to_warp.empty():
        warp(to_warp.get())
    if to_walk.empty() and to_warp.empty():
        break

if cost_list[G[0]][G[1]] == MAX:
    print(-1)
else:
    print(cost_list[G[0]][G[1]])

Submission status: Time Limit Exceeded

Solution code:
import queue

H, W = list(map(int, input().split()))
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S = [S[0] - 1, S[1] - 1]
G = [G[0] - 1, G[1] - 1]

maze = []
for i in range(H):
    maze.append(input())

MAX = 1000001
cost_list = [[MAX] * W for i in range(H)]


to_walk = queue.Queue()
to_warp = queue.Queue()


def walk(z):
    h, w = z
    cost = cost_list[h][w]
    for [p, q] in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        if (0 <= h + p < H) and (0 <= w + q < W):
            if maze[h + p][w + q] == "." :
                if cost_list[h + p][w + q] > cost:
                    cost_list[h + p][w + q] = cost
                    to_walk.put([h + p, w + q])
            else:
                to_warp.put([h, w])


def warp(z):
    h, w = z
    cost = cost_list[h][w] + 1
    for [p, q] 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]]:
        if (0 <= h + p < H) and (0 <= w + q < W):
            if maze[h + p][w + q] == "." and cost_list[h + p][w + q] > cost:
                cost_list[h + p][w + q] = cost
                to_walk.put([h + p, w + q])


to_walk.put(S)
cost_list[S[0]][S[1]] = 0

while True:
    while not to_walk.empty():
        walk(to_walk.get())
    while not to_warp.empty():
        warp(to_warp.get())
    if to_walk.empty() and to_warp.empty():
        break

if cost_list[G[0]][G[1]] == MAX:
    print(-1)
else:
    print(cost_list[G[0]][G[1]])

Submission status: Time Limit Exceeded

Solution code:

import queue

H, W = list(map(int, input().split()))
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S = [S[0] - 1, S[1] - 1]
G = [G[0] - 1, G[1] - 1]

maze = []
for i in range(H):
    maze.append(input())

MAX = 1000001
cost_list = [[MAX] * W for i in range(H)]


to_walk = queue.Queue()
to_warp = queue.Queue()


def walk(z):
    h, w = z
    cost = cost_list[h][w]
    for [p, q] in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        if (0 <= h + p < H) and (0 <= w + q < W):
            if maze[h + p][w + q] == "." :
                if cost_list[h + p][w + q] > cost:
                    cost_list[h + p][w + q] = cost
                    to_walk.put([h + p, w + q])
            else:
                to_warp.put([h, w])


def warp(z):
    h, w = z
    cost = cost_list[h][w] + 1
    for [p, q] 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]]:
        if (0 <= h + p < H) and (0 <= w + q < W):
            if maze[h + p][w + q] == "." and cost_list[h + p][w + q] > cost:
                cost_list[h + p][w + q] = cost
                to_walk.put([h + p, w + q])


to_walk.put(S)
cost_list[S[0]][S[1]] = 0

while True:
    while not to_walk.empty():
        walk(to_walk.get())
    while not to_warp.empty():
        warp(to_warp.get())
    if to_walk.empty() and to_warp.empty():
        break

if cost_list[G[0]][G[1]] == MAX:
    print(-1)
else:
    print(cost_list[G[0]][G[1]])