Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

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

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

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

1

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

Note that he cannot walk diagonally.

Sample Input 2

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

Sample Output 2

-1

He cannot move from there.

Sample Input 3

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

Sample Output 3

0

No use of magic is needed.

Sample Input 4

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

Sample Output 4

2



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


Sample output:
1

Submission status: Time Limit Exceeded

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

import sys
import pprint
from collections import deque


sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	h, w = map(int, sys.stdin.readline().split())
	ch, cw = map(int, sys.stdin.readline().split())
	dh, dw = map(int, sys.stdin.readline().split())
	s = [sys.stdin.readline().rstrip() for i in [0]*h]
	graph = [[[] for i in [0]*w] for j in [0]*h]
	
	def getMaze(x, y):
		if not (0 <= x < w and 0 <= y < h):
			return -1
		return s[y][x]

	for y in range(h):
		for x in range(w):
			if s[y][x] == "#":
				continue
			for i in range(-2, 2+1):
				for j in range(-2, 2+1):
					if (i, j) == (0, 0):
						continue
					if getMaze(x + i, y + j) == ".":
						if (i, j) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
							graph[y][x].append((x + i, y + j, 0))
						else:
							graph[y][x].append((x + i, y + j, 1))


	# log.print(graph)
	stack = deque([(cw-1, ch-1)])
	dist = [[float("inf")]*w for i in range(h)]
	while len(stack) != 0:
		x, y = stack.popleft()
		log.print(x, y, dist[y][x])
		if dist[y][x] == float("inf"):
			dist[y][x] = 0
		d = dist[y][x]
		nexts = graph[y][x]
		for next in nexts:
			nx, ny, cost = next
			if dist[ny][nx] > d + cost:
				dist[ny][nx] = d + cost
				if cost == 1:
					stack.append((nx, ny))
				else:
					stack.appendleft((nx, ny))
	log.print(dist)
	if dist[dh-1][dw-1] == float("inf"):
		print(-1)
	else:
		print(dist[dh-1][dw-1])
	
	


main()

Submission status: Time Limit Exceeded

Solution code:
from queue import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
inf = 10**10

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

li = [["" for i in range(w)]for j in range(h)]
for i in range(h):
    s = input()
    for j in range(w):
        li[i][j] = s[j]

que = deque()

mx = []
my = []

for i in range(-2,3):
    for j in range(-2,3):
        if i == 0 and j == 0:
            continue
        mx.append(i)
        my.append(j)

lin = [[inf for i in range(w)]for j in range(h)]
lin[ch][cw] = 0#ここをスタートの座標に変えること
que.append((ch,cw))#ここもスタートの座標に変えること

def main():
    while que:
        k = que.popleft()
        x = k[0]
        y = k[1]
        se = set()#被りがないかの確認

        for i,j in zip(mx,my):
            nx = x + i
            ny = y + j
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            elif li[nx][ny] == "#":
                continue
            else:
                if [i,j] in [[-1,0],[1,0],[0,-1],[0,1]]:
                    if lin[nx][ny] > lin[x][y]:
                        que.appendleft((nx,ny))
                        se.add((nx,ny))
                        lin[nx][ny] = lin[x][y]# 直接行ける
                else:
                    if lin[nx][ny] > lin[x][y]+1:
                        if (nx,ny) not in se:
                            que.append((nx,ny))
                            lin[nx][ny] = lin[x][y]+1# 魔法の力で行く

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
import sys
import os
from operator import mul
from collections import deque


sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353    

H,W = LI()
C = LI()
D = LI()
maze = [list(_S()) for i in range(H)]

def bfs():
    ans = -1
    # すべての点を INF で初期化
    d = [[float("inf")] * W for i in range(H)]

    
    sx = C[0]-1
    sy = C[1]-1
    gx = D[0]-1
    gy = D[1]-1

    # スタート地点をキューに入れ、ワープ数を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    que2 = deque([])
    que2.append((sx, sy))

    while que: 
        while que:
            p = que.popleft()
            que2.append(p)
            # 取り出してきた状態がゴールなら探索をやめる
            if p[0] == gx and p[1] == gy:
                ans = d[p[0]][p[1]]
                break
            # 移動4方向をループ
            # 移動4方向のベクトル
            dx = [1, 0, -1, 0]
            dy = [0, 1, 0, -1]

            for i in range(4):
                # 移動した後の点を (nx, ny) とする
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]

                # 移動が可能かの判定とすでに訪れたことがあるかの判定
                # d[nx][ny] != INF なら訪れたことがある
                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                    # 移動できるならキューに入れ、その点のワープ回数を p までのワープ回数で確定する
                    que.append((nx, ny))
                    que2.append((nx, ny))
                    d[nx][ny] = d[p[0]][p[1]]
        # print('after que: ',d)
        dx = [-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0, 1, 1,  1,  1, 2, 2, 2,  2, 2]
        dy = [-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, 2, 1, -1, -2, 2, 1, 0, -1, -2]
        while que2:
            # キューの先頭を取り出す
            p = que2.popleft()
            for i in range(20):
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]
                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                    # 移動できるならキューに入れ、その点のワープ回数を p からのワープ回数 +1 で確定する
                    que.append((nx, ny))
                    d[nx][ny] = d[p[0]][p[1]]+1  
        # print('after que2: ',d)  
    return ans

print(bfs())

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
A = 10**12
B = 10**6
d = [INF] * (h*w)

nex = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
            continue
        else:
            nex.append((i,j))

T = ((-1,0), (1,0), (0,1), (0,-1))

q = [(ch-1)*A + (cw-1)*B + 0]
for x in q:
    curh = (x // A)
    x -= curh * A
    curw = (x // B)
    cnt = x - curw * B

    if d[curh * w + curw] <= cnt: continue
    else:
        d[curh * w + curw] = cnt

    for dh, dw in T:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            q.append(nh*A + nw*B + cnt)

    for dh, dw in nex:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            q.append(nh*A + nw*B + cnt+1)

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])

Submission status: Time Limit Exceeded

Solution code:
import sys, math
import numpy as np

# input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


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


uf = UnionFind(H*W)
for i in range(H):
    for j in range(W):
        if S_[i][j] == '#':
            uf.parents[W*i+j] = math.inf
            continue
        if i != H-1 and S_[i + 1][j] == '.':
            uf.union(W*i + j, W*(i+1) + j)
        if j != W-1 and S_[i][j+1] == '.':
            uf.union(W*i + j, W*i + j + 1)

groupidx = {k: v for v, k in enumerate(uf.roots())}
S = np.zeros((H, W), dtype=int)
for i in range(H):
    for j in range(W):
        if S_[i][j] == '#':
            S[i][j] = -1
        else:
            S[i][j] = groupidx[uf.find(W*i+j)]


groups = list(range(len(uf.roots())))
can_reach = [[False]*len(groups) for _ in range(len(groups))]
for i in range(H):
    for j in range(W):
        if S[i][j] != -1:
            continue
        g = set(S[max(0, i-1):i+2, max(0, j-1):j+2].flatten())
        if -1 in g:
            g.remove(-1)
        for k in g:
            for l in g:
                can_reach[k][l] = True
can_reach_ = {}
for i in range(len(groups)):
    can_reach_[i] = [j for j, k in enumerate(can_reach[i]) if k]
ans = 0
s = S[Ch-1][Cw-1]
g = S[Dh-1][Dw-1]
if s==g:
    print(0)
    sys.exit()

reached = [s]
searched = [False]*len(groups)
ans = 0
while len(reached)>0:
    new_reached = []
    ans += 1
    for p in reached:
        searched[p] = True
    for p in reached:
        for k in can_reach_[p]:
            if k == g:
                print(ans)
                sys.exit()
            if not searched[k]:
                new_reached.append(k)
    reached = list(set(new_reached))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
 
dx = [-1,0,1,0]
dy = [0,-1,0,1]
 
def bfs(ch,cw):
    q = []#queue.Queue()
    S[ch][cw] = 0
    heapq.heappush(q,(S[ch][cw],[ch,cw]))
    while q:
        p = heapq.heappop(q)[1]
        if p[0]==dh and p[1]==dw:
          break
        
        for i in range(4):
            next_p = [p[0]+dx[i],p[1]+dy[i]]
            if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                continue
            if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]:
                S[next_p[0]][next_p[1]] = S[p[0]][p[1]]
                heapq.heappush(q,(S[next_p[0]][next_p[1]],next_p))
                
                
        for i in range(-2,3):
            for j in range(-2,3):
                if (i == 0 and j == 0) or (i==-1 and j==0)or(i==1 and j==0)or(i==0 and j==-1)or (i==0 and j==1):
                    continue
                next_p = [p[0]+i,p[1]+j]
                if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                    continue
                if S[next_p[0]][next_p[1]] > S[p[0]][p[1]]+1:
                    S[next_p[0]][next_p[1]] = S[p[0]][p[1]]+1
                    heapq.heappush(q,(S[next_p[0]][next_p[1]],next_p))
                    
            
    return 
        
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 = [list(input()) for _ in range(h)]
 
for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            S[i][j] = float('inf')
        else:
            S[i][j] = -1
 
 
bfs(ch,cw)
if S[dh][dw] != float('inf'):
    print(S[dh][dw])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
from numba import jit

h,w = map(int,input().rstrip().split())
sy,sx = map(int,input().rstrip().split())
gy,gx = map(int,input().rstrip().split())
a = [list(input().rstrip())for _ in range(h)]

sx -= 1
sy -= 1
gx -= 1
gy -= 1

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

@jit
def bfs():
    d = [[float("inf")]*w for _ in range(h)]
    q = deque([])
    q.append((sx,sy))
    d[sy][sx] = 0 #warp回数
    goal = False
    local_area = deque([])

    while q:
        p = q.popleft()
        local_area.append((p[0],p[1]))
        if p[0] == gx and p[1] == gy:
            goal = True
            break

        for i in range(4):
            nx = p[0]+dx[i]
            ny = p[1]+dy[i]
            if 0<=nx<w and 0<=ny<h and a[ny][nx] != "#" and d[ny][nx] == float("inf"):
                q.append((nx,ny))
                d[ny][nx] = d[p[1]][p[0]]
        if len(q) == 0 and goal == False:
            while local_area:
                p = local_area.popleft()
                for i in range(-2,3):
                    for j in range(-2,3):
                        nx = p[0]+i 
                        ny = p[1]+j
                        if 0<=nx<w and 0<=ny<h and a[ny][nx] != "#" and d[ny][nx] == float("inf"):
                            q.append((nx,ny))
                            d[ny][nx] = d[p[1]][p[0]] + 1                        

    if goal == False:
        return -1
    else:
        return d[gy][gx]
        
print(bfs())

Submission status: Time Limit Exceeded

Solution code:
from queue import deque

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
inf = 10**10

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

li = [["" for i in range(w)]for j in range(h)]
for i in range(h):
    s = input()
    for j in range(w):
        li[i][j] = s[j]

que = deque()

mx = []
my = []

for i in range(-2,3):
    for j in range(-2,3):
        if i == 0 and j == 0:
            continue
        mx.append(i)
        my.append(j)

lin = [[inf for i in range(w)]for j in range(h)]
lin[ch][cw] = 0#ここをスタートの座標に変えること
que.append((ch,cw))#ここもスタートの座標に変えること

while que:
    k = que.popleft()
    x = k[0]
    y = k[1]
    se = set()#被りがないかの確認

    for i,j in zip(mx,my):
        nx = x + i
        ny = y + j
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        elif li[nx][ny] == "#":
            continue
        else:
            if [i,j] in [[-1,0],[1,0],[0,-1],[0,1]]:
                if lin[nx][ny] > lin[x][y]:
                    que.appendleft((nx,ny))
                    se.add((nx,ny))
                    lin[nx][ny] = lin[x][y]# 直接行ける
            else:
                if lin[nx][ny] > lin[x][y]+1:
                    if (nx,ny) not in se:
                        que.append((nx,ny))
                        lin[nx][ny] = lin[x][y]+1# 魔法の力で行く

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math
 
def explore(C, D):
    queue = deque([(C[0]-1, C[1]-1)])
    maze_visited[C[0]-1][C[1]-1] = 0
    while queue:
        y, x = queue.popleft()
        mv_cur = maze_visited[y][x]
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            n_x, n_y = x + i, y + j
            if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                mv_n = maze_visited[n_y][n_x]
                if mv_n > mv_cur:
                    if S[n_y][n_x] == '.':
                        maze_visited[n_y][n_x] = mv_cur
                        queue.append((n_y, n_x))
        for i in range(-2, 3):
            for j in range(-2, 3):
                if abs(i) + abs(j) <= 1:
                    continue
                n_x, n_y = x + i, y + j
                if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                    mv_n = maze_visited[n_y][n_x]
                    if mv_n > mv_cur + 1:
                        if S[n_y][n_x] == '.':
                            maze_visited[n_y][n_x] = mv_cur + 1
                            queue.append((n_y, n_x))
    
H, W = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))
 
S = [list(input()) for i in range(H)]
 
maze_visited = [[math.inf] * W for i in range(H)]
 
explore(C,D)
 
if maze_visited[D[0] - 1][D[1] - 1] == math.inf:
    print('-1')
else:
    print(maze_visited[D[0] - 1][D[1] - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
A = 10**12
B = 10**6
d = [INF] * (h*w)

stack = deque([(ch-1)*A + (cw-1)*B + 0])
stack_append = stack.append
stack_popleft = stack.popleft

nex = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
            continue
        else:
            nex.append((i,j))

T = ((-1,0), (1,0), (0,1), (0,-1))
while stack:
    x = stack_popleft()
    curh = (x // A)
    x -= curh * A
    curw = (x // B)
    cnt = x - curw * B

    if d[curh * w + curw] <= cnt:
        continue
    else:
        d[curh * w + curw] = cnt

    for dh, dw in T:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            stack_append(nh*A + nw*B + cnt)

    for dh, dw in nex:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            stack_append(nh*A + nw*B + cnt+1)

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
H,W=map(int, input().split())
Ch, Cw=map(int, input().split())
Dh, Dw=map(int, input().split())
maze=[]
for _ in range(H):
    RRR=(input().replace(".","0")).replace("#","1")
    maze.append(list(map(int, RRR)))
#print(maze)
dis=[[H**2*W**2 for _ in range(W+1)]for _ in range(H+1)]
start=(Ch,Cw,0)
goal=(Dh,Dw)
walk=[(1,0),(-1,0),(0,1),(0,-1)]
wap=[(2,0),(2,1),(2,2),(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)]
cand=[start]
dis[start[0]][start[1]]=0
done=[]
flag=False
while len(cand)>0:
    #print(cand)
    place=cand.pop()
    hh,ww,cost=place
    if hh==Dh and ww==Dw:
        flag=True
    for each in walk:
        h1,w1=hh+each[0],ww+each[1]
        if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost:
            dis[h1][w1]=cost
            cand.append((h1,w1,cost))
    for each in wap:
        h1,w1=hh+each[0],ww+each[1]
        if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost+1:
            dis[h1][w1]=cost+1
            cand.append((h1,w1,cost+1))
if flag:
    print(dis[Dh][Dw])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
S = ['#' * (W+4)] * 2
for i in range(H):
    S.append('##' + input() + '##')
S.append('#' * (W+4))
S.append('#' * (W+4))

CH += 2
CW += 2
DH += 2
DW += 2

dist = [[-1 for i in range(W + 4)] for j in range(H + 4)]
dist[CH - 1][CW - 1] = 0
q = deque()
q.append([CH, CW])

while len(q) != 0:
    current_pos = q.popleft()
    y = current_pos[0]
    x = current_pos[1]
    if (y, x) == (DH, DW):
        print(dist[DH - 1][DW - 1])
        exit()

    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == j == 0:
                continue
            next_y = y + i
            next_x = x + j

            if S[next_y - 1][next_x - 1] == '#':
                continue
            if dist[next_y - 1][next_x - 1] == dist[y - 1][x - 1]:
                continue

            if dist[next_y - 1][next_x - 1] == -1 or dist[next_y - 1][next_x - 1] > dist[y - 1][x - 1]:
                if (i == 0 and j in (-1, 1)) or (j == 0 and i in (-1, 1)):
                    q.appendleft([next_y, next_x])
                    dist[next_y - 1][next_x - 1] = dist[y - 1][x - 1]
                else:
                    if dist[next_y - 1][next_x - 1] == -1:
                        q.append([next_y, next_x])
                        dist[next_y - 1][next_x - 1] = dist[y - 1][x - 1] + 1

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
def main():
    H, W = map(int, input().split())
    S = list(map(int, input().split()))
    G = list(map(int, input().split()))
    S[0] -= 1
    S[1] -= 1
    G[0] -= 1
    G[1] -= 1
    c = [input() for i in range(H)]
    dist = [[-1]*W for _ in range(H)]

    for i in range(H):
        for g in range(W):
            if c[i][g] == "#":
                dist[i][g] = -2

    checkList = set()
    que = deque()
    que.append(S)
    dist[S[0]][S[1]] = 0

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

    cost = 0

    while True:
        if len(que) == 0:
            cost += 1
            que = set()
            for h, w in checkList:
                for i in range(-2, 3):
                    for g in range(-2, 3):
                        nh = h+i
                        nw = w+g
                        if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                            continue
                        else:
                            if dist[nh][nw] == -1:
                                que.add((nh, nw))
            que = deque(que)
            checkList = set()
            if len(que) == 0:
                print(-1)
                exit()
        else:
            h, w = que.popleft()
            if h == G[0] and w == G[1]:
                print(cost)
                exit()
            for i in range(4):
                nh = h+directions[i][0]
                nw = w+directions[i][1]
                if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                    continue
                if dist[nh][nw] == -1:
                    que.append((nh, nw))
                    dist[nh][nw] = cost
                elif dist[nh][nw] == -2:
                    checkList.add((h, w))
main()

Submission status: Time Limit Exceeded

Solution code:
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

input = sys.stdin.readline

########################################
def valid(a,b):
	#print(a,b)
	if 0<=a<=h-1 and 0<=b<=w-1 and arr[a][b] == ".":
		return True
	else:
		return False


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
arr = [input() for i in range(h)]
#print(arr)
can_vis = []
dist = [[10**10]*w for i in range(h)]
q = deque()
ans = float("inf")
q.append((ch,cw))
dist[ch][cw] = 0
#print(dh,dw,ch,cw)
while q:
	#print(q.popleft())
	#print(q)
	curx , cury = q.popleft()
	#can_vis.append((curx,cury))
	for dx,dy in [[1,0],[0,1],[-1,0],[0,-1]]:
		if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
			dist[curx+dx][cury+dy] = dist[curx][cury]
			q.append((curx+dx, cury+dy))
	for dx in range(-2,3):
		for dy in range(-2,3):
			if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
				dist[curx+dx][cury+dy] = dist[curx][cury] + 1 
				q.append((curx+dx, cury+dy))


if dist[dh][dw] == 10**10:
	print(-1)
else:
	print(dist[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
ch -= 1
cw -= 1
dh -= 1
dw -= 1
vec5 = []
vec = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(-2, 3):
    for j in range(-2, 3):
        if abs(i) + abs(j) < 2:
            continue
        vec5 += [(i,j)]

c = 0
q = [(ch, cw)]
while len(q) > 0:
    nq = []
    while len(q) > 0:
        i, j = q.pop()
        s[i][j] = c
        nq += [(i,j)]
        for v in vec:
            ii = i + v[0]
            jj = j + v[1]
            if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
                q += [(ii, jj)]


    while len(nq) > 0:
        i, j = nq.pop()
        for v in vec5:
            ii = i+v[0]
            jj = j+v[1]
            if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
                q += [(ii, jj)]
    c += 1
if s[dh][dw] == '.':
    print(-1)
else:
    print(s[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

input = sys.stdin.readline

########################################
def valid(a,b):
	#print(a,b)
	if 0<=a<=h-1 and 0<=b<=w-1 and arr[a][b] == ".":
		return True
	else:
		return False


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
arr = [list(input()) for i in range(h)]
#print(arr)
can_vis = []
dist = [[10**10]*w for i in range(h)]
q = deque()
ans = float("inf")
q.append((ch,cw))
dist[ch][cw] = 0
#print(dh,dw,ch,cw)
while q:
	#print(q.popleft())
	#print(q)
	curx , cury = q.popleft()
	#can_vis.append((curx,cury))
	for dx,dy in [[1,0],[0,1],[-1,0],[0,-1]]:
		if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
			dist[curx+dx][cury+dy] = dist[curx][cury]
			q.append((curx+dx, cury+dy))
	for dx in range(-2,3):
		for dy in range(-2,3):
			if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
				dist[curx+dx][cury+dy] = dist[curx][cury] + 1 
				q.append((curx+dx, cury+dy))


if dist[dh][dw] == 10**10:
	print(-1)
else:
	print(dist[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 15 17:00:46 2020

@author: saito
"""

# %% import phase
from collections import deque

# %% define phase
global afx
global afy
global ans
ans = 0

def check(s, x, y, o, cnt):
    for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        if s[x+i][y+j] == '.':
            o.append([x+i, y+j, cnt])
            s[x+i][y+j] = str(cnt)
    return o, s

def wcheck(s, x, y, o, cnt):
    for i in range(5):
        a = i-2
        for j in range(5):
            b = j-2
#            if x+a>=0 and y+b>=0 and \
#            x+a<=h+2 and y+b<=w+2 and\
#            s[x+a][y+j] == '.':
            if s[x+a][y+b] == '.':
                if [x+a, y+b] not in o:
                    o.append([x+a, y+b, cnt+1])    
    return o
    
def bfs(s, x, y, h, w):
    cnt = 0
    s[x][y] = str(cnt)
    f = deque()
    wf = deque()
    wf.append([x, y, cnt])
    while wf:
        [x, y, cnt] = wf.popleft()
        f.append([x, y, cnt])
        while f:
            [x, y, cnt] = f.popleft()
            if [x, y, cnt+1] in wf:
                wf.remove([x, y, cnt+1])
            if [x, y] == [h, w]:
                wf.clear()
                return cnt
            f, s = check(s, x, y, f, cnt)
            wf = wcheck(s, x, y, wf, cnt)
    
    return -1

    
    

# %% input phase
h, w = list(map(int, input().split()))
ch, cw = list(map(int, input().split()))
ch += 1
cw += 1
dh, dw = list(map(int, input().split()))
dh += 1
dw += 1
s = [[] for _ in range(h+4)]
s[0] = list('#'*(w+4))
s[1] = list('#'*(w+4))
for i in range(h):
    si = input()
    s[i+2] = list('##' + si + '##')
s[h+2] = list('#'*(w+4))
s[h+3] = list('#'*(w+4))

# %% process phase
ans = bfs(s, ch, cw, dh, dw)

    

# %%output phase
print(ans)

Submission status: Time Limit Exceeded

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


from collections import deque
 
N,M=map(int,input().split())
starty,startx=map(int,input().split())
goaly,goalx=map(int,input().split())
startx-=1
starty-=1
goalx-=1
goaly-=1
 
 
S = [[None] *M for _ in range(N)]#2行3列の場合
#iがyｊがx
 
 
 
 
 
 
for i in range(N):
    tmp=input()
    for j in range(M):
        S[i][j]=tmp[j]
 
if N==1 and M==1:
    if S[0][0]=="#":
        print(-1)
        exit()
    else:
        print(0)
        exit()
 
 
 
seen=[[-1] *M for _ in range(N)]
#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
 
 
dx=[1,0,-1,0]
dy=[0,1,0,-1]
ddx=[2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
ddy=[2,1,0,-1,-2,2,1,-1,-2,2,-2,2,1,-1,-2,2,1,0,-1,-2]
 
 
def dfs(y,x):
 
    todox=deque()
    todoy=deque()
    seen[y][x]=0
    todox.append(x)
    todoy.append(y)
    count=0
    flug=True
    while flug==True:
        flug=False
        while len(todox) !=0:
            x=todox.popleft()
            y=todoy.popleft()
            for i in range(4):
                nx=x+dx[i]
                ny=y+dy[i]
                if nx>=0 and nx<M and ny>=0 and ny<N :
    
    
                            
                    if S[ny][nx]==".":
                        
                        
                        
                        if seen[ny][nx] ==-1:
                            #print("mohu",nx,ny)
                            seen[ny][nx] =seen[y][x]
                            todox.append(nx)
                            todoy.append(ny)

        for k in range(N):
            for j in range(M):
                if seen[k][j]==count:
                    for i in range(20):
                        nx=j+ddx[i]
                        ny=k+ddy[i]
                        if nx>=0 and nx<M and ny>=0 and ny<N :
                            if S[ny][nx]==".":
                                if seen[ny][nx] ==-1:
                                    #print("mohu",nx,ny)
                                    seen[ny][nx] =seen[k][j]+1
                                    todox.append(nx)
                                    todoy.append(ny)
                                
                    flug=True
                    
        count+=1

        
    return seen[goaly][goalx]
 
            
print(dfs(starty,startx))