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: Wrong Answer

Solution code:
from collections import deque
def bfs(sl, visited, sy, sx, gy, gx, h, w):
    q = deque([[sy,sx]])
    visited[sy][sx] = 0
    qn = deque([[sy,sx]])

    while q:
        while q:
            y, x = q.popleft()
            if [y, x] == [gy, gx]:
                return visited[gy][gx]
            for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                ny, nx = y+j, x+k
                if ny >= h or nx >= w or ny < 0 or nx < 0:
                    continue
                if sl[ny][nx] == '.' and visited[ny][nx] == -1:
                    visited[ny][nx] = visited[y][x]
                    q.append([ny,nx])
                    qn.append([ny,nx])

        while qn:
            y, x = qn.popleft()
            for j in range(-2,3):
                for k in range(-2,3):
                    ny, nx = y+j, x+k
                    if ny >= h or nx >= w or ny < 0 or nx < 0: continue
                    if sl[ny][nx] == '.' and visited[ny][nx] == -1:
                        visited[ny][nx] = visited[y][x] + 1
                        q.append([ny,nx])
    return -1


h, w = map(int, input().split()) 
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
sl = [list(input()) for _ in range(h)]
visited = [ [-1]*w for i in range(h)]
ans = bfs(sl,visited,ch-1,cw-1,dh-1,dw-1,h,w)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

def main():

    ##########################################
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        ・復元なし
        """

        #最短のpathをたす


        class Edge():
            #重み付き有向辺

            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost

        def __init__(self, V):
            #引数Vは頂点数
            self.inf=10**20
            self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
            self. _E = 0 #辺の数
            self._V = V #頂点数

        #proparty - 辺の数
        def E(self):
            return self._E

        #proparty - 頂点数
        def V(self):
            return self._V

        def add(self, _from, _to, _cost):
            #2頂点と辺のコストを追加
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1

        def add2(self, _from, _to, _cost):
            #2頂点と辺のコスト（無向）を追加
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2

        def shortest_path(self,s):#,g):
            #始点sから頂点iまでの最短経路長のリストを返す
            que = [] #priority queue
            d = [self.inf] * self.V()

            #prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
            #復元で使う

            d[s] = 0
            heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加

            while len(que)!=0:
                #キューに格納されてある中で一番コストが小さい頂点を取り出す
                cost,v = heapq.heappop(que)

                #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
                if d[v] < cost:
                    continue

                #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
                for i in range(len(self.G[v])):
                    e = self.G[v][i] #vのi個目の隣接辺
                    if d[e.to] > d[v] + e.cost:
                        d[e.to] = d[v] + e.cost #更新

                        #prev[e.to] = v
                        #復元で使う

                        heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加

            """#sからgまでの最短経路
            path = []
            pos = g #今いる場所，ゴールで初期化
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                #print("pos:",format(pos))
                pos = prev[pos]
            path.reverse()
            #print(path)"""

            return d#,path
    ########################
    mod=10**9+7
    H,W=MI()
    ch,cw=MI()
    dh,dw=MI()
    ch+=1
    cw+=1
    dh+=1
    dw+=1
    
    S=[]
    S.append(["#"]*(W+4))
    S.append(["#"]*(W+4))
    for i in range(H):
        s=["#"]*2 + list(input()) + ["#"]*2
        S.append(s)
    S.append(["#"]*(W+4))
    S.append(["#"]*(W+4))
    djk=Dijkstra((H+4)*(W+4))
    
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    dx2=[-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
    dy2=[-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
    
    for i in range(H+2):
        for j in range(W+2):
            if S[i][j]!="#":
                for k in range(4):
                    ii=i+dx[k]
                    jj=j+dy[k]
                    if S[ii][jj]!="#":
                        fro=i*(W+4)+j
                        to=ii*(W+4)+jj
                        djk.add2(fro,to,0)
                for k in range(20):
                    ii=i+dx2[k]
                    jj=j+dy2[k]
                    if S[ii][jj]!="#":
                        fro=i*(W+4)+j
                        to=ii*(W+4)+jj
                        djk.add2(fro,to,1)
                        
    s=ch*(W+4)+cw
    g=dh*(W+4)+dw
    D=djk.shortest_path(s)
    ans=D[g]
    if ans>=10**7:
        ans=-1
    print(ans)
                    
                

main()

Submission status: Time Limit Exceeded

Solution code:
from __future__ import print_function

from functools import reduce
from operator import mul
from collections import Counter
from collections import deque
from itertools import accumulate
from queue import Queue
from queue import PriorityQueue as pq
from heapq import heapreplace
from heapq import heapify
from heapq import heappushpop
from heapq import heappop
from heapq import heappush
import heapq
import time
import random
import bisect
import itertools
import collections
from fractions import Fraction
import fractions
import string
import math
import operator
import functools
import copy
import array
import re
import sys
sys.setrecursionlimit(500000)


import pprint

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


mod = 1000000007


def combinations_count_mod(n, r):
    r = min(r, n - r)
    numer = reduce(lambda x, y: x * y % mod, range(n, n - r, -1), 1)
    denom = pow(reduce(lambda x, y: x * y % mod, range(1, r + 1), 1), mod - 2, mod)
    return numer * denom % mod


def solve():
    pass


delta_u = [(1, 0), (0, 1), (-1, 0), (0, -1)]
# [(u, v) for u in range(-2, 3) for v in range(-2, 3)]
delta2_u = [(-1, -1), (-1, 1), (1, -1), (1, 1), (-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, 2), (0, -2), (0, 2), (1, -2), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]


def main():
    #
    H, W = map(int, input().strip().split())
    Ch, Cw = map(lambda x: int(x) -1 + 2, input().strip().split())
    Dh, Dw = map(lambda x: int(x) -1 + 2, input().strip().split())
    GRID = []
    ANS = []
    for i in range(H + 4):
        ANS.append([sys.maxsize for _ in range(W+4)])

    GRID.append("#" * (W+4))
    GRID.append("#" * (W+4))
    for i in range(H):
        S = "##" + input().strip() + "##"
        GRID.append(S)
    GRID.append("#" * (W+4))
    GRID.append("#" * (W+4))

    # eprint('GRID ',end=':\n')
    # pprint.pprint(GRID)
    # eprint('ANS ',end=':\n')
    # pprint.pprint(ANS)


    #
    PQ = pq()
    PQ.put((0, Ch, Cw))
    while not(PQ.empty()):
        distance, Uh, Uw = PQ.get()
        distance = -distance

        # ANS[Uh][Uw] の 「スコア」 の 「更新」
        if distance >= ANS[Uh][Uw]:
            continue
        ANS[Uh][Uw] = distance

        #
        for delta_h, delta_w in delta_u:
            new_distance = distance
            new_Uh = Uh + delta_h
            new_Uw = Uw + delta_w
            if GRID[new_Uh][new_Uw] == "#":    #
                continue
            if new_distance >= ANS[new_Uh][new_Uw]:  # 「新しい距離」 が，今までに記録していたその座標における「古い距離」 よりも大きくなってしまう場合，その新しい地点はキューに追加しない()
                continue
            PQ.put((-new_distance, new_Uh, new_Uw))

        for delta_h, delta_w in delta2_u:
            new_distance = distance + 1
            new_Uh = Uh + delta_h
            new_Uw = Uw + delta_w
            if GRID[new_Uh][new_Uw] == "#":    #
                continue
            if new_distance >= ANS[new_Uh][new_Uw]:  # 「新しい距離」 が，今までに記録していたその座標における「古い距離」 よりも大きくなってしまう場合，その新しい地点はキューに追加しない()
                continue
            PQ.put((-new_distance, new_Uh, new_Uw))

    if ANS[Dh][Dw] != sys.maxsize:
        print(ANS[Dh][Dw])
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import collections

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input()+'#') for _ in range(h)]+[['#']*(w+2)]
checked=[[False]*(w+1) for _ in range(h+1)]
checked[sy][sx]=True
q=collections.deque()
q.append((sy,sx))
ans=0
while 1:
  cur_pos=[]
  while len(q)!=0:
    y,x=q.popleft()
    cur_pos.append((y,x))
    for dy,dx in [[-1,0],[1,0],[0,-1],[0,1]]:
      if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and checked[y+dy][x+dx]==False:
        checked[y+dy][x+dx]=True
        q.append((y+dy,x+dx))
  if checked[gy][gx]==True:
    print(ans)
    exit()
  if len(cur_pos)==0:
    print(-1)
    exit()
  ans+=1
  for y,x in cur_pos:
    for dy in range(-2,3):
      for dx in range(-2,3):
        if dy==0 and dx==0:
          continue
        if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and checked[y+dy][x+dx]==False:
          checked[y+dy][x+dx]=True
          q.append((y+dy,x+dx))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

H, W = map(int, input().split())
xs, ys = map(int, input().split())
xt, yt = map(int, input().split())
xs -= 1
ys -= 1
xt -= 1
yt -= 1
G = [input() for _ in range(H)]

D_wk = [[1,0], [0,1], [-1,0], [0,-1]]
D_tl = 2

#cost = [[-1  for _ in range(W)] for _ in range(H)]

possible = set()
for i in range(H):
  for j in range(W):
    if G[i][j] == ".":
      possible.add(i * W + j)

# 01-BFS
def append_walk(c, x, y):
  for dx, dy in D_wk:
    if 0 <= x+dx <= H-1 and 0 <= y+dy <= W-1 and ((x+dx)*W+(y+dy)) in possible and ((x+dx)*W+(y+dy)) not in visited:
      task.appendleft([c, x+dx, y+dy])
def append_tele(c, x, y):
  for dx in range(-D_tl, D_tl+1):
    for dy in range(-D_tl, D_tl+1):
      if 0 <= x+dx <= H-1 and 0 <= y+dy <= W-1 and ((x+dx)*W+(y+dy)) in possible and ((x+dx)*W+(y+dy)) not in visited:
        task.append([c+1, x+dx, y+dy])

task = deque([[0, xs, ys]])
visited = set()
while task:
  while True:
    c, x, y = task.popleft()
    if x*W+y not in visited:
      break
    if not task:
      print(-1)
      sys.exit()    
  if x == xt and y == yt:
    print(c)
    #print(*cost, sep="\n")
    sys.exit()  
  visited.add(x*W+y)
  #cost[x][y] = c
  append_walk(c, x, y)
  append_tele(c, x, y)
  
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
c = list(map(lambda x: int(x)+1, input().split()))
d = list(map(lambda x: int(x)+1, input().split()))
s = ['#'*(w+4)]*2 + ['#'*2 + input() + '#'*2 for _ in range(h)] + ['#'*(w+4)]*2

ans = [[-1]*(w+4) for _ in range(h+4)]
for i in range(h+4):
    for j in range(w+4):
        if s[i][j] == '#':
            ans[i][j] = -2
ans[c[0]][c[1]] = 0

move1 = [(0, 1), (0, -1), (1, 0), (-1, 0)]
move2 = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if abs(i)+abs(j) > 1]

yet = deque([(c[0], c[1])])
done = deque()

while yet:
    y, x = yet.popleft()
    done.append((y, x))
    for dy, dx in move1:
        ydy, xdx = y+dy, x+dx
        if ans[ydy][xdx] == -1:
            yet.append((ydy, xdx))
            ans[ydy][xdx] = ans[y][x]

    if len(yet) == 0:
        while done:
            y, x = done.popleft()
            for dy, dx in move2:
                ydy, xdx = y+dy, x+dx
                if ans[ydy][xdx] == -1:
                    ans[ydy][xdx] = ans[y][x] + 1
                    yet.append((ydy, xdx))

print(ans[d[0]][d[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)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
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:  # 移動A
        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.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        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))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys
    readline = sys.stdin.buffer.readline

    h, w = map(int, readline().split())
    c = list(map(lambda x: int(x)+1, readline().split()))
    d = list(map(lambda x: int(x)+1, readline().split()))
    s = ['#'*(w+4)]*2 + ['#'*2 + readline().rstrip().decode('utf-8') + '#'*2 for _ in range(h)] + ['#'*(w+4)]*2

    t0 = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    t1 = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if abs(i)+abs(j) > 1]

    INF = float('inf')
    check = [[INF]*(w+4) for _ in range(h+4)]
    q = deque([(c[0], c[1], 0)])

    while q:
        y, x, b = q.pop()
        if y == d[0] and x == d[1]:
            print(b)
            exit()
        for dy, dx in t0:
            ydy, xdx = y+dy, x+dx
            if s[ydy][xdx] == '.' and b < check[ydy][xdx]:
                check[ydy][xdx] = b
                q.append((ydy, xdx, b))
        for dy, dx in t1:
            ydy, xdx = y+dy, x+dx
            if s[ydy][xdx] == '.' and b+1 < check[ydy][xdx]:
                check[ydy][xdx] = b+1
                q.appendleft((ydy, xdx, b+1))
    print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys
    readline = sys.stdin.buffer.readline

    h, w = map(int, readline().split())
    c = list(map(int, readline().split()))
    d = list(map(int, readline().split()))
    s = ['#'*(w+4)]*2 + ['#'*2 + readline().rstrip().decode('utf-8') + '#'*2 for _ in range(h)] + ['#'*(w+4)]*2

    c = [i-1+2 for i in c]
    d = [i-1+2 for i in d]

    t0 = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    t1 = []
    for i in range(-2, 3):
        for j in range(-2, 3):
            t1.append((i, j))
    for i in t0:
        t1.remove(i)
    t1.remove((0, 0))

    check = [[-1]*(w+4) for _ in range(h+4)]
    q = deque()
    q.appendleft((c[0], c[1], 0))

    while q:
        y, x, b = q.pop()
        if y == d[0] and x == d[1]:
            print(b)
            exit()
        if check[y][x] == -1:
            check[y][x] = b
            for dy, dx in t0:
                ydy, xdx = y+dy, x+dx
                if s[ydy][xdx] == '.' and check[ydy][xdx] == -1:
                    q.append((ydy, xdx, b))
            for dy, dx in t1:
                ydy, xdx = y+dy, x+dx
                if s[ydy][xdx] == '.' and check[ydy][xdx] == -1:
                    q.appendleft((ydy, xdx, b+1))
    print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
c = list(map(int, input().split()))
d = list(map(int, input().split()))
s = ['#'*(w+4)]*2 + ['#'*2 + input() + '#'*2 for _ in range(h)] + ['#'*(w+4)]*2

c = [i-1+2 for i in c]
d = [i-1+2 for i in d]

t0 = [(0, 1), (0, -1), (1, 0), (-1, 0)]
t1 = []
for i in range(-2, 3):
    for j in range(-2, 3):
        t1.append((i, j))
for i in t0:
    t1.remove(i)
t1.remove((0, 0))

check = [[-1]*(w+4) for _ in range(h+4)]
q = deque()
q.appendleft((c[0], c[1], 0))

while q:
    y, x, b = q.pop()
    if y == d[0] and x == d[1]:
        print(b)
        exit()
    if check[y][x] == -1:
        check[y][x] = b
        for dy, dx in t0:
            ydy, xdx = y+dy, x+dx
            if s[ydy][xdx] == '.' and check[ydy][xdx] == -1:
                q.append((ydy, xdx, b))
        for dy, dx in t1:
            ydy, xdx = y+dy, x+dx
            if s[ydy][xdx] == '.' and check[ydy][xdx] == -1:
                q.appendleft((ydy, xdx, b+1))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h , w = map(int, input().split())
start_y, start_x = map(int, input().split())
end_y, end_x = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
cost = [[float('inf') for i in range(w)] for j in range(h)]

def bfs():
    que = deque()
    que.append((start_x-1, start_y-1,0))
    finished = set()
    while que:
        x, y, c = que.popleft()
        finished.add((x,y))
        if not ((0 <= y < h) and (0 <= x < w)) :
            continue
        if grid[y][x] == '#':
            continue
        if cost[y][x] <= c:
            continue
        cost[y][x] = c
        for n_x, n_y in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
            if (n_x,n_y) not in finished:
                que.appendleft((n_x, n_y, c))
                finished.add((n_x, n_y))
        for i in range(-2,3):
            for j in range(-2,3):
                if (x+i,y+j) not in finished:
                    que.append((x+i,y+j,c+1))
bfs()
# print(cost)
if cost[end_y-1][end_x-1] == float('inf'):
    print(-1)
    exit()
print(cost[end_y-1][end_x-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h , w = map(int, input().split())
start_y, start_x = map(int, input().split())
end_y, end_x = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
cost = [[float('inf') for i in range(w)] for j in range(h)]

def bfs():
    que = deque()
    que.append((start_x-1, start_y-1,0))
    finished = set()
    while que:
        x, y, c = que.popleft()
        if (x, y) in finished:
            continue
        finished.add((x,y))
        if not ((0 <= y < h) and (0 <= x < w)) :
            continue
        if grid[y][x] == '#':
            continue
        if cost[y][x] <= c:
            continue
        cost[y][x] = c
        for n_x, n_y in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
            if (n_x,n_y) not in finished:
                que.appendleft((n_x, n_y, c))
        for i in range(-2,3):
            for j in range(-2,3):
                if (x+i,y+j) not in finished:
                    que.append((x+i,y+j,c+1))
bfs()
if cost[end_y-1][end_x-1] == float('inf'):
    print(-1)
    exit()
print(cost[end_y-1][end_x-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h , w = map(int, input().split())
start_y, start_x = map(int, input().split())
end_y, end_x = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
cost = [[float('inf') for i in range(w)] for j in range(h)]

def bfs():
    que = deque()
    que.append((start_x-1, start_y-1,0))
    finished = set()
    while que:
        x, y, c = que.popleft()
        finished.add((x,y))
        if not ((0 <= y < h) and (0 <= x < w)) :
            continue
        if grid[y][x] == '#':
            continue
        if cost[y][x] <= c:
            continue
        cost[y][x] = c
        for n_x, n_y in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
            if (n_x,n_y) not in finished:
                que.appendleft((n_x, n_y, c))
                finished.add((n_x,n_y))
        for i in range(-2,3):
            for j in range(-2,3):
                if (x+i,y+j) not in finished:
                    que.append((x+i,y+j,c+1))
                    finished.add((n_x,n_y))

bfs()
if cost[end_y-1][end_x-1] == float('inf'):
    print(-1)
    exit()
print(cost[end_y-1][end_x-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h , w = map(int, input().split())
start_y, start_x = map(int, input().split())
end_y, end_x = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
cost = [[float('inf') for i in range(w)] for j in range(h)]

def bfs():
    que = deque()
    que.append((start_x-1, start_y-1,0))
    finished = set()
    while que:
        x, y, c = que.popleft()
        finished.add((x,y))
        if not ((0 <= y < h) and (0 <= x < w)) :
            continue
        if grid[y][x] == '#':
            continue
        if cost[y][x] <= c:
            continue
        cost[y][x] = c
        for n_x, n_y in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
            if (n_x,n_y) not in finished:
                que.appendleft((n_x, n_y, c))
                finished.add((n_x,n_y))
        for i in range(-2,3):
            for j in range(-2,3):
                if (x+i,y+j) not in finished:
                    que.append((x+i,y+j,c+1))
                

bfs()
if cost[end_y-1][end_x-1] == float('inf'):
    print(-1)
    exit()
print(cost[end_y-1][end_x-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h , w = map(int, input().split())
start_y, start_x = map(int, input().split())
end_y, end_x = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
cost = [[float('inf') for i in range(w)] for j in range(h)]

def bfs():
    que = deque()
    que.append((start_x-1, start_y-1,0))
    finished = set()
    while que:
        x, y, c = que.popleft()
        finished.add((x,y))
        if not ((0 <= y < h) and (0 <= x < w)) :
            continue
        if grid[y][x] == '#':
            continue
        if cost[y][x] <= c:
            continue
        cost[y][x] = c
        for n_x, n_y in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
            if (n_x,n_y) not in finished:
                que.appendleft((n_x, n_y, c))
        for i in range(-2,3):
            for j in range(-2,3):
                if (x+i,y+j) not in finished:
                    que.append((x+i,y+j,c+1))
                

bfs()
if cost[end_y-1][end_x-1] == float('inf'):
    print(-1)
    exit()
print(cost[end_y-1][end_x-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h , w = map(int, input().split())
start_y, start_x = map(int, input().split())
end_y, end_x = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
cost = [[float('inf') for i in range(w)] for j in range(h)]

def bfs():
    que = deque()
    que.append((start_x-1, start_y-1,0))
    que_contents = set()
    que_contents.add((start_x-1, start_y-1))
    while que:
        x, y, c = que.popleft()
        if (x,y) in que_contents:
            que_contents.remove((x, y))
        if not ((0 <= y < h) and (0 <= x < w)) :
            continue
        if grid[y][x] == '#':
            continue
        if cost[y][x] <= c:
            continue
        cost[y][x] = c
        for n_x, n_y in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
            que.appendleft((n_x, n_y, c))
            que_contents.add((n_x, n_y))
        for i in range(-2,3):
            for j in range(-2,3):
                if (x+i, y+j) not in que_contents:
                    que.append((x+i,y+j,c+1))
                    que_contents.add((x+i, y+j))
                

bfs()
if cost[end_y-1][end_x-1] == float('inf'):
    print(-1)
    exit()
print(cost[end_y-1][end_x-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h , w = map(int, input().split())
start_y, start_x = map(int, input().split())
end_y, end_x = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
cost = [[float('inf') for i in range(w)] for j in range(h)]

def bfs():
    que = deque()
    que.append((start_x-1, start_y-1,0))
    que_contents = set()
    while que:
        x, y, c = que.popleft()
        if not ((0 <= y < h) and (0 <= x < w)) :
            continue
        if grid[y][x] == '#':
            continue
        if cost[y][x] <= c:
            continue
        cost[y][x] = c
        for n_x, n_y in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:
            que.appendleft((n_x, n_y, c))
        for i in range(-2,3):
            for j in range(-2,3):
                que.append((x+i,y+j,c+1))

bfs()
if cost[end_y-1][end_x-1] == float('inf'):
    print(-1)
    exit()
print(cost[end_y-1][end_x-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque

def main():
    h, w = map(int,input().split())
    h += 4
    w += 4
    C_h, C_w = map(int,input().split())
    C_h += 1
    C_w += 1
    D_h, D_w = map(int,input().split())
    D_h += 1
    D_w += 1
    S = ["#"*w for hh in range(h)]
    for hh in range(2, h-2):
        S[hh] = "##" + input() + "##"
    queue = deque([C_h*w + C_w])
    ans = [-1]*(h*w)
    ans[C_h*w + C_w] = 0
    visited = [False]*(h*w)
    visited[C_h*w + C_w] = True

    queue_0 = deque([C_h*w + C_w])
    while queue_0:
        node = queue_0.popleft()
        for xnode in (node - 1, node + 1, node - w, node + w):
            if S[xnode//w][xnode%w] == "." and not visited[xnode]:
                visited[xnode] = True
                ans[xnode] = 0
                queue_0.append(xnode)
                queue.append(xnode)
    while queue:
        node = queue.popleft()
        node_h = node//w
        node_w = node%w
        for xnode_h in (node_h - 2, node_h - 1, node_h, node_h + 1, node_h + 2):
            for xnode_w in (node_w - 2, node_w - 1, node_w, node_w + 1, node_w + 2):
                xnode = xnode_h*w + xnode_w
                if S[xnode_h][xnode_w] == "." and not visited[xnode]:
                    next_ans = ans[node] + 1
                    ans[xnode] = next_ans
                    queue.append(xnode)
                    visited[xnode] = True

                    queue_0 = deque([xnode])
                    while queue_0:
                        node2 = queue_0.popleft()
                        for xnode2 in (node2 - 1, node2 + 1, node2 - w, node2 + w):
                            if S[xnode2//w][xnode2%w] == "." and not visited[xnode2]:
                                visited[xnode2] = True
                                ans[xnode2] = next_ans
                                queue_0.append(xnode2)
                                queue.append(xnode2)

#    for i in range(h):
#        print(ans[w*i:w*(i+1)])
#    gnode = D_h*w + D_w
    print(ans[D_h*w + D_w])
        
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
        elif (0<=ny<h and 0<=nx<w) and G[ny][nx] != '#':
            if abs(dy)+abs(dx)<=1:
                G[ny][nx] = '#'
                D[ny][nx] = D[y][x]
                Q.append((ny, nx))
            elif D[ny][nx] == 10**6:
                D[ny][nx] = D[y][x]+1
                Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])