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:
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
yukaset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == ".":
			yukaset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if k in yukaset:
					if not k in setmada:
						if not k in settansaku:
							setmada.add(k)
								
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in list(stock):
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if not k in settansaku:
					setmada.add(k)
	
	stock=set()
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
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 = [list(input()) for _ in range(h)]

ch, cw = ch - 1, cw - 1
dh, dw = dh - 1, dw - 1
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [0, -2], [-1, 2], [-1, 1],
     [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NY, NX in N:
        if 0 <= x + NX < w and 0 <= y + NY < h and S[y + NY][x + NX] != "#":
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for PY, PX in P:
        if 0 <= x + PX < w and 0 <= y + PY < h and S[y + PY][x + PX] != "#":
            if grid[y + PY][x + PX] == -1 or grid[y + PY][x + PX] > count + 1:
                grid[y + PY][x + PX] = count + 1
            que.append((count + 1, y + PY, x + PX))

print(grid[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
kabeset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == "#":
			kabeset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if not k in kabeset:
					if 0 <= k[0]:
						if 0 <= k[1]:
							if k[0] < h:
								if k[1] < w:
									if not k in setmada:
										if not k in settansaku:
											setmada.add(k)
								
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in list(stock):
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if not k in settansaku:
				if 0 <= k[0]:
					if 0 <= k[1]:
						if k[0] < h:
							if k[1] < w:
								if not k in kabeset:
									setmada.add(k)
	
	stock=set()
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque

    h, w = map(int, readline().split())
    sr, sc = map(int, readline().split())
    gr, gc = map(int, readline().split())

    grid = [["#"] * (w + 2)]
    for _ in range(h):
        s = ["#"] + list(input()) + ["#"]
        grid.append(s)
    grid.append(["#"] * (w + 2))

    ans = 0
    que1 = deque()
    que1.append((sr, sc, 0))
    grid[sr][sc] = "!"

    while que1:
        cr, cc, cost = que1.popleft()
        if cr == gr and cc == gc:
            return print(cost)

        if grid[cr + 1][cc] == ".":
            que1.appendleft((cr + 1, cc, cost))
            grid[cr + 1][cc] = "!"
        if grid[cr - 1][cc] == ".":
            que1.appendleft((cr - 1, cc, cost))
            grid[cr - 1][cc] = "!"
        if grid[cr][cc + 1] == ".":
            que1.appendleft((cr, cc + 1, cost))
            grid[cr][cc + 1] = "!"
        if grid[cr][cc - 1] == ".":
            que1.appendleft((cr, cc - 1, cost))
            grid[cr][cc - 1] = "!"

        for mr in range(-2, 3):
            for mc in range(-2, 3):
                nr = cr + mr
                nc = cc + mc
                if 1 <= nr <= h and 1 <= nc <= w:
                    if grid[nr][nc] == ".":
                        que1.append((nr, nc, cost + 1))

    return print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class P:
    def __init__(self, c):
        self.c = c
        self.reached = False
        self.searched = False
        self.checked = False

from collections import deque
H, W = [int(i) for i in input().split()]
Ch, Cw = [int(i)-1 for i in input().split()]
Dh, Dw = [int(i)-1 for i in input().split()]
S = [[None for _ in range(H)] for _ in range(W)]
for y in range(H):
    tmp = input()
    for x in range(W):
        S[x][y] = P(tmp[x])

def neighbors(x, y, d):
    for i in range(max(0, x-1), min(W, x+2)):
        if S[i][y].reached == False and S[i][y].c == '.':
            d.append((i, y))
    for i in range(max(0, y-1), min(H, y+2)):
        if S[x][i].reached == False and S[x][i].c == '.':
            d.append((x, i))

def jump(x, y, d):
    S[x][y].checked = True
    for i in range(max(0, x-2), min(W, x+3)):
        for j in range(max(0, y-2), min(H, y+3)):
            if S[i][j].reached == False and S[i][j].searched == False and S[i][j].c == '.':
                d.append((i, j))
                S[i][j].searched = True


def BFS(x, y):
    route = deque([(x, y)])
    if S[x][y].reached:
        return route
    d = deque([(x, y)])
    while True:
        x, y = d.popleft()
        route.append((x, y))
        S[x][y].reached = True
        neighbors(x, y, d)
        if len(d) == 0:
            break
    return route


counter = 0
if Cw == Dw and Ch == Dh:
    print(0)
    exit()
q = deque([(Cw, Ch)])
flag = False
while True:
    array = []
    while len(q) > 0:
        x, y = q.popleft()
        array.append(BFS(x, y))
    if S[Dw][Dh].reached == True:
        break
    counter += 1
    for each in array:
        while len(each) > 0:
            i, j = each.pop()
            if S[i][j].reached and S[i][j].checked == False:
                jump(i, j, q)
    if len(q) == 0:
        flag = True
        break
if flag:
    print(-1)
else:
    print(counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
H, W = map(int, input().split())
c = [int(i) + 1 for i in input().split()]
d = [int(i) + 1 for i in input().split()]

s = []
s.append('#'*(W+4))
s.append('#'*(W+4))
for i in range(H):
    a = input()
    s.append('##' + a + '##')
s.append('#'*(W+4))
s.append('#'*(W+4))

q = deque([]) # 探索開始点
qq = deque([])
q.append((c[0], c[1], 0))
visited = [[False for __ in range(W+4)] for _ in range(H+4)]

while q:
    xx, yy, kaisuu = q.popleft()
    if visited[xx][yy] == True:
        continue
    qq.append((xx, yy))
    ls = deque()
    while qq:
        x, y = qq.pop()
        visited[x][y] = True
        ls.append((x, y, kaisuu))
        if x == d[0] and y == d[1]:
            num = 0
            for i in range(10**100):
                num += 1
            print(kaisuu)
            sys.exit()
        if s[x+1][y] == '.' and visited[x+1][y] == False:
            qq.append((x+1, y))
        if s[x-1][y] == '.' and visited[x-1][y] == False:
            qq.append((x-1, y))
        if s[x][y+1] == '.' and visited[x][y+1] == False:
            qq.append((x, y+1))
        if s[x][y-1] == '.' and visited[x][y-1] == False:
            qq.append((x, y-1))
    for u in ls:
        a, b, e = u
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                if abs(i) == 1 and abs(j) == 1:
                    continue
                if s[a+i][b+j] == '.' and visited[a+i][b+j] == False:
                    q.append((a+i, b+j, e+1))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')

def dijkstra_al(s, n, ALcost):
    '''
    n: 頂点の数、s: 始点
    AL_cost[head] = [(tail, cost), ..., (tail, cost)]
    cost存在しないときはinf
    '''
    import heapq

    fixed = [False] * n # 重み確定したかどうか
    nfixed = 0 # 確定した数
    vertex_cost = [INF] * n  # 始点sから各頂点への重み

    # 1. 始点に0を書き込む
    vertex_cost[s] = 0
    H = []  # (cost, vertex)のheap
    heapq.heappush(H, (0, s))

    while(H): # Hが空になるまで
        # 2. 未確定の地点の中からもっとも小さい値を持つ地点を1つ選び、その値を確定させる
        u_cost, u = heapq.heappop(H)
        if fixed[u]: continue  # 取り出した頂点がすでに決まっている（古い情報）
        fixed[u] = True
        nfixed += 1

        # 3. 2で確定した地点から直接繋がっていて、かつ未確定な地点に対し、
        #    重みを計算し、書き込まれている値より小さければ更新する
        for v, cost in ALcost[u]:
            if fixed[v]: continue
            newcost = u_cost + cost
            if newcost < vertex_cost[v]:
                vertex_cost[v] = newcost
                heapq.heappush(H, (newcost, v))

        # 4. 全ての地点が確定していれば終了。そうでなければ2に戻る
        if nfixed == n: break

    return vertex_cost


def rc_to_v(y, x):
    return y * W + x

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

AL = [[] for _ in range(H * W)]

for y in range(H):
    for x in range(W):
        if S[y][x] == '#':  continue

        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny = y + dy
                nx = x + dx
                if ny < 0 or H <= ny or nx < 0 or W <= nx:
                    continue
                if S[ny][nx] == '#':  # 行けない
                    continue
                if (dy, dx) in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 0))
                else:
                    AL[rc_to_v(y, x)].append((rc_to_v(ny, nx), 1))


cost = dijkstra_al(rc_to_v(sy, sx), H * W, AL)

ans = cost[rc_to_v(gy, gx)]
print(-1 if ans == INF else int(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
kabeset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == "#":
			kabeset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if not k in kabeset:
					if 0 <= k[0]:
						if 0 <= k[1]:
							if k[0] < h:
								if k[1] < w:
									if not k in setmada:
										if not k in settansaku:
											setmada.add(k)
								
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in list(stock):
		stock.remove((i, j))
		for k in itertools.product(range(i-2, i+3), range(j-2, j+3)):
			if not k in settansaku:
				if 0 <= k[0]:
					if 0 <= k[1]:
						if k[0] < h:
							if k[1] < w:
								if not k in kabeset:
									setmada.add(k)
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [0, -2], [-1, 2], [-1, 1],
     [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NY, NX in N:
        if 0 <= x + NX < w and 0 <= y + NY < h and S[y + NY][x + NX] != "#":
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for PY, PX in P:
        if 0 <= x + PX < w and 0 <= y + PY < h and S[y + PY][x + PX] != "#":
            if grid[y + PY][x + PX] == -1 or grid[y + PY][x + PX] > count + 1:
                grid[y + PY][x + PX] = count + 1
            que.append((count + 1, y + PY, x + PX))

print(grid[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = [int(_) for _ in input().split()]
C = [int(_) - 1 for _ in input().split()]
D = [int(_) - 1 for _ in input().split()]

S = [input() for _ in range(H)]
V = [[-1 for w in range(W)] for h in range(H)]

V[C[0]][C[1]] = 0

pool = deque()
pool.append(tuple([0, C[0], C[1]]))
while(pool):
    c, y, x = pool.pop()
    for dx in [-2, -1, 0, 1, 2]:
        for dy in [-2, -1, 0, 1, 2]:
            if y + dy < 0 or H <= y + dy:
                continue
            if x + dx < 0 or W <= x + dx:
                continue
            if S[y+dy][x+dx] == "#":
                continue
            if c != V[y][x]:
                continue
            if (dx, dy) in [(-1,0),(1,0),(0,-1),(0,1)]:
                if V[y+dy][x+dx] == -1 or V[y+dy][x+dx] > V[y][x]:
                    V[y+dy][x+dx] = V[y][x]
                    pool.appendleft((c, y+dy, x+dx))
            elif V[y+dy][x+dx] == -1 or V[y+dy][x+dx] > V[y][x] + 1:
                V[y+dy][x+dx] = V[y][x] + 1
                pool.append((c+1, y+dy, x+dx))
print(V[D[0]][D[1]])

Submission status: Time Limit Exceeded

Solution code:
import collections

def bfs(v, goal, D, next_v, seen, rank):
    for x in D[v]:
        if x in seen:
            continue
        if x == goal:
            return True
        else:
            next_v.append((x,rank))
            seen.append(x)    


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
S = [[x for x in input()] for _ in range(h)]
A = [i for i in range(h*w)]
B = collections.defaultdict(lambda:set())
#移動Aで連結成分に分解
for i in range(h):
    for j in range(w):
        if S[i][j] == '#':
            A[w*i+j] = -1
        if i < h-1:
            if S[i][j] == '.' and S[i+1][j] == '.':
                A[w*i+j] = A[w*(i+1)+j] = min(A[w*i+j], A[w*(i+1)+j]) 
        if j < w-1:
            if S[i][j] == '.' and S[i][j+1] == '.':
                A[w*i+j] = A[w*i+(j+1)] = min(A[w*i+j], A[w*i+(j+1)])
        #移動Aによる連結成分をノードとして移動Bで連結グラフを作成
        for k in range(3):
            for l in range(5):
                if i+k-2 >= 0 and j+l-2 >= 0 and j+l-2 < w:
                    if S[i][j] == '.' and S[i+k-2][j+l-2] == '.': #連結可能条件
                        if A[w*i+j] != A[w*(i+k-2)+(j+l-2)]:
                            B[A[w*i+j]].add(A[w*(i+k-2)+(j+l-2)])
                            B[A[w*(i+k-2)+(j+l-2)]].add(A[w*i+j])        
                

if A[ch*w+cw] == A[dh*w+dw]: #Aで連結している
    ans = 0
else:
    next_v = [(A[ch*w+cw],0)]
    goal = A[dh*w+dw]
    seen = [A[ch*w+cw]]
    ans = 1
    while (True):
        if len(next_v) == 0: #Bで連結してない
            ans = -1
            break
        v = next_v[0][0]
        rank = next_v[0][1] + 1
        next_v.pop(0)
        if bfs(v, goal, B, next_v, seen, rank): #Bで連結しているなら
            ans = rank
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
kabeset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == "#":
			kabeset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if not k in kabeset:
					if 0 <= k[0]:
						if 0 <= k[1]:
							if k[0] < h:
								if k[1] < w:
									if not k in setmada:
										if not k in settansaku:
											setmada.add(k)
											if k == goal:
												mode = 0
								
	if mode == 0:
		break
	
	cost += 1
	for i, j in list(stock):
		stock.remove((i, j))
		for k in itertools.product(range(i-2, i+3), range(j-2, j+3)):
			if not k in settansaku:
				if 0 <= k[0]:
					if 0 <= k[1]:
						if k[0] < h:
							if k[1] < w:
								if not k in kabeset:
									setmada.add(k)
									if k == goal:
										mode = 0
							
	if mode == 0:
		break

if mode == 0:
	print(cost)
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
import itertools
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
kabeset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == "#":
			kabeset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
kouho = 1
mode = 1
cost = 0

while kouho > 0:
	while kouho > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			kouho -= 1
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if not k in kabeset:
					if 0 <= k[0]:
						if 0 <= k[1]:
							if k[0] < h:
								if k[1] < w:
									if not k in setmada:
										if not k in settansaku:
											setmada.add(k)
											kouho += 1
											if k == goal:
												mode = 0
								
	if mode == 0:
		break
	
	cost += 1
	for i, j in list(stock):
		stock.remove((i, j))
		for k in itertools.product(range(i-2, i+3), range(j-2, j+3)):
			if not k in settansaku:
				if 0 <= k[0]:
					if 0 <= k[1]:
						if k[0] < h:
							if k[1] < w:
								if not k in kabeset:
									setmada.add(k)
									kouho += 1
									if k == goal:
										mode = 0
							
	if mode == 0:
		break
	
	kouho = len(setmada)

if mode == 0:
	print(cost)
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 = [None]*(H+4)
S[0] = S[1] = S[H+2] = S[H+3] = ["#"]*(W+4)
for i in range(2, H+2):
    S[i] = ["#"] + ["#"] + list(input()) + ["#"] + ["#"]

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

Ch += 1
Cw += 1
Dh += 1
Dw += 1

# bfs

warp_times = 0

def warp(i, j, cost, warp_times, q):
    change = 0
    for h in range(i-2, i+3):
        for w in range(j-2, j+3):
            # print(h, w, i, j)
            # print(S[h][w])
            if S[h][w] == "." and cost[h][w] == -1:
                q.append([h, w])
                cost[h][w] = warp_times + 1
                change = 1
    
    return change

q = deque()
q.append([Ch, Cw])

while True:
    

    same_cost = list()
    no_change = 1

    while len(q):
        # print(q)
        now = q.popleft()
        i = now[0]
        j = now[1]

        cost[i][j] = warp_times
        same_cost.append([i, j])

        if S[i][j-1] == "." and cost[i][j-1] == -1:
            q.append([i, j-1])
        if S[i][j+1] == "." and cost[i][j+1] == -1:
            q.append([i, j+1])
        if S[i-1][j] == "." and cost[i-1][j] == -1:
            q.append([i-1, j])
        if S[i+1][j] == "." and cost[i+1][j] == -1:
            q.append([i+1, j])
    

    for point in same_cost:
        change = warp(point[0], point[1], cost, warp_times, q)
        if change :
            no_change = 0
    
    warp_times += 1
    
    if no_change:
        break

print(cost[Dh][Dw])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [0, -2], [-1, 2], [-1, 1],
     [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NX, NY in N:
        if 0 <= x + NX < w and 0 <= y + NY < h and S[y + NY][x + NX] != "#":
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for PX, PY in P:
        if 0 <= x + PX < w and 0 <= y + PY < h and S[y + PY][x + PX] != "#":
            if grid[y + PY][x + PX] == -1 or grid[y + PY][x + PX] > count + 1:
                grid[y + PY][x + PX] = count + 1
            que.append((count + 1, y + PY, x + PX))

print(grid[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
def check(g,h,w,s):
    if (g[0]<0 or g[0]>=h) or (g[1]<0 or g[1]>=w):
        return False
    if s[g[0]][g[1]]==-1:
        return True
    else:
        return False



h,w=map(int,input().split())
c=[int(x)-1 for x in input().split()]
d=[int(x)-1 for x in input().split()]
s=[]
for j in range(h):
    l=[-1 if x=="." else -2 for x in list(input())]
    s.append(l)
s[c[0]][c[1]]=0
u=[c]
i=0
t=0
while t==0:
    for j in u:
        if j==d:
            t=1
            break
        for k in [[j[0]-1,j[1]],[j[0]+1,j[1]],[j[0],j[1]-1],[j[0],j[1]+1]]:
            if check(k,h,w,s):
                s[k[0]][k[1]]=i
                u.append(k)
    i+=1
    v=[]
    for j in u:
        if j==d:
            t=1
            break
        for k1 in range(-2,3):
            for k2 in range(-2,3):
                k=[j[0]+k1,j[1]+k2]
                if check(k,h,w,s):
                    s[k[0]][k[1]]=i
                    v.append(k)
    if v==[]:
        t=1
    u=v
print(s[d[0]][d[1]])

Submission status: Time Limit Exceeded

Solution code:
import itertools
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
kabeset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == "#":
			kabeset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
kouho = 1
mode = 1
cost = 0

while kouho > 0:
	while kouho > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			kouho -= 1
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if 0 <= k[0]:
					if 0 <= k[1]:
						if k[0] < h:
							if k[1] < w:
								if not k in kabeset:
									if not k in setmada:
										if not k in settansaku:
											setmada.add(k)
											kouho += 1
											if k == goal:
												mode = 0
								
	if mode == 0:
		break
	
	cost += 1
	newkouho = len(stock)
	while newkouho > 0:
		for i, j in list(stock):
			stock.remove((i, j))
			newkouho -= 1
			for k in itertools.product(range(i-2, i+3), range(j-2, j+3)):
				if 0 <= k[0]:
					if 0 <= k[1]:
						if k[0] < h:
							if k[1] < w:
								if not k in kabeset:
									if not k in settansaku:
										setmada.add(k)
										kouho += 1
										if k == goal:
											mode = 0
								
	if mode == 0:
		break
	
	kouho = len(setmada)

if mode == 0:
	print(cost)
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
#辺の重み(変化量)が0である場合は01DFSって特別なやつ
#0の場合はそこでBFSできる
import sys
from collections import deque
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
h,w=map(int,input().split())
c=[int(i)-1 for i in input().split()]
d=[int(i)-1 for i in input().split()]
s=[input() for i in range(h)]
inf=100000000
dp=[[-1 if s[i][j]=="#" else inf for j in range(w)] for i in range(h)]
dp[c[0]][c[1]]=0
now=deque([[c[0],c[1]]])
def bfs():
    global h,w,s,dp,now
    while len(now):
        i,j=now.popleft()
        if i>0:
            if dp[i-1][j]!=-1:
                if dp[i-1][j]>dp[i][j]:
                    dp[i-1][j]=dp[i][j]
                    now.appendleft([i-1,j])
        if j>0:
            if dp[i][j-1]!=-1:
                if dp[i][j-1]>dp[i][j]:
                    dp[i][j-1]=dp[i][j]
                    now.appendleft([i,j-1])
        if i<h-1:
            if dp[i+1][j]!=-1:
                if dp[i+1][j]>dp[i][j]:
                    dp[i+1][j]=dp[i][j]
                    now.appendleft([i+1,j])
        if j<w-1:
            if dp[i][j+1]!=-1:
                if dp[i][j+1]>dp[i][j]:
                    dp[i][j+1]=dp[i][j]
                    now.appendleft([i,j+1])
        for k in range(-2,3):
            for l in range(-2,3):
                if 0<=i+k<h and 0<=j+l<w:
                    if dp[i+k][j+l]!=-1:
                        if dp[i+k][j+l]>dp[i][j]+1:
                            dp[i+k][j+l]=dp[i][j]+1
                            now.appendleft([i+k,j+l])
bfs()
print(dp[d[0]][d[1]] if dp[d[0]][d[1]]!=inf else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [0, -2], [-1, 2], [-1, 1],
     [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NX, NY in N:
        nx = x + NX
        ny = y + NY
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "#":
            if grid[ny][nx] == -1 or grid[ny][nx] > count:
                grid[ny][nx] = count
                que.appendleft((count, ny, nx))
    for PX, PY in P:
        px = x + PX
        py = y + PY
        if 0 <= px < w and 0 <= py < h and S[py][px] != "#":
            if grid[py][px] == -1 or grid[py][px] > count + 1:
                grid[py][px] = count + 1
            que.append((count + 1, py, px))

print(grid[dh][dw])

Submission status: Time Limit Exceeded

Solution code:
import itertools
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
kabeset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == "#":
			kabeset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
kouho = 1
mode = 1
cost = 0

while kouho > 0:
	while kouho > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			kouho -= 1
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if 0 <= k[0] < h and 0 <= k[1] < w:
					if not k in kabeset:
						if not k in setmada:
							if not k in settansaku:
								setmada.add(k)
								kouho += 1
								if k == goal:
									mode = 0
								
	if mode == 0:
		break
	
	cost += 1
	newkouho = len(stock)
	while newkouho > 0:
		for i, j in list(stock):
			stock.remove((i, j))
			newkouho -= 1
			for k in itertools.product(range(i-2, i+3), range(j-2, j+3)):
				if 0 <= k[0] < h and 0 <= k[1] < w:
					if not k in kabeset:
						if not k in setmada:
							if not k in settansaku:
								setmada.add(k)
								kouho += 1
								if k == goal:
									mode = 0
								
	if mode == 0:
		break
	
	kouho = len(setmada)

if mode == 0:
	print(cost)
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
PX = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
PY = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]

que = deque([[0, ch, cw]])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for i in range(4):
        nx = x + NX[i]
        ny = y + NY[i]
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "#":
            if grid[ny][nx] == -1 or grid[ny][nx] > count:
                grid[ny][nx] = count
                que.appendleft([count, ny, nx])
    for qx, qy in zip(PX, PY):
        px = x + qx
        py = y + qy
        if 0 <= px < w and 0 <= py < h and S[py][px] != "#":
            if grid[py][px] == -1 or grid[py][px] > count + 1:
                grid[py][px] = count + 1
            que.append([count + 1, py, px])

print(grid[dh][dw])