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 l():
    return [int(x) for x in input().split()]
def main():
    H,W=l()
    ch,cw=l()
    dh,dw=l()
    ch-=1
    cw-=1
    dw-=1
    dh-=1
    s=[[-2 if x=='#' else -1 for x in list(input())] for _ in range(H)]
    pad1=[-2,-2]
    pad2=[[-2]*(W+4)]*2
    s=pad2+[pad1+x+pad1 for x in s]+pad2
    move1=[(-1,0),(1,0),(0,-1),(0,1)]
    move2=list(set([(i,j) for i in range(-2,3) for j in range(-2,3)])-set(move1)-set([(0,0)]))
    q1=[(0,ch+2,cw+2)]
    q2=[]
    s[ch+2][cw+2]=0
    def mark(c,h,w):
        #if 0<=h<H and 0<=w<W and s[h][w]==-1:
        if s[h][w]==-1:
            s[h][w]=c
            q1.append((c,h,w))
    while q1:
        #print(q1)
        c,h,w=q1.pop()
        for i,j in move1:
            mark(c,h+i,w+j)
        q2.append((c+1,h,w))
        if not q1:
            for c,h,w in q2:
                for i,j in move2:
                    mark(c,h+i,w+j)
            q2=[]
    ans=s[dh+2][dw+2]
    if ans>=0:
        print(ans)
    else:
        print(-1)
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def solve(h, w, ch, cw, dh, dw, s_list):

    s_arr = [[False] * (w + 4) for _ in range(h + 4)]
    for i, s in enumerate(s_list):
        for j in range(w):
            if s[j] == ".":
                s_arr[i + 2][j + 2] = True

    done_arr = [[False] * (w + 4) for _ in range(h + 4)]

    # heap
    queue = deque()
    res = -1
    # start
    queue.append((0, ch + 1, cw + 1))
    # main
    while len(queue):
        d, i, j = queue.popleft()
        if done_arr[i][j]:
            continue
        done_arr[i][j] = True
        # print(d, i, j)
        if i == dh + 1 and j == dw + 1:
            res = d
            # print("done")
            break
        for i_ in range(i - 2, i + 3):
            for j_ in range(j - 2, j + 3):
                if not done_arr[i_][j_] and s_arr[i_][j_]:
                    diff = abs(i_ - i) + abs(j_ - j)
                    if diff > 1:
                        queue.append((d + 1, i_, j_))
                    else:
                        queue.appendleft((d, i_, j_))
    # print(res)
    return res


def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    s_list = []
    for i in range(h):
        s = input()
        s_list.append(s)
    res = solve(h, w, ch, cw, dh, dw, s_list)
    print(res)


def test():
    assert solve(4, 4, 1, 1, 4, 4, ["..#.", "..#.", ".#..", ".#.."]) == 1
    assert solve(4, 4, 1, 4, 4, 1, [".##.", "####", "####", ".##."]) == -1
    assert solve(4, 4, 2, 2, 3, 3, ["....", "....", "....", "...."]) == 0
    assert solve(4, 5, 1, 2, 2, 5, ["#.###", "####.", "#..##", "#..##"]) == 2


def test_large():
    assert solve(1000, 1000, 1, 1, 1000, 1000, ["." * 1000 for _ in range(1000)]) == 0


if __name__ == "__main__":
    test()
    # test_large()
    main()

Submission status: Time Limit Exceeded

Solution code:
def l():
    return [int(x) for x in input().split()]
def main():
    H,W=l()
    ch,cw=l()
    dh,dw=l()
    ch-=1
    cw-=1
    dw-=1
    dh-=1
    s=[[-2 if x=='#' else -1 for x in list(input())] for _ in range(H)]
    move1=[(-1,0),(1,0),(0,-1),(0,1)]
    move2=list(set([(i,j) for i in range(-2,3) for j in range(-2,3)])-set(move1)-set([(0,0)]))
    q1=[(0,ch,cw)]
    q2=[]
    def mark(c,h,w):
        if 0<=h<H and 0<=w<W and s[h][w]==-1:
            s[h][w]=c
            q1.append((c,h,w))
    while q1:
        c,h,w=q1.pop()
        mark(c,h,w)
        for i,j in move1:
            mark(c,h+i,w+j)
        q2.append((c+1,h,w))
        if not q1:
            for c,h,w in q2:
                for i,j in move2:
                    mark(c,h+i,w+j)
            q2.clear()
    ans=s[dh][dw]
    if ans>=0:
        print(ans)
    else:
        print(-1)
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W = map(int,input().split())
c_h, c_w = map(int,input().split())
d_h, d_w = map(int,input().split())

c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1

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

# print(s)

q = deque()
q.append((c_h,c_w))

INF = 1e9
# マス目に入る数字を入れる配列
# 最初はINFで初期化
dist = [[INF for _ in range(W)] for __ in range(H)]

dist[c_h][c_w] = 0
# (右、上、左、下)
dh = (0,1,0,-1)
dw = (1,0,-1,0)

while(len(q) > 0):
    # dequeの一番左を取り出す。
    now = q.popleft()
    now_h,now_w = now

    d = dist[now_h][now_w]

    # 今のマスの上下左右で動けるか確認する
    for di in range(4):
        next_h = now_h + dh[di]
        next_w = now_w + dw[di]

        if (next_h<0 or next_h>=H or next_w<0 or next_w>=W): continue
        if (s[next_h][next_w] == '#'): continue
        if dist[next_h][next_w] <= d: continue

        # 隣り合う動けるマスには同じ数字を記入
        dist[next_h][next_w] = d

        # dequeに前から入れる
        q.appendleft((next_h,next_w))

    # 魔法を使う場合
    for ew in range(-2,3):
        for eh in range(-2,3):
            next_h = eh + now_h
            next_w = ew + now_w

            if (next_h<0 or next_h>=H or next_w<0 or next_w>=W): continue
            if (s[next_h][next_w] == '#'): continue
            if dist[next_h][next_w] <= d+1: continue

            dist[next_h][next_w] = d+1
            q.append((next_h,next_w))

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

# print(dist)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
move_q = deque()
move_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while move_q:
    while move_q:
        # 移動AでBFS
        x, y = move_q.pop()
        for dx, dy in zip(dx_list, dy_list):
            nx, ny = x + dx, y + dy
            if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                continue
            # if scores[ny][nx] == float('inf'):
            if scores[ny][nx] > scores[y][x]:
                scores[ny][nx] = scores[y][x]
                move_q.appendleft([nx, ny])

        # 移動bで動けるマスをmodeA_qに格納
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                    continue
                # if scores[ny][nx] == float('inf'):
                if scores[ny][nx] > scores[y][x]:
                    scores[ny][nx] = scores[y][x] + 1
                    move_q.append([nx, ny])


# print(*scores,sep='\n')
if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W = map(int, input().split())

    y, x = map(int, input().split())
    start = (x-1, y-1)

    y, x = map(int, input().split())
    goal = (x-1, y-1)

    dist_table = [[-1 if c =='.' else -2 for c in input()] for i in range(H)]

    sx, sy = start
    dist_table[sy][sx] = 0

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

    queue1 = [start]
    queue2 = []

    while queue1:
        now_x, now_y = queue1.pop()
        queue2.append((now_x, now_y))
        dist = dist_table[now_y][now_x]
        for dx, dy in move1:
            tx, ty = now_x + dx, now_y + dy
            if tx < 0 or W <= tx or ty < 0 or H <= ty:
                continue
            if dist_table[ty][tx] == -1:
                dist_table[ty][tx] = dist
                queue1.append((tx, ty))
        if len(queue1) == 0:
            while queue2:
                now_x, now_y = queue2.pop()
                dist = dist_table[now_y][now_x]
                for dx, dy in move2:
                    tx, ty = now_x + dx, now_y + dy
                    if tx < 0 or W <= tx or ty < 0 or H <= ty:
                        continue
                    if dist_table[ty][tx] == -1:
                        dist_table[ty][tx] = dist + 1
                        queue1.append((tx, ty))
    gx, gy = goal
    print(dist_table[gy][gx])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W = map(int, input().split())

    y, x = map(int, input().split())
    start = (x-1, y-1)

    y, x = map(int, input().split())
    goal = (x-1, y-1)

    dist_table = [[-1 if c =='.' else -2 for c in input()] for i in range(H)]

    sx, sy = start
    dist_table[sy][sx] = 0

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

    queue1 = [start]
    queue2 = []

    while queue1:
        now_x, now_y = queue1.pop()
        if (now_x, now_y) == goal:
            break
        queue2.append((now_x, now_y))
        dist = dist_table[now_y][now_x]
        for dx, dy in move1:
            tx, ty = now_x + dx, now_y + dy
            if tx < 0 or W <= tx or ty < 0 or H <= ty:
                continue
            if dist_table[ty][tx] == -1:
                dist_table[ty][tx] = dist
                queue1.append((tx, ty))
        if len(queue1) == 0:
            while queue2:
                now_x, now_y = queue2.pop()
                dist = dist_table[now_y][now_x]
                for dx, dy in move2:
                    tx, ty = now_x + dx, now_y + dy
                    if tx < 0 or W <= tx or ty < 0 or H <= ty:
                        continue
                    if dist_table[ty][tx] == -1:
                        dist_table[ty][tx] = dist + 1
                        queue1.append((tx, ty))
    gx, gy = goal
    print(dist_table[gy][gx])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W = map(int, input().split())

    y, x = map(int, input().split())
    start = (x-1, y-1)

    y, x = map(int, input().split())
    goal = (x-1, y-1)

    field = [[c for c in input()] for i in range(H)]
    dist_table = [[-1] * W for i in range(H)]
    for y in range(H):
        for x in range(W):
            if field[y][x] == '#':
                dist_table[y][x] = -2

    sx, sy = start
    dist_table[sy][sx] = 0

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

    queue1 = [start]
    queue2 = []

    while queue1:
        now_x, now_y = queue1.pop()
        if (now_x, now_y) == goal:
            break
        queue2.append((now_x, now_y))
        dist = dist_table[now_y][now_x]
        for dx, dy in move1:
            tx, ty = now_x + dx, now_y + dy
            if tx < 0 or W <= tx or ty < 0 or H <= ty:
                continue
            if dist_table[ty][tx] == -1:
                dist_table[ty][tx] = dist
                queue1.append((tx, ty))
        if len(queue1) == 0:
            while queue2:
                now_x, now_y = queue2.pop()
                dist = dist_table[now_y][now_x]
                for dx, dy in move2:
                    tx, ty = now_x + dx, now_y + dy
                    if tx < 0 or W <= tx or ty < 0 or H <= ty:
                        continue
                    if dist_table[ty][tx] == -1:
                        dist_table[ty][tx] = dist + 1
                        queue1.append((tx, ty))
    gx, gy = goal
    print(dist_table[gy][gx])

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())
maze = [input() for i in range(H)]

queue = []
queue.append([Ch-1, Cw-1, 0])
inf = float("inf")
table = [[inf] * W for i in range(H)]
table[Ch-1][Cw-1] = 0
walk_move = [[-1, 0], [0, -1], [1, 0], [0, 1]]
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i, j])

while queue:
  x, y, cost = queue.pop(0)
  for i,j in walk_move:
    dx = x+i
    dy = y+j
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost:
      queue.insert(0, [dx, dy, cost])
      table[dx][dy] = cost
  for k,l in magic_move:
    dx = x+k
    dy = y+l
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost+1:
      queue.insert(0, [dx, dy, cost+1])
      table[dx][dy] = cost+1

ans = table[Dh-1][Dw-1]
if ans == inf:
  print("-1")
else:
  print(table[Dh-1][Dw-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import *

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

walk_move = [[-1, 0], [0, -1], [0, 1], [1, 0]]
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i ,j])
inf = float("inf")
table = [[inf for i in range(W)] for i in range(H)]
table[Ch-1][Cw-1] = 0
queue = [[Ch-1, Cw-1, 0]]

def main():
  while queue:
    x, y, cost = heappop(queue)
    for i, j in walk_move:
      dx = x+i
      dy = y+j
      if 0 <= dx <= H-1 and 0 <= dy <= W-1:
        if maze[dx][dy] == "." and table[dx][dy] > cost:
          table[dx][dy] = cost
          heappush(queue, [dx, dy, cost])
    for k, l in magic_move:
      dx = x+k
      dy = y+l
      if 0 <= dx <= H-1 and 0 <= dy <= W-1:
        if maze[dx][dy] == "." and table[dx][dy] > cost+1:
          table[dx][dy] = cost+1
          heappush(queue, [dx, dy, cost+1])
  return table[Dh-1][Dw-1]
        
ans = main()
if ans == inf:
  print("-1")
else:
  print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
from heapq import *
from numba import jit

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = np.array([input() for i in range(H)])

walk_move = [[-1, 0], [0, -1], [0, 1], [1, 0]]
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i ,j])
inf = float("inf")
table = np.array([[inf for i in range(W)] for i in range(H)])
table[Ch-1, Cw-1] = 0
queue = [(Ch-1, Cw-1, 0)]

@jit
def main():
  while queue:
    x, y, cost = heappop(queue)
    for i, j in walk_move:
      dx = x+i
      dy = y+j
      if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost:
        table[dx][dy] = cost
        heappush(queue, (dx, dy, cost))
    for k, l in magic_move:
      dx = x+k
      dy = y+l
      if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost+1:
        table[dx][dy] = cost+1
        heappush(queue, (dx, dy, cost+1))
  return table[Dh-1][Dw-1]
        
ans = main()
if ans == inf:
  print("-1")
else:
  print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
dh=DH-1
dw=DW-1
S=[[x=='#' for x in list(input())] for _ in range(H)]
q=deque([(0,CH-1,CW-1)])
checked=set()
def check(h,w,c,e):
    if h<0 or h>=H or w<0 or w>=W:
        return
    if S[h][w]:
        return
    if e==0:
        q.append((c,h,w))
    else:
        q.appendleft((c+e,h,w))

def main():
    while q:
        c,h,w=q.pop()
        if h==dh and w==dw:
            return c
        key=(h,w)
        if key in checked:
            continue
        checked.add(key)
        # walk
        check(h-1,w-0,c,0)
        check(h-0,w-1,c,0)
        check(h+1,w+0,c,0)
        check(h+0,w+1,c,0)
        # warp
        check(h,w-2,c,1)
        check(h,w+2,c,1)
        check(h-2,w,c,1)
        check(h+2,w,c,1)
        for i in [-2,-1,1,2]:
            for j in [-2,-1,1,2]:
                check(h+i,w+j,c,1)
    return -1
print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W = map(int, input().split())

    y, x = map(int, input().split())
    start = (x-1, y-1)

    y, x = map(int, input().split())
    goal = (x-1, y-1)

    field = [[c for c in input()] for i in range(H)]
    dist_table = [[-1] * W for i in range(H)]
    sx, sy = start
    dist_table[sy][sx] = 0

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

    queue1 = [start]
    queue2 = []

    while queue1:
        now_x, now_y = queue1.pop()
        if (now_x, now_y) == goal:
            break
        queue2.append((now_x, now_y))
        dist = dist_table[now_y][now_x]
        for dx, dy in move1:
            tx, ty = now_x + dx, now_y + dy
            if 0 <= tx < W and 0 <= ty < H and field[ty][tx] == '.':
                if dist_table[ty][tx] == -1:
                    dist_table[ty][tx] = dist
                    queue1.append((tx, ty))
        if len(queue1) == 0:
            while queue2:
                now_x, now_y = queue2.pop()
                dist = dist_table[now_y][now_x]
                for dx, dy in move2:
                    tx, ty = now_x + dx, now_y + dy
                    if 0 <= tx < W and 0 <= ty < H and field[ty][tx] == '.':
                        if dist_table[ty][tx] == -1:
                            dist_table[ty][tx] = dist + 1
                            queue1.append((tx, ty))
    gx, gy = goal
    print(dist_table[gy][gx])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())

y, x = map(int, input().split())
start = (x-1, y-1)

y, x = map(int, input().split())
goal = (x-1, y-1)

field = [[c for c in input()] for i in range(H)]
dist_table = [[-1] * W for i in range(H)]
sx, sy = start
dist_table[sy][sx] = 0

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

queue1 = [start]
queue2 = []

while queue1:
    now_x, now_y = queue1.pop()
    if (now_x, now_y) == goal:
        break
    queue2.append((now_x, now_y))
    dist = dist_table[now_y][now_x]
    for dx, dy in move1:
        tx, ty = now_x + dx, now_y + dy
        if 0 <= tx < W and 0 <= ty < H and field[ty][tx] == '.':
            if dist_table[ty][tx] == -1:
                dist_table[ty][tx] = dist
                queue1.append((tx, ty))
    if len(queue1) == 0:
        while queue2:
            now_x, now_y = queue2.pop()
            dist = dist_table[now_y][now_x]
            for dx, dy in move2:
                tx, ty = now_x + dx, now_y + dy
                if 0 <= tx < W and 0 <= ty < H and field[ty][tx] == '.':
                    if dist_table[ty][tx] == -1:
                        dist_table[ty][tx] = dist + 1
                        queue1.append((tx, ty))
gx, gy = goal
print(dist_table[gy][gx])

Submission status: Time Limit Exceeded

Solution code:
import heapq
l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
dh=DH-1
dw=DW-1
S=[[x=='#' for x in list(input())] for _ in range(H)]
q=[(0,0,CH-1,CW-1)]
heapq.heapify(q)
checked=set()
def check(h,w,c):
    if h<0 or h>=H or w<0 or w>=W:
        return
    if S[h][w]:
        return
    p=(abs(dh-h),abs(dw-w))
    heapq.heappush(q,(c,p,h,w))
    return True

def main():
    while q:
        c,_,h,w=heapq.heappop(q)
        if h==dh and w==dw:
            return c
        key=(h,w)
        if key in checked:
            continue
        checked.add(key)
        # walk
        check(h-1,w-0,c)
        check(h-0,w-1,c)
        check(h+1,w+0,c)
        check(h+0,w+1,c)
        # warp
        check(h,w-2,c+1)
        check(h,w+2,c+1)
        check(h-2,w,c+1)
        check(h+2,w,c+1)
        for i in [-2,-1,1,2]:
            for j in [-2,-1,1,2]:
                check(h+i,w+j,c+1)
    return -1
print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
(h,w),(ch,cw),(dh,dw)=eval('map(int,input().split()),'*3)
ss=[list(map(str, input())) for _ in range(h)]
q = deque([(ch-1,cw-1,0)])
while q:
  j,i,c=q.popleft()
  if ss[j][i]=='.':
    ss[j][i]=c
  for s in range(-2,3):
    for t in range(-2,3):
      if 0<=j+t<h and 0<=i+s<w and ss[j+t][i+s]=='.':
        if abs(t)+abs(s)==1:
          q.appendleft((j+t,i+s,c))
        elif abs(t)+abs(s)>=2:
          q.append((j+t,i+s,c+1))
if ss[dh-1][dw-1] == '.':
    print(-1)
else:
    print(ss[dh-1][dw-1])

Submission status: Time Limit Exceeded

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

from collections import deque

H, W = map(int,input().split())
sth, stw = map(int,input().split())
glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
direc5 = set([])
for i in range(-2,3):
    for j in range(-2,3):
        direc5.add((i, j))
direc5 = direc5 - direc
direc5 = direc5 - {(0,0)}

def bfs(pnxt):
    next_q = deque([])
    for h, w in pnxt:
        next_q.append((h,w))
        seen[h][w] = 0
    nxt = set([])
    while len(next_q)!=0:
        h, w = next_q.popleft()
        if h == glh and w == glw:
            print(ret)
            exit()
        for dh, dw in direc:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF:
                next_q.append((hs, ws))
                seen[hs][ws] = 0
        for dh, dw in direc5:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF and not (hs, ws) in nxt:
                nxt.add((hs, ws))
    return nxt

ret = 0
nxt_st = set([])
nxt_st.add((sth, stw))
while len(nxt_st)>0:
    nxt_st = bfs(nxt_st)
    ret += 1
print(-1)

Submission status: Time Limit Exceeded

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

from collections import deque

H, W = map(int,input().split())
sth, stw = map(int,input().split())
glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
direc5 = set([])
for i in range(-2,3):
    for j in range(-2,3):
        direc5.add((i, j))
direc5 = direc5 - direc
direc5 = direc5 - {(0,0)}
nxt_st = set([])

def bfs(pnxt):
    next_q = deque([])
    for hw in pnxt:
        next_q.append(hw)
    nxt = set([])
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h,w = next_q.popleft()
        if h == glh and w == glw:
            print(ret)
            exit()
        seen[h][w] = 0
        for dh, dw in direc:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF:
                next_q.append((hs, ws))
                seen[hs][ws] = 0
        for dh, dw in direc5:
            hs, ws = h + dh, w + dw
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='.' and seen[hs][ws]==INF:
                nxt.add((hs, ws))

    return nxt

ret = -1
nxt_st.add((sth, stw))
while len(nxt_st)>0:
    ret += 1
    nxt_st = bfs(nxt_st)
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x)-1, input().split())
dh, dw = map(lambda x: int(x)-1, input().split())
maze = [input() for _ in range(h)]

INF = 10**12
path = [[INF] * w for _ in range(h)] #ここに各マスの移動コストを記録する

walk = [(1,0), (0,1), (-1,0), (0,-1)] #ワープしない移動
warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)] + walk] #ワープするときの移動

q = deque()
path[ch][cw] = 0
q.append((ch, cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and path[nx][ny] > s:
            path[nx][ny] = s
            q.append((nx, ny, s))
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and path[nx][ny] > s+1:
            path[nx][ny] = s+1
            q.append((nx, ny, s+1))

ans = path[dh][dw] if path[dh][dw] < INF else -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x)-1, input().split())
dh, dw = map(lambda x: int(x)-1, input().split())
maze = [input() for _ in range(h)]

INF = float('inf')
path = [[INF] * w for _ in range(h)] #ここに各マスの移動コストを記録する

walk = [(1,0), (0,1), (-1,0), (0,-1)] #ワープしない移動
warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)] + walk] #ワープするときの移動

q = deque()
path[ch][cw] = 0
q.append((ch, cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and path[nx][ny] > s:
            path[nx][ny] = s
            q.append((nx, ny, s))
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and path[nx][ny] > s+1:
            path[nx][ny] = s+1
            q.append((nx, ny, s+1))

ans = path[dh][dw] if path[dh][dw] < INF else -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
dh=DH-1
dw=DW-1
S=[[x=='#' for x in list(input())] for _ in range(H)]
q=[(0,0,CH-1,CW-1)]
heapq.heapify(q)
checked=set()
def check(h,w,c):
    if h<0 or h>=H or w<0 or w>=W:
        return
    if S[h][w]:
        return
    p=(abs(dh-h),abs(dw-w))
    heapq.heappush(q,(c,p,h,w))

def main():
    while q:
        c,_,h,w=heapq.heappop(q)
        if h==dh and w==dw:
            return c
        key=(h,w)
        if key in checked:
            continue
        checked.add(key)
        # walk
        check(h-1,w-0,c)
        check(h-0,w-1,c)
        check(h+1,w+0,c)
        check(h+0,w+1,c)
        # warp
        check(h-1,w-1,c+1)
        check(h-1,w+1,c+1)
        check(h+1,w-1,c+1)
        check(h+1,w+1,c+1)
        for i in [-2,+2]:
            for j in range(-2,3):
                check(h+i,w+j,c+1)
                check(h+j,w+i,c+1)
    return -1
print(main())

Submission status: Time Limit Exceeded

Solution code:
import heapq
l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
dh=DH-1
dw=DW-1
S=[[x=='#' for x in list(input())] for _ in range(H)]
q=[(0,0,CH-1,CW-1)]
heapq.heapify(q)
checked=set()
def check(h,w,c):
    if h<0 or h>=H or w<0 or w>=W:
        return
    if S[h][w]:
        return
    p=(abs(dh-h),abs(dw-w))
    heapq.heappush(q,(c,p,h,w))

def main():
    while q:
        c,_,h,w=heapq.heappop(q)
        if h==dh and w==dw:
            return c
        key=(h,w)
        if key in checked:
            continue
        checked.add(key)
        # walk
        check(h-1,w-0,c)
        check(h-0,w-1,c)
        check(h+1,w+0,c)
        check(h+0,w+1,c)
        # warp
        check(h-1,w-1,c+1)
        check(h-1,w+1,c+1)
        check(h+1,w-1,c+1)
        check(h+1,w+1,c+1)
        for i in [-2,+2]:
            for j in range(-2,3):
                check(h+i,w+j,c+1)
                check(h+j,w+i,c+1)
    return -1
print(main())

Submission status: Time Limit Exceeded

Solution code:
import heapq
l=lambda:[int(x) for x in input().split()]
H,W=l()
CH,CW=l()
DH,DW=l()
S=[[x=='#' for x in list(input())] for _ in range(H)]
q=[(0,CH-1,CW-1)]
heapq.heapify(q)
checked=set()
def check(h,w,c):
    if h<0 or h>=H or w<0 or w>=W:
        return
    if S[h][w]:
        return
    heapq.heappush(q,(c,h,w))

def main():
    dh=DH-1
    dw=DW-1
    while q:
        c,h,w=heapq.heappop(q)
        if h==dh and w==dw:
            return c
        key=(h,w)
        if key in checked:
            continue
        checked.add(key)
        # walk
        check(h-1,w-0,c)
        check(h-0,w-1,c)
        check(h+1,w+0,c)
        check(h+0,w+1,c)
        # warp
        check(h-1,w-1,c+1)
        check(h-1,w+1,c+1)
        check(h+1,w-1,c+1)
        check(h+1,w+1,c+1)
        for i in [-2,+2]:
            for j in range(-2,3):
                check(h+i,w+j,c+1)
                check(h+j,w+i,c+1)
    return -1
print(main())