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:
# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
from collections import defaultdict
from collections import deque
INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b, w):
		self.graph[a].append([b, w])

class BFS0_1(object):
	def  __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque()
		self.Q.append(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		while self.Q:
			v = self.Q.popleft()
			for i, w in self.g[v]:
				if w:
					if self.dist[v] + 1 >= self.dist[i]:
						continue
					self.dist[i] = self.dist[v] + 1
					self.Q.append(i)
				else:
					if self.dist[v] >= self.dist[i]:
						continue
					self.dist[i] = self.dist[v]
					self.Q.appendleft(i)

def main():
	H, W = getlist()
	Ch, Cw = getlist()
	Dh, Dw = getlist()
	L = [[0] * (W + 4)]
	L.append([0] * (W + 4))
	for i in range(H):
		l = list(input())
		l = [0 if l[j] == "#" else 1 for j in range(W)]
		L.append([0, 0] + l + [0, 0])

	L.append([0] * (W + 4))
	L.append([0] * (W + 4))


	G = Graph()
	for h in range(2, H + 2):
		for w in range(2, W + 2):
			if L[h][w]:
				for p in range(-2, 3):
					for q in range(-2, 3):
						if L[h + p][w + q]:
							d = abs(p) + abs(q)
							if d == 0:
								pass
							elif d >= 2:
								G.add_edge(W * h + w, W * (h + p) + w + q, 1)
								G.add_edge(W * (h + p) + w + q, W * h + w, 1)
							else:
								G.add_edge(W * h + w, W * (h + p) + w + q, 0)
								G.add_edge(W * (h + p) + w + q, W * h + w, 0)


	N = (H + 4) * (W + 4)
	BF = BFS0_1(G, W * (Ch + 1) + Cw + 1, N)
	ans = BF.dist[W * (Dh + 1) + Dw + 1]
	if ans == INF:
		print(-1)
	else:
		print(ans)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
from collections import defaultdict
from collections import deque
INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b, w):
		self.graph[a].append([b, w])

class BFS0_1(object):
	def  __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque()
		self.Q.append(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		while self.Q:
			v = self.Q.popleft()
			for i, w in self.g[v]:
				if w == 1:
					if self.dist[v] + 1 >= self.dist[i]:
						continue
					self.dist[i] = self.dist[v] + 1
					self.Q.append(i)
				else:
					if self.dist[v] >= self.dist[i]:
						continue
					self.dist[i] = self.dist[v]
					self.Q.appendleft(i)

def main():
	H, W = getlist()
	Ch, Cw = getlist()
	Dh, Dw = getlist()
	L = [0] * (2 * W + 8)
	for i in range(H):
		l = list(input())
		l = [0 if l[j] == "#" else 1 for j in range(W)]
		L += [0, 0] + l + [0, 0]

	L += [0] * (2 * W + 8)
	G = Graph()
	for h in range(2, H + 2):
		for w in range(2, W + 2):
			if L[(W + 4) * h + w] == 1:
				for p in range(-2, 3):
					for q in range(-2, 3):
						if L[(W + 4) * (h + p) + w + q] == 1:
							if (abs(p) + abs(q) >= 2):
								G.add_edge(W * h + w, W * (h + p) + w + q, 1)
								G.add_edge(W * (h + p) + w + q, W * h + w, 1)
							else:
								G.add_edge(W * h + w, W * (h + p) + w + q, 0)
								G.add_edge(W * (h + p) + w + q, W * h + w, 0)

	N = (H + 4) * (W + 4)
	BF = BFS0_1(G, W * (Ch + 1) + Cw + 1, N)
	# print(BF.dist)
	# print(G.graph)
	ans = BF.dist[W * (Dh + 1) + Dw + 1]
	if ans == INF:
		print(-1)
	else:
		print(ans)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
from collections import defaultdict
from collections import deque
INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b, w):
		self.graph[a].append([b, w])

class BFS0_1(object):
	def  __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque()
		self.Q.append(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		while self.Q:
			v = self.Q.popleft()
			for i, w in self.g[v]:
				if w == 1:
					if self.dist[v] + 1 >= self.dist[i]:
						continue
					self.dist[i] = self.dist[v] + 1
					self.Q.append(i)
				else:
					if self.dist[v] >= self.dist[i]:
						continue
					self.dist[i] = self.dist[v]
					self.Q.appendleft(i)

def main():
	H, W = getlist()
	Ch, Cw = getlist()
	Dh, Dw = getlist()
	L = [[0] * (W + 4)]
	L.append([0] * (W + 4))
	for i in range(H):
		l = list(input())
		l = [0 if l[j] == "#" else 1 for j in range(W)]
		L.append([0, 0] + l + [0, 0])

	L.append([0] * (W + 4))
	L.append([0] * (W + 4))


	G = Graph()
	for h in range(2, H + 2):
		for w in range(2, W + 2):
			if L[h][w] == 1:
				for p in range(-2, 3):
					for q in range(-2, 3):
						if L[h + p][w + q] == 1:
							if (abs(p) + abs(q) >= 2):
								G.add_edge(W * h + w, W * (h + p) + w + q, 1)
								G.add_edge(W * (h + p) + w + q, W * h + w, 1)
							else:
								G.add_edge(W * h + w, W * (h + p) + w + q, 0)
								G.add_edge(W * (h + p) + w + q, W * h + w, 0)


	N = (H + 4) * (W + 4)
	BF = BFS0_1(G, W * (Ch + 1) + Cw + 1, N)
	# print(BF.dist)
	ans = BF.dist[W * (Dh + 1) + Dw + 1]
	if ans == INF:
		print(-1)
	else:
		print(ans)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
from collections import defaultdict
from collections import deque
INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b, w):
		self.graph[a].append([b, w])

class BFS0_1(object):
	def  __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque()
		self.Q.append(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		while self.Q:
			v = self.Q.popleft()
			for i, w in self.g[v]:
				if w == 1:
					if self.dist[v] + 1 >= self.dist[i]:
						continue
					self.dist[i] = self.dist[v] + 1
					self.Q.append(i)
				else:
					if self.dist[v] >= self.dist[i]:
						continue
					self.dist[i] = self.dist[v]
					self.Q.appendleft(i)

def main():
	H, W = getlist()
	Ch, Cw = getlist()
	Dh, Dw = getlist()
	L = [[0] * (W + 4)]
	L.append([0] * (W + 4))
	for i in range(H):
		l = list(input())
		l = [0 if l[j] == "#" else 1 for j in range(W)]
		L.append([0, 0] + l + [0, 0])

	L.append([0] * (W + 4))
	L.append([0] * (W + 4))
	# print(L)

	G = Graph()
	for h in range(2, H + 2):
		for w in range(2, W + 2):
			if L[h][w] == 1:
				for p in range(-2, 3):
					for q in range(-2, 3):
						if L[h + p][w + q] == 1 and (abs(p) + abs(q) >= 2):
							G.add_edge(W * h + w, W * (h + p) + w + q, 1)
							G.add_edge(W * (h + p) + w + q, W * h + w, 1)

	for h in range(2, H + 1):
		for w in range(2, W + 2):
			if L[h][w] == 1 and L[h + 1][w] == 1:
				G.add_edge(W * h + w, W * (h + 1) + w, 0)
				G.add_edge(W * (h + 1) + w, W * h + w, 0)

	for h in range(2, H + 2):
		for w in range(2, W + 1):
			if L[h][w] == 1 and L[h][w + 1] == 1:
				G.add_edge(W * h + w, W * h + w + 1, 0)
				G.add_edge(W * h + w + 1, W * h + w, 0)

	N = (H + 4) * (W + 4)
	BF = BFS0_1(G, W * (Ch + 1) + Cw + 1, N)
	# print(BF.dist)
	ans = BF.dist[W * (Dh + 1) + Dw + 1]
	if ans == INF:
		print(-1)
	else:
		print(ans)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
from collections import defaultdict
from collections import deque
INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b, w):
		self.graph[a].append([b, w])

class BFS0_1(object):
	def  __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque()
		self.Q.append(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		while self.Q:
			v = self.Q.popleft()
			for i, w in self.g[v]:
				if w == 1:
					if self.dist[v] + 1 >= self.dist[i]:
						continue
					self.dist[i] = self.dist[v] + 1
					self.Q.append(i)
				else:
					if self.dist[v] >= self.dist[i]:
						continue
					self.dist[i] = self.dist[v]
					self.Q.appendleft(i)

def main():
	H, W = getlist()
	Ch, Cw = getlist()
	Dh, Dw = getlist()
	L = [[0] * (W + 4)]
	L.append([0] * (W + 4))
	for i in range(H):
		l = list(input())
		l = [0 if l[j] == "#" else 1 for j in range(W)]
		L.append([0, 0] + l + [0, 0])

	L.append([0] * (W + 4))
	L.append([0] * (W + 4))
	# print(L)

	G = Graph()
	for h in range(2, H + 2):
		for w in range(2, W + 2):
			if L[h][w] == 1:
				for p in range(-2, 3):
					for q in range(-2, 3):
						if L[h + p][w + q] == 1:
							G.add_edge(W * h + w, W * (h + p) + w + q, 1)
							G.add_edge(W * (h + p) + w + q, W * h + w, 1)

	for h in range(2, H + 1):
		for w in range(2, W + 2):
			if L[h][w] == 1 and L[h + 1][w] == 1:
				G.add_edge(W * h + w, W * (h + 1) + w, 0)
				G.add_edge(W * (h + 1) + w, W * h + w, 0)

	for h in range(2, H + 2):
		for w in range(2, W + 1):
			if L[h][w] == 1 and L[h][w + 1] == 1:
				G.add_edge(W * h + w, W * h + w + 1, 0)
				G.add_edge(W * h + w + 1, W * h + w, 0)

	N = (H + 4) * (W + 4)
	BF = BFS0_1(G, W * (Ch + 1) + Cw + 1, N)
	# print(BF.dist)
	ans = BF.dist[W * (Dh + 1) + Dw + 1]
	if ans == INF:
		print(-1)
	else:
		print(ans)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
#dp[][]は何回のジャンプが必要かを示す

from collections import deque
h,w = list(map(int,input().split()))
sy,sx = list(map(int,input().split()))
gy,gx = list(map(int,input().split()))


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


grid = [input() for _ in range(h)]
dp = [[-1 for _ in range(w)] for _ in range(h)]

dp[sy][sx] = 0

#print(dp)
pos_que = deque()
pos_que.append((sx,sy))
#print(pos_que)
ps = deque()
ps.append((sx,sy))

def area_move(pos_que):
    while pos_que:
        px,py = pos_que.popleft()
        d = dp[py][px]
        ps.append((px,py))
        for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
            px_new = px + dx
            py_new = py + dy
            if py_new < 0 or h <= py_new or px_new < 0 or w <= px_new or dp[py_new][px_new] != -1 or grid[py_new][px_new] == '#':
                continue
            else:
                dp[py_new][px_new] = d
                pos_que.append((px_new,py_new))
                ps.append((px_new,py_new))
    return False




def magic_jump(n,ps):
    while ps:
        if True:
            i,j = ps.popleft()
            #print(i,j)
            if dp[j][i] == n:
                for dx,dy in ((2,-2),(2,-1),(2,0),(2,1),(2,2),(-2,2),(-1,2),(0,2),(1,2),(2,2),(-1,1),(1,1)):
                    new_w = i+dx
                    new_h = j + dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w or grid[new_h][new_w] == '#' or dp[new_h][new_w] >-1:
                        continue
                    else:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                for dx,dy in ((2,-2),(2,-1),(2,0),(2,1),(2,2),(-2,2),(-1,2),(0,2),(1,2),(2,2),(-1,1),(1,1)):
                    new_w = i-dx
                    new_h = j-dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w or grid[new_h][new_w] == '#' or dp[new_h][new_w] >-1:
                        continue
                    else:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                        
                        
                
def main(dp_old):
    for i in range(10000000):
        area_move(pos_que)
        if dp[gy][gx] != -1:
            return dp[gy][gx]
        magic_jump(i,ps)
        if not pos_que:
            return -1
    return -1

print(main([]))

Submission status: Time Limit Exceeded

Solution code:
#dp[][]は何回のジャンプが必要かを示す

from collections import deque
h,w = list(map(int,input().split()))
sy,sx = list(map(int,input().split()))
gy,gx = list(map(int,input().split()))


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


grid = [input() for _ in range(h)]
dp = [[-1 for _ in range(w)] for _ in range(h)]

dp[sy][sx] = 0

#print(dp)
pos_que = deque()
pos_que.append((sx,sy))
#print(pos_que)
ps = deque()
ps.append((sx,sy))

def area_move(pos_que):
    while pos_que:
        px,py = pos_que.popleft()
        d = dp[py][px]
        ps.append((px,py))
        for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
            px_new = px + dx
            py_new = py + dy
            if py_new < 0 or h <= py_new or px_new < 0 or w <= px_new or dp[py_new][px_new] != -1:
                continue
            if grid[py_new][px_new] == '.':
                dp[py_new][px_new] = d
                pos_que.append((px_new,py_new))
                ps.append((px_new,py_new))
    return False




def magic_jump(n,ps):
    while ps:
        if True:
            i,j = ps.popleft()
            #print(i,j)
            if dp[j][i] == n:
                for dx,dy in ((2,-2),(2,-1),(2,0),(2,1),(2,2),(-2,2),(-1,2),(0,2),(1,2),(2,2),(-1,1),(1,1)):
                    new_w = i+dx
                    new_h = j + dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w:
                        continue
                    if grid[new_h][new_w] == '#' or dp[new_h][new_w] >=0:
                        continue
                    else:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                for dx,dy in ((2,-2),(2,-1),(2,0),(2,1),(2,2),(-2,2),(-1,2),(0,2),(1,2),(2,2),(-1,1),(1,1)):
                    new_w = i-dx
                    new_h = j-dy
                    if new_h < 0 or h <= new_h or new_w < 0 or w <= new_w:
                        continue
                    if grid[new_h][new_w] == '#' or dp[new_h][new_w] >-1:
                        continue
                    else:
                        dp[new_h][new_w] =n+1
                        pos_que.append((new_w,new_h))
                        
                        
                
def main(dp_old):
    for i in range(10000000):
        area_move(pos_que)

        if dp[gy][gx] != -1:
            return dp[gy][gx]
        magic_jump(i,ps)

        #print(i)
        if not pos_que:
            return -1
    return -1

print(main([]))

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)]

INF = H * W

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

num_step = [[INF for w in range(W)] for h in range(H)]
num_step[Ch - 1][Cw - 1] = 0

# スタート地点を定義
queue = [(Ch - 1, Cw - 1)]
num_warp = 0

# 幅優先探索
while not queue == []:
    magic_tiles = []
    while not queue == []:
        h = queue.pop() # here 
        if h[0] == Dh - 1 and h[1] == Dw - 1:
            print(num_warp)
            exit()
        for i in range(4):
            if 0 <= h[0]+dy[i] < H and 0 <= h[1]+dx[i] < W and S[h[0]+dy[i]][h[1]+dx[i]] == '.' \
                 and num_step[h[0]+dy[i]][h[1]+dx[i]] > num_warp:
                queue.append((h[0]+dy[i], h[1]+dx[i]))
                num_step[h[0]+dy[i]][h[1]+dx[i]] = num_warp

        # 魔法を使っていける場所を検討
        mx = [-2, -1 , 0, 1, 2]
        my = [-2, -1 , 0, 1, 2]

        for x in mx:
            for y in my:
                 if 0 <= h[0] + y < H and 0 <= h[1] + x < W and S[h[0] + y][h[1] + x] == '.' \
                     and num_step[h[0] + y][h[1] + x] == INF:
                    magic_tiles.append((h[0] + y, h[1] + x))

    num_warp += 1

    # キューの追加
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            num_step[magic[0]][magic[1]] = num_warp
            queue.append((magic[0], magic[1]))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
h,w = map(int,input().split())
sx,sy = map(int,input().split())
sx -= 1
sy -= 1
gx,gy = map(int,input().split())
gx -= 1
gy -= 1
route = []
for i in range(h):
  lst = list(input())
  route.append(lst)
  
brock = [['#']*w for i in range(h)]
s = 0
que = deque([])
dx = [-1,0,1,0]
dy = [0,-1,0,1]

brock[sx][sy] = 0
que.append((sx,sy))



while que:
  
  (p,q) = que.popleft()
  if (p,q) == (gx,gy):
    print(brock[gx][gy])
    sys.exit()
  for i in range(4):
    p2,q2 = p+dx[i],q+dy[i]
    if 0 <= p2 < h and 0<= q2 < w and route[p2][q2] == '.' and brock[p2][q2] == '#':
      brock[p2][q2] = brock[p][q]
      que.append((p2,q2))
      
  
  if len(que) == 0:
    
    s += 1
    for u in range(h):
      for v in range(w):
        if brock[u][v] == s-1:
          x,y = u,v
          for j in range(-2,3):
             for k in range(-2,3):
                x2 = x+j
                y2 = y+k
                if 0 <= x2 < h and 0<= y2 < w and route[x2][y2] == '.' and brock[x2][y2] == '#':
                  brock[x2][y2] = s
                  que.append((x2,y2))
            
                  
              
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
h,w = map(int,input().split())
sx,sy = map(int,input().split())
sx -= 1
sy -= 1
gx,gy = map(int,input().split())
gx -= 1
gy -= 1
route = []
for i in range(h):
  lst = list(input())
  route.append(lst)
  
brock = [['#']*w for i in range(h)]
s = 0
que = deque([])
dx = [-1,0,1,0]
dy = [0,-1,0,1]

brock[sx][sy] = 0
que.append((sx,sy))
lst = [(sx,sy)]


while que:
  
  (p,q) = que.popleft()
  if (p,q) == (gx,gy):
    print(brock[gx][gy])
    sys.exit()
  for i in range(4):
    p2,q2 = p+dx[i],q+dy[i]
    if 0 <= p2 < h and 0<= q2 < w and route[p2][q2] == '.' and brock[p2][q2] == '#':
      brock[p2][q2] = brock[p][q]
      que.append((p2,q2))
      lst.append((p2,q2))
  
  if len(que) == 0:
    
    s += 1
    for u in range(h):
      for v in range(w):
        if brock[u][v] == s-1:
          x,y = u,v
          for j in range(-2,3):
             for k in range(-2,3):
                x2 = x+j
                y2 = y+k
                if 0 <= x2 < h and 0<= y2 < w and route[x2][y2] == '.' and brock[x2][y2] == '#':
                  brock[x2][y2] = s
                  que.append((x2,y2))
            
                  
              
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import queue

H,W = map(int,input().split())
C = [int(i)+1 for i in input().split()]
D = [int(i)+1 for i in input().split()]

l = []
l.append([-1]*(W+4))
l.append([-1]*(W+4))
for _ in range(H):
    l.append([-1,-1]+ [0 if i=="." else -1 for i in input()] + [-1,-1])
l.append([-1]*(W+4))
l.append([-1]*(W+4))

l[C[0]][C[1]] = 1 

def p():
    for i in l[2:2+H]:
        print(",".join([str(j) for j in i[2:2+W]]))

q = queue.Queue()
q.put(C)
now = 1
q2 = queue.Queue()
while True:
    while not q.empty():
        x,y = q.get()
        q2.put([x,y])
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            if l[x+i][y+j] ==0:
                q.put([x+i,y+j])
                l[x+i][y+j] = now
    if l[D[0]][D[1]] > 0:
        print(l[D[0]][D[1]]-1)
        break
    now += 1
    if q2.empty():
        print(-1)
        break
    while not q2.empty():
        x,y = q2.get()
        for i in range(-2,3):
            for j in range(-2,3):
                if l[x+i][y+j] ==0:
                    q.put([x+i,y+j])
                    l[x+i][y+j] = now
    if l[D[0]][D[1]] > 0:
        print(l[D[0]][D[1]]-1) 
        break

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Sep  6 00:28:43 2020

@author: liang
"""


H, W = map(int, input().split())
sh, sw = map(int, input().split())
sh -= 1
sw -= 1

gh, gw = map(int, input().split())
gh -= 1
gw -= 1

field = [input() for i in range(H)]

d = [[-1]*W for _ in range(H)]
visited = [[False]*W for _ in range(H)]
adj1 = [(1,0), (-1,0), (0,1), (0,-1)]
adj2 = [(x,y) for x in range(-2,3) for y in range(-2,3)]

from collections import deque

def BFS():
    def isValid(p):
        if p[0] < 0 or p[0] >= H or p[1] < 0 or p[1] >= W:
            return False
        if field[p[0]][p[1]] == "#":
            return False
        if visited[p[0]][p[1]] :
            return False
        return True
    
    q = deque()
    q.append((sh, sw))
    d[sh][sw] = 0
    visited[sh][sw] = True
    while q:
        cur = q.popleft()
        #normal move
        for a in adj1:
            nex = (cur[0] + a[0], cur[1] + a[1])
            if isValid(nex) and (d[nex[0]][nex[1]] == -1 or d[nex[0]][nex[1]] > d[cur[0]][cur[1]]):
                 d[nex[0]][nex[1]] = d[cur[0]][cur[1]]
                 visited[nex[0]][nex[1]] = True
                 q.append((nex[0], nex[1]))
        #warp
        for a in adj2:
            nex = (cur[0] + a[0], cur[1] + a[1])
            if isValid(nex):
                d[nex[0]][nex[1]] = d[cur[0]][cur[1]] + 1
                q.append((nex[0], nex[1]))
                    
BFS()
#print(d)
#print(visited)
print(d[gh][gw])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Sep 11 11:57:24 2020

@author: liang
"""

H, W = map(int, input().split())
sy, sx = map(int, input().split())
sy -= 1
sx -= 1
gy, gx = map(int, input().split())
gy -= 1
gx -= 1
field = [input() for _ in range(H)]

from collections import deque
q = deque()
adj1 = [(0,1), (0,-1), (1,0), (-1,0)]
visited = [[False]*W for _ in range(H)]

q.append((sy, sx, 0))

while q:
    cy, cx, cost = q.popleft()
    #print(cy,cx,cost)
    if (cy,cx) == (gy,gx):
        print(cost)
        break
    if not visited[cy][cx]:
        #print("visit!")
        visited[cy][cx] = True
        #cost 0
        for a in adj1:
            ny, nx = cy + a[0], cx + a[1]
            if ny >= H or ny < 0:
                continue
            if nx >= W or nx < 0:
                continue
            if field[ny][nx] == "#":
                continue
            if not visited[ny][nx]:
                q.appendleft((ny, nx, cost))
        #cost 1
        for i in range(-2,3):
            for j in range(-2,3):
                ny, nx = cy + i, cx + j
                if ny >= H or ny < 0:
                    continue
                if nx >= W or nx < 0:
                    continue
                if field[ny][nx] == "#":
                    continue
                if not visited[ny][nx]:
                    q.append((ny, nx, cost+1))
else:
    print(-1)

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)]

INF = H * W

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

# def steppable(h,w):
#     if not (h in range(H)) or not (w in range(W)):
#         return False
#     if S[h][w] == '#':
#         return False
#     else:
#         return True

num_step = [[INF for w in range(W)] for h in range(H)]
num_step[Ch - 1][Cw - 1] = 0

# スタート地点を定義
queue = [(Ch - 1, Cw - 1)]
num_warp = 0

# 幅優先探索
while not queue == []:
    magic_tiles = []
    while not queue == []:
        h = queue.pop() # here 
        if h[0] == Dh - 1 and h[1] == Dw - 1:
            print(num_warp)
            exit()
        # next_  = [
        #     (h[0] + 1, h[1], 0),
        #     (h[0] - 1, h[1], 0),
        #     (h[0], h[1] + 1, 0),
        #     (h[0], h[1] - 1, 0),]
        for i in range(4):
            if 0 <= h[0]+dy[i] < H and 0 <= h[1]+dx[i] < W and S[h[0]+dy[i]][h[1]+dx[i]] == '.' \
                 and num_step[h[0]+dy[i]][h[1]+dx[i]] > num_warp:
                queue.append((h[0]+dy[i], h[1]+dx[i]))
                num_step[h[0]+dy[i]][h[1]+dx[i]] = num_warp

        # 魔法を使っていける場所を検討
        mx = [-2, -1 , 0, 1, 2]
        my = [-2, -1 , 0, 1, 2]

        for x in mx:
            for y in my:
                 if 0 <= h[0] + y < H and 0 <= h[1] + x < W and S[h[0] + y][h[1] + x] == '.' \
                     and num_step[h[0] + y][h[1] + x] == INF:
                    magic_tiles.append((h[0] + y, h[1] + x))

    num_warp += 1

    # キューの追加
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            num_step[magic[0]][magic[1]] = num_warp
            queue.append((magic[0], magic[1]))

print(-1)

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)]

INF = H * W

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

# def steppable(h,w):
#     if not (h in range(H)) or not (w in range(W)):
#         return False
#     if S[h][w] == '#':
#         return False
#     else:
#         return True

num_step = [[INF for w in range(W)] for h in range(H)]
num_step[Ch - 1][Cw - 1] = 0

# スタート地点を定義
queue = [(Ch - 1, Cw - 1)]
num_warp = 0

# 幅優先探索
while not queue == []:
    magic_tiles = []
    while not queue == []:
        h = queue.pop(0) # here 
        if h[0] == Dh - 1 and h[1] == Dw - 1:
            print(num_warp)
            exit()
        # next_  = [
        #     (h[0] + 1, h[1], 0),
        #     (h[0] - 1, h[1], 0),
        #     (h[0], h[1] + 1, 0),
        #     (h[0], h[1] - 1, 0),]
        for i in range(4):
            if 0 <= h[0]+dy[i] < H and 0 <= h[1]+dx[i] < W and S[h[0]+dy[i]][h[1]+dx[i]] == '.' \
                 and num_step[h[0]+dy[i]][h[1]+dx[i]] > num_warp:
                queue.append((h[0]+dy[i], h[1]+dx[i]))
                num_step[h[0]+dy[i]][h[1]+dx[i]] = num_warp

        # 魔法を使っていける場所を検討
        mx = [-2, -1 , 0, 1, 2]
        my = [-2, -1 , 0, 1, 2]

        for x in mx:
            for y in my:
                 if 0 <= h[0] + y < H and 0 <= h[1] + x < W and S[h[0] + y][h[1] + x] == '.' \
                     and num_step[h[0] + y][h[1] + x] == INF:
                    magic_tiles.append((h[0] + y, h[1] + x))

    num_warp += 1

    # キューの追加
    for magic in magic_tiles:
        if num_step[magic[0]][magic[1]] == INF:
            num_step[magic[0]][magic[1]] = num_warp
            queue.append((magic[0], magic[1]))

print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)

[h,w]=list(map(int,input().split()))
[ch,cw]=list(map(int,input().split()))
[dh,dw]=list(map(int,input().split()))
chizu=[]
for i in range(h):
    chizu.append(list(input()))

chizu[ch-1][cw-1]=0
jougesayu=[[-1,0],[1,0],[0,-1],[0,1]]
warp=[]
for i in [-2,-1,0,1,2]:
    for j in [-2,-1,0,1,2]:
        if [i,j] not in jougesayu and [i,j]!=[0,0]:
            warp.append([i,j])

def bfs(x,y,num):
    global chizu
    for [i,j] in jougesayu:#上下左右
        if 1<=x+i<=h and 1<=y+j<=w:#枠内ならば
            if chizu[x+i-1][y+j-1]!="#":#道があれば
                if chizu[x+i-1][y+j-1]==".":#未到達なら数ふる
                    chizu[x+i-1][y+j-1]=num
                    bfs(x+i,y+j,num)
                else:#到達済みなら
                    if num<chizu[x+i-1][y+j-1]:#より早ければ
                        chizu[x+i-1][y+j-1]=num
                        bfs(x+i,y+j,num)
    for [i,j] in warp:#ワープ
        if 1<=x+i<=h and 1<=y+j<=w:#枠内ならば
            if chizu[x+i-1][y+j-1]!="#":#道があれば
                if chizu[x+i-1][y+j-1]==".":#未到達なら数ふる
                    chizu[x+i-1][y+j-1]=num+1
                    bfs(x+i,y+j,num+1)
                else:#到達済みなら
                    if num+1<chizu[x+i-1][y+j-1]:#より早ければ
                        chizu[x+i-1][y+j-1]=num+1
                        bfs(x+i,y+j,num+1)

bfs(ch,cw,0)
ans=chizu[dh-1][dw-1]
if chizu[dh-1][dw-1]=="#" or chizu[dh-1][dw-1]==".":
    ans=-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)

[h,w]=list(map(int,input().split()))
[ch,cw]=list(map(int,input().split()))
[dh,dw]=list(map(int,input().split()))
chizu=[]
for i in range(h):
    chizu.append(list(input()))

chizu[ch-1][cw-1]=0

def bfs(x,y,num):
    global chizu
    for i in [-2,-1,0,1,2]:#x座標
        for j in [-2,-1,0,1,2]:#y座標
            if i!=0 or j!=0:#周囲の24つ調べる
                if 1<=x+i<=h and 1<=y+j<=w:#枠内ならば
                    if [i,j] in [[-1,0],[1,0],[0,-1],[0,1]]:#上下左右
                        if chizu[x+i-1][y+j-1]!="#":#道があれば
                            if chizu[x+i-1][y+j-1]==".":#未到達なら数ふる
                                chizu[x+i-1][y+j-1]=num
                                bfs(x+i,y+j,num)
                            else:#到達済みなら
                                if num<chizu[x+i-1][y+j-1]:#より早ければ
                                    chizu[x+i-1][y+j-1]=num
                                    bfs(x+i,y+j,num)
                    else:#ワープ
                        if chizu[x+i-1][y+j-1]!="#":#道があれば
                            if chizu[x+i-1][y+j-1]==".":#未到達なら数ふる
                                chizu[x+i-1][y+j-1]=num+1
                                bfs(x+i,y+j,num+1)
                            else:#到達済みなら
                                if num+1<chizu[x+i-1][y+j-1]:#より早ければ
                                    chizu[x+i-1][y+j-1]=num+1
                                    bfs(x+i,y+j,num+1)


bfs(ch,cw,0)
ans=chizu[dh-1][dw-1]
if chizu[dh-1][dw-1]=="#" or chizu[dh-1][dw-1]==".":
    ans=-1
print(ans)