Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int, input().split())
c = tuple(map(int, input().split()))
d = tuple(map(int, input().split()))
m = ['#' for _ in range(h+2)]
m[0] += '#'*(w+1)
m[h+1] += '#'*(w+1)
que = deque()
que.append(c)
warp = [[10**9 for _ in range(w+1)] for _ in range(h+1)]
for i in range(1,h+1):  m[i] += input()+'#'
up = lambda x,y: 1 if 0<x-1 and m[x-1][y]=='.' else 0
down = lambda x,y: 1 if x+1<=h and m[x+1][y]=='.' else 0
right = lambda x,y: 1 if y+1<=w and m[x][y+1]=='.' else 0
left = lambda x,y: 1 if 0<y-1 and m[x][y-1]=='.' else 0

def jump(x,y,cost):
  deq = deque()
  for i in range(x-2,x+3):
    if i<=0 or h<i:  continue
    for j in range(y-2,y+3):
      if j<=0 or w<j:  continue
      if m[i][j] == '.' and warp[i][j]>cost+1:
        warp[i][j] = cost+1
        if (i,j) not in que:
          deq.append((i,j))
  return deq
  
warp[c[0]][c[1]] = 0
while que:
  q = que.popleft()
  row,col = q[0],q[1]
  cost = warp[row][col]
  if up(row,col) and warp[row-1][col]>cost:
    que.appendleft((row-1,col))
    warp[row-1][col] = cost
  if down(row,col) and warp[row+1][col]>cost:
    que.appendleft((row+1,col))
    warp[row+1][col] = cost
  if right(row,col) and warp[row][col+1]>cost:
    que.appendleft((row,col+1))
    warp[row][col+1] = cost
  if left(row,col) and warp[row][col-1]>cost:
    que.appendleft((row,col-1))
    warp[row][col-1] = cost
  que.extend(jump(row,col,cost))
if warp[d[0]][d[1]] != 10**9: print(warp[d[0]][d[1]])
else: print(-1)

Submission status: Time Limit Exceeded

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

H, W = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
dh, dw = list(map(int, input().split()))

ch -= 1
cw -= 1
dh -= 1
dw -= 1

S = [list((str(input()))) for i in range(H)]


def check(h, w):
    if h < 0 or h >= H:
        return False
    if w < 0 or w >= W:
        return False
    if S[h][w] == "#":
        return False
    return True


def main():

    map_ = [[10**10]*W for i in range(H)]
    # map_[ch][cw] = 0

    dq = deque([[ch, cw, 0]])

    while(len(dq) > 0):
        # print(dq)
        h, w, value = dq.popleft()
        map_value = map_[h][w]
        if map_value <= value:
            continue
        map_[h][w] = value

        for i in [-2, -1, 0, 1, 2]:
            for j in [-2, -1, 0, 1, 2]:
                if i == 0 and j == 0:
                    continue
                if abs(i)+abs(j) == 1:
                    if check(h+i, w+j):
                        # print(h+i, w+)
                        if map_[h+i][w+j] > value:
                            dq.appendleft([h+i, w+j, value])
                else:
                    if check(h+i, w+j):
                        if map_[h+i][w+j] > value+1:
                            dq.append([h+i, w+j, value+1])
    # for i in map_:
        # print(i)
    ans = map_[dh][dw]
    if ans == 10**10:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import deque
import numpy as np
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
check_set = set()
check_set.add(tuple([ch, cw, 0]))
d = deque()
d.appendleft([ch, cw, 0])
dist = np.full((h, w), float('inf'))
f_list = []
for i in range(h):
    f_list.append(input())
now_no = 0
while True:
    hh, ww, no = d.popleft()
    if dh == hh and dw == ww:
        print(no)
        break
    if dist[hh, ww] == float('inf') or dist[hh, ww] == now_no:
        if now_no != no:
            now_no += 1
        dist[hh, ww] = now_no
        for i in range(-2, 3):
            for j in range(-2, 3):
                if hh + i < 0 or h <= hh + i or ww + j < 0 or w <= ww + j or (i == 0 and j == 0):
                    continue
                if (i == -1 and j == 0) or (i == 1 and j == 0) or (i == 0 and j == -1) or (i == 0 and j == 1):
                    if tuple([hh + i, ww + j, now_no]) not in check_set and f_list[hh + i][ww + j] == "." and now_no < dist[hh + i, ww + j]:
                        dist[hh + i, ww + j] = now_no
                        check_set.add(tuple([hh + i, ww + j, now_no]))
                        d.appendleft([hh + i, ww + j, now_no])
                else:
                    if tuple([hh + i, ww + j, now_no + 1]) not in check_set and f_list[hh + i][ww + j] == "." and now_no < dist[hh + i, ww + j]:
                        check_set.add(tuple([hh + i, ww + j, now_no + 1]))
                        d.append([hh + i, ww + j, now_no + 1])
    if len(d) == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
import numpy as np
from collections import deque
H,W = map(int, input().rstrip().split())
CH,CW = map(int, input().rstrip().split())
DH,DW = map(int, input().rstrip().split())
[CH,CW,DH,DW] = [CH-1,CW-1,DH-1,DW-1]
S = np.array([list(input().rstrip()) for i in range(H)])
INF = 10 ** 9
Distance = np.ones((H,W))*INF
Distance[CH,CW] = 0
[nowH,nowW] = [CH,CW]
q = deque([])
q.append([nowH,nowW])
while len(q) != 0:
  [nowH,nowW] = q.popleft()
  if [nowH,nowW] == [DH,DW]:
    break
  for i in range(-1,2):
    for j in range(-1,2):
      if nowH+i < 0 or nowW+j < 0 or nowH+i >= H or nowW+j >= W:
        continue
      if S[nowH+i,nowW+j] != '.':
        continue
      if abs(i) + abs(j) != 1:
        continue
      if Distance[nowH,nowW] < Distance[nowH+i,nowW+j]:
        Distance[nowH+i,nowW+j] = Distance[nowH,nowW]
        if [nowH+i,nowW+j] in q:
          q.remove([nowH+i,nowW+j])
        q.appendleft([nowH+i,nowW+j])
  for i in range(-2,3):
    for j in range(-2,3):
      if nowH+i < 0 or nowW+j < 0 or nowH+i >= H or nowW+j >= W:
        continue
      if S[nowH+i,nowW+j] != '.':
        continue
      if abs(i) + abs(j) < 2:
        continue
      if Distance[nowH,nowW] + 1 < Distance[nowH+i,nowW+j]:
        Distance[nowH+i,nowW+j] = Distance[nowH,nowW] + 1
        q.append([nowH+i,nowW+j])
if Distance[DH,DW] == INF:
  print(-1)
else:
  print(int(Distance[DH,DW]))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import deque
import numpy as np
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
check_set = set()
check_set.add(tuple([ch, cw, 0]))
d = deque()
d.appendleft([ch, cw, 0])
dist = np.full((h, w), float('inf'))
f_list = []
for i in range(h):
    f_list.append(input())
now_no = 0
while True:
    hh, ww, no = d.popleft()
    if dh == hh and dw == ww:
        print(no)
        break
    if dist[hh, ww] == float('inf'):
        if now_no != no:
            now_no += 1
        dist[hh, ww] = now_no
        for i in range(-2, 3):
            for j in range(-2, 3):
                if hh + i < 0 or h <= hh + i or ww + j < 0 or w <= ww + j or (i == 0 and j == 0):
                    continue
                if (i == -1 and j == 0) or (i == 1 and j == 0) or (i == 0 and j == -1) or (i == 0 and j == 1):
                    if tuple([hh + i, ww + j, now_no]) not in check_set and f_list[hh + i][ww + j] == "." and now_no < dist[hh + i, ww + j]:
                        check_set.add(tuple([hh + i, ww + j, now_no]))
                        d.appendleft([hh + i, ww + j, now_no])
                else:
                    if tuple([hh + i, ww + j, now_no + 1]) not in check_set and f_list[hh + i][ww + j] == "." and now_no < dist[hh + i, ww + j]:
                        check_set.add(tuple([hh + i, ww + j, now_no + 1]))
                        d.append([hh + i, ww + j, now_no + 1])
    if len(d) == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
import numpy as np
from collections import deque
H,W = map(int, input().rstrip().split())
CH,CW = map(int, input().rstrip().split())
DH,DW = map(int, input().rstrip().split())
[CH,CW,DH,DW] = [CH-1,CW-1,DH-1,DW-1]
S = np.array([list(input().rstrip()) for i in range(H)])
INF = 10 ** 9
Distance = np.ones((H,W))*INF
Distance[CH,CW] = 0
[nowH,nowW] = [CH,CW]
q = deque([])
q.append([nowH,nowW])
while len(q) != 0:
  [nowH,nowW] = q.popleft()
  if [nowH,nowW] == [DH,DW]:
    break
  for i in range(-1,2):
    for j in range(-1,2):
      if nowH+i < 0 or nowW+j < 0 or nowH+i >= H or nowW+j >= W:
        continue
      if S[nowH+i,nowW+j] != '.':
        continue
      if abs(i) + abs(j) != 1:
        continue
      if Distance[nowH,nowW] < Distance[nowH+i,nowW+j]:
        Distance[nowH+i,nowW+j] = Distance[nowH,nowW]
        q.appendleft([nowH+i,nowW+j])
  for i in range(-2,3):
    for j in range(-2,3):
      if nowH+i < 0 or nowW+j < 0 or nowH+i >= H or nowW+j >= W:
        continue
      if S[nowH+i,nowW+j] != '.':
        continue
      if abs(i) + abs(j) < 2:
        continue
      if Distance[nowH,nowW] + 1 < Distance[nowH+i,nowW+j]:
        Distance[nowH+i,nowW+j] = Distance[nowH,nowW] + 1
        q.append([nowH+i,nowW+j])
if Distance[DH,DW] == INF:
  print(-1)
else:
  print(int(Distance[DH,DW]))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import deque
import numpy as np
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
check_set = set()
check_set.add(tuple([ch, cw, 0]))
d = deque()
d.appendleft([ch, cw, 0])
dist = np.full((h, w), float('inf'))
f_list = []
for i in range(h):
    f_list.append(input())
now_no = 0
while True:
    hh, ww, no = d.popleft()
    if dh == hh and dw == ww:
        print(no)
        break
    if dist[hh, ww] == float('inf'):
        if now_no != no:
            now_no += 1
        dist[hh, ww] = now_no
        for i in range(-2, 3):
            for j in range(-2, 3):
                if hh + i < 0 or h <= hh + i or ww + j < 0 or w <= ww + j or (i == 0 and j == 0):
                    continue
                if (i == -1 and j == 0) or (i == 1 and j == 0) or (i == 0 and j == -1) or (i == 0 and j == 1):
                    if tuple([hh + i, ww + j, now_no]) not in check_set and f_list[hh + i][ww + j] == ".":
                        check_set.add(tuple([hh + i, ww + j, now_no]))
                        d.appendleft([hh + i, ww + j, now_no])
                else:
                    if tuple([hh + i, ww + j, now_no + 1]) not in check_set and f_list[hh + i][ww + j] == ".":
                        check_set.add(tuple([hh + i, ww + j, now_no + 1]))
                        d.append([hh + i, ww + j, now_no + 1])
    if len(d) == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import deque
import numpy as np
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
check_set = set()
check_set.add(tuple([ch, cw, 0]))
d = deque()
d.appendleft([ch, cw, 0])
dist = np.full((h, w), float('inf'))
dist[ch, cw] = 0
f_list = []
for i in range(h):
    f_list.append(input())
now_no = 0
while True:
    hh, ww, no = d.popleft()
    if dh == hh and dw == ww:
        print(no)
        break
    if now_no != no:
        now_no += 1
    dist[hh, ww] = now_no
    for i in range(-2, 3):
        for j in range(-2, 3):
            if hh + i < 0 or h <= hh + i or ww + j < 0 or w <= ww + j or (i == 0 and j == 0):
                continue
            if (i == -1 and j == 0) or (i == 1 and j == 0) or (i == 0 and j == -1) or (i == 0 and j == 1):
                if tuple([hh + i, ww + j, now_no]) not in check_set and f_list[hh + i][ww + j] == "." and now_no < dist[hh + i, ww + j]:
                    check_set.add(tuple([hh + i, ww + j, now_no]))
                    d.appendleft([hh + i, ww + j, now_no])
            else:
                if tuple([hh + i, ww + j, now_no + 1]) not in check_set and f_list[hh + i][ww + j] == "." and now_no < dist[hh + i, ww + j]:
                    check_set.add(tuple([hh + i, ww + j, now_no + 1]))
                    d.append([hh + i, ww + j, now_no + 1])
    if len(d) == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

grid = [list(input()) for s in range(H)]
search = [[float('inf')] * W for _ in range(H)]

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

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

while dq:
    r, c, cur_cost = dq.popleft()

    for x, y in direction:
        r_new = r + x
        c_new = c + y

        if r_new < 0 or r_new >= H or c_new < 0 or c_new >= W or \
                search[r_new][c_new] <= cur_cost or grid[r_new][c_new] == '#':
            continue

        dq.appendleft((r_new, c_new, cur_cost))
        search[r_new][c_new] = cur_cost

    for x in range(-2, 3):
        r_new = r + x
        if r_new < 0 or r_new >= H:
            continue

        for y in range(-2, 3):
            c_new = c + y

            if c_new < 0 or c_new >= W or search[r_new][c_new] <= cur_cost + 1 or grid[r_new][c_new] == '#':
                continue

            dq.append((r_new, c_new, cur_cost + 1))
            search[r_new][c_new] = cur_cost + 1


if search[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(search[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import deque
import numpy as np
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
check_set = set()
check_set.add(tuple([ch, cw, 0]))
d = deque()
d.appendleft([ch, cw, 0])
dist = np.full((h, w), float('inf'))
dist[ch, cw] = 0
f_list = []
for i in range(h):
    f_list.append(input())
now_no = 0
while True:
    hh, ww, no = d.popleft()
    if dh == hh and dw == ww:
        print(no)
        break
    if now_no != no:
        now_no += 1
    dist[hh, ww] = now_no
    for i in range(-2, 3):
        for j in range(-2, 3):
            if hh + i < 0 or h <= hh + i or ww + j < 0 or w <= ww + j or (i == 0 and j == 0):
                continue
            if (i == -1 and j == 0) or (i == 1 and j == 0) or (i == 0 and j == -1) or (i == 0 and j == 1):
                if tuple([hh + i, ww + j, now_no]) not in check_set and f_list[hh + i][ww + j] == ".":
                    check_set.add(tuple([hh + i, ww + j, now_no]))
                    d.appendleft([hh + i, ww + j, now_no])
            else:
                if tuple([hh + i, ww + j, now_no + 1]) not in check_set and f_list[hh + i][ww + j] == ".":
                    check_set.add(tuple([hh + i, ww + j, now_no + 1]))
                    d.append([hh + i, ww + j, now_no + 1])
    if len(d) == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
h,w=map(int,input().split())
c=[int(i)-1 for i in input().split()]
d=[int(i)-1 for i in input().split()]
s=[input() for i in range(h)]
inf=100000000
dp=[[-1 if s[i][j]=="#" else inf for j in range(w)] for i in range(h)]
dp[c[0]][c[1]]=0
now=deque([[c[0],c[1]]])
#グリッド上のbfsはfor文で
def bfs():
    global h,w,s,dp,now
    while len(now):
        i,j=now.popleft()
        for k,l in [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]:
            if 0<=k<h and 0<=l<w:
                if dp[k][l]!=-1:
                    if dp[k][l]>dp[i][j]:
                        dp[k][l]=dp[i][j]
                        now.appendleft([k,l])
        for k in range(i-2,i+3):
            for l in range(j-2,j+3):
                if 0<=k<h and 0<=l<w:
                    if dp[k][l]!=-1:
                        if dp[k][l]>dp[i][j]+1:
                            dp[k][l]=dp[i][j]+1
                            now.append([k,l])
bfs()
print(dp[d[0]][d[1]] if dp[d[0]][d[1]]!=inf else -1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
ch, cw = map(int, input().split())
eh, ew = map(int, input().split())

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

from heapq import heappop, heappush
q = []
heappush(q, (0, ch-1, cw-1))
e = {(ch-1, cw-1): 0}

d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while q:
    t, hh, ww = heappop(q)
    if hh == (eh - 1) and ww == (ew - 1):
        print(t)
        exit(0)

    for dh, dw in d:
        h, w = hh+dh, ww+dw
        if h < 0 or h > H-1 or w < 0 or w > W-1:
            continue
        if s[h][w] == '#':
            continue
        if (h, w) in e and e[(h, w)] <= t:
            continue
        e[(h, w)] = t
        heappush(q, (t, h, w))
    for dh in range(-2,3):
        for dw in range(-2,3):
            h, w = hh + dh, ww + dw
            if h < 0 or h > H - 1 or w < 0 or w > W - 1:
                continue
            if s[h][w] == '#':
                continue
            if (h, w) in e and e[(h, w)] <= t+1:
                continue
            e[(h, w)] = t+1
            heappush(q, (t+1, h, w))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math


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

    d = deque()
    d.append([Ch - 1, Cw - 1])

    cost = [[math.inf for _ in range(W)] for _ in range(H)]
    cost[Ch - 1][Cw - 1] = 0

    while d:
        r, c = d.popleft()

        for dr, dc in [[-1, 0], [1, 0], [0, -1], [0, 1]]:  # 上下左右
            nr = r + dr
            nc = c + dc

            if not 0 <= nr < H:
                continue
            if not 0 <= nc < W:
                continue
            if S[nr][nc] == "#":
                continue
            if cost[nr][nc] <= cost[r][c]:
                continue

            cost[nr][nc] = cost[r][c]
            d.appendleft([nr, nc])

        for dr in range(-2, 3, 1):  # ワープ
            for dc in range(-2, 3, 1):
                if dr == 0 and dc == 0:
                    continue

                nr = r + dr
                nc = c + dc

                if not 0 <= nr < H:
                    continue
                if not 0 <= nc < W:
                    continue
                if S[nr][nc] == "#":
                    continue
                if cost[nr][nc] <= cost[r][c] + 1:
                    continue

                cost[nr][nc] = cost[r][c] + 1
                d.append([nr, nc])

    if cost[Dh - 1][Dw - 1] == math.inf:
        ans = -1
    else:
        ans = cost[Dh - 1][Dw - 1]

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math


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

    d = deque()
    d.append([Ch - 1, Cw - 1])

    cost = [[math.inf for _ in range(W)] for _ in range(H)]
    cost[Ch - 1][Cw - 1] = 0

    while d:
        r, c = d.popleft()

        for dr, dc in [[-1, 0], [1, 0], [0, -1], [0, 1]]:  # 上下左右
            nr = r + dr
            nc = c + dc
            if 0 <= nr < H and 0 <= nc < W and S[nr][nc] == "." and cost[nr][nc] > cost[r][c]:
                cost[nr][nc] = cost[r][c]
                d.appendleft([nr, nc])

        for dr in range(-2, 3, 1):  # ワープ
            for dc in range(-2, 3, 1):
                if dr == 0 and dc == 0:
                    continue
                nr = r + dr
                nc = c + dc
                if 0 <= nr < H and 0 <= nc < W and S[nr][nc] == "." and cost[nr][nc] > cost[r][c] + 1:
                    cost[nr][nc] = cost[r][c] + 1
                    d.append([nr, nc])

    if cost[Dh - 1][Dw - 1] == math.inf:
        ans = -1
    else:
        ans = cost[Dh - 1][Dw - 1]

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 問題：https://atcoder.jp/contests/abc176/tasks/abc176_d

import numpy as np

h, w = map(int, input().strip().split())
cx, cy = map(int, input().strip().split())
dx, dy = map(int, input().strip().split())
cx -= 1
cy -= 1
dx -= 1
dy -= 1
qx = [cx]
qy = [cy]

s = [input() for _ in range(h)]
reached = np.zeros((h, w))
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            reached[i][j] = 1
res = 0

while qx:
    pre_qx = []
    pre_qy = []
    while qx:
        x = qx.pop(0)
        y = qy.pop(0)
        if reached[x][y] == 1:
            continue
        pre_qx.append(x)
        pre_qy.append(y)
        reached[x][y] = 1
        if x > 0 and reached[x-1][y] == 0:
            qx.append(x-1)
            qy.append(y)
        if x < h-1 and reached[x+1][y] == 0:
            qx.append(x+1)
            qy.append(y)
        if y > 0 and reached[x][y-1] == 0:
            qx.append(x)
            qy.append(y-1)
        if y < w-1 and reached[x][y+1] == 0:
            qx.append(x)
            qy.append(y+1)
    if reached[dx][dy] == 1:
        break
    res += 1
    while pre_qx:
        x = pre_qx.pop(0)
        y = pre_qy.pop(0)
        lx = max(x-2, 0)
        rx = min(x+3, h)
        ly = max(y-2, 0)
        ry = min(y+3, w)
        for i in range(lx, rx):
            for j in range(ly, ry):
                if reached[i][j] == 0:
                    qx.append(i)
                    qy.append(j)

if reached[dx][dy] == 0:
    res = -1

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

INF = pow(10, 10)
seen = [[INF] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append((Ch, Cw))

while q:
    th, tw = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= seen[th][tw]:
            continue
        seen[nh][nw] = seen[th][tw]
        q.append((nh, nw))
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            if dh2 == 0 and dw2 == 0:
                continue
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= seen[th][tw] + 1:
                continue
            seen[nh][nw] = seen[th][tw] + 1
            q.append((nh, nw))

if seen[Dh][Dw] is INF:
    print(-1)
else:
    print(seen[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
INF = 10**9
from heapq import heappop,heappush
H,W = (int(i) for i in input().split())
Ch,Cw = (int(i)-1 for i in input().split())
Dh,Dw = (int(i)-1 for i in input().split())
S = [input() for i in range(H)]

dist = [[INF]*W for _ in range(H)]
dist[Ch][Cw]= 0
que = [(0,Ch*W+Cw)]
while(que):
    u_dist,u = heappop(que)
    uh,uw = u//W,u%W
    if dist[uh][uw] < u_dist:
        continue
    for dh in range(-2,3):
        for dw in range(-2,3):
            nh = uh + dh
            nw = uw + dw
            if nh<0 or H <= nh or nw < 0 or W <= nw:
                continue
            if S[nh][nw]=="#":
                continue
            cost = 0 if abs(dh)+abs(dw)<=1 else 1
            if dist[nh][nw] > dist[uh][uw] + cost:
                dist[nh][nw] = dist[uh][uw] + cost
                heappush(que,(dist[nh][nw],nh*W+nw))
if dist[Dh][Dw] == INF:
    print(-1)
else:
    print(dist[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

INF = pow(10, 10)
seen = [[INF] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw, 0])

while q:
    th, tw, t = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= t:
            continue
        seen[nh][nw] = t
        q.append([nh, nw, t])
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            if dh2 == 0 and dw2 == 0:
                continue
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= t + 1:
                continue
            seen[nh][nw] = t + 1
            q.append([nh, nw, t + 1])

if seen[Dh][Dw] is INF:
    print(-1)
else:
    print(seen[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
# 問題：https://atcoder.jp/contests/abc176/tasks/abc176_d

h, w = map(int, input().strip().split())
cx, cy = map(int, input().strip().split())
dx, dy = map(int, input().strip().split())
cx -= 1
cy -= 1
dx -= 1
dy -= 1
s = [input() for _ in range(h)]
reached = [[] for _ in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            reached[i].append(0)
        if s[i][j] == '#':
            reached[i].append(1)
res = 0
qx = [cx]
qy = [cy]

while qx:
    pre_qx = []
    pre_qy = []
    while qx:
        x = qx.pop(0)
        y = qy.pop(0)
        if reached[x][y] == 1:
            continue
        pre_qx.append(x)
        pre_qy.append(y)
        reached[x][y] = 1
        if x > 0 and reached[x-1][y] == 0:
            qx.append(x-1)
            qy.append(y)
            reached[x-1][y] = 2
        if x < h-1 and reached[x+1][y] == 0:
            qx.append(x+1)
            qy.append(y)
            reached[x+1][y] = 2
        if y > 0 and reached[x][y-1] == 0:
            qx.append(x)
            qy.append(y-1)
            reached[x][y-1] = 2
        if y < w-1 and reached[x][y+1] == 0:
            qx.append(x)
            qy.append(y+1)
            reached[x][y+1] = 2
    if reached[dx][dy] == 1:
        break
    res += 1
    while pre_qx:
        x = pre_qx.pop(0)
        y = pre_qy.pop(0)
        lx = max(x-2, 0)
        rx = min(x+3, h)
        ly = max(y-2, 0)
        ry = min(y+3, w)
        for i in range(lx, rx):
            for j in range(ly, ry):
                if reached[i][j] == 0:
                    qx.append(i)
                    qy.append(j)
                    reached[i][j] = 2

if reached[dx][dy] == 0:
    res = -1

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

INF = pow(10, 10)
seen = [[INF] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw, 0])

while q:
    th, tw, t = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= t:
            continue
        seen[nh][nw] = t
        q.append([nh, nw, t])
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            if dh2 == 0 and dw2 == 0:
                continue
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= t + 1:
                continue
            seen[nh][nw] = t + 1
            q.append([nh, nw, t + 1])

if seen[Dh][Dw] is INF:
    print(-1)
else:
    print(seen[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

INF = pow(10, 10)
seen = [[INF] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw, 0])

while q:
    th, tw, t = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1:
            continue
        if S[nh][nw] == '#':
            continue
        if seen[nh][nw] <= t:
            continue
        seen[nh][nw] = t
        q.append([nh, nw, t])
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            if dh2 == 0 and dw2 == 0:
                continue
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1:
                continue
            if S[nh][nw] == '#':
                continue
            if seen[nh][nw] <= t + 1:
                continue
            seen[nh][nw] = t + 1
            q.append([nh, nw, t + 1])

if seen[Dh][Dw] is INF:
    print(-1)
else:
    print(seen[Dh][Dw])