Problem p02579 (python)

Fixed submission:
#!/usr/bin/env python3

from collections import deque

INF = 10 ** 12


H, W = map(int, input().split())
s_i, s_j = map(lambda x: int(x) - 1, input().split())
t_i, t_j = map(lambda x: int(x) - 1, input().split())
field = [input() for _ in range(H)]

# 1. bfs でワープなしで到達できるマスを探索
# 2. 1 で見つかったマスから一回ワープして到達できるマスを探索
# 3. 1, 2 を繰り返す


walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

warp_times = [[INF for j in range(W)] for i in range(H)]
que = deque()

warp_times[s_i][s_j] = 0
que.append((s_i, s_j, 0))

while que:
    i, j, times = que.popleft()
    # ワープ無しで到達できるマスの探索
    for di, dj in walk:
        i_adj, j_adj = i + di, j + dj
        if 0 <= i_adj < H and 0 <= j_adj < W and field[i_adj][j_adj] == '.':
            if warp_times[i_adj][j_adj] > times:
                warp_times[i_adj][j_adj] = times
                que.appendleft((i_adj, j_adj, times))

    # ワープ有りで到達できるマスの探索
    for di, dj in warp:
        i_adj, j_adj = i + di, j + dj
        if 0 <= i_adj < H and 0 <= j_adj < W and field[i_adj][j_adj] == '.':
            if warp_times[i_adj][j_adj] > times + 1:
                warp_times[i_adj][j_adj] = times + 1
                # ワープ無しで到達できるマスを探索しきった後に探索するため、単に append
                que.append((i_adj, j_adj, times + 1))

ans = warp_times[t_i][t_j] if warp_times[t_i][t_j] < INF else '-1'
print(ans)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

from collections import deque
import sys

INF = 10 ** 12


H, W = map(int, input().split())
s_i, s_j = map(lambda x: int(x) - 1, input().split())
t_i, t_j = map(lambda x: int(x) - 1, input().split())
field = [list(input()) for _ in range(H)]

# 1. bfs でワープなしで到達できるマスを探索
# 2. 1 で見つかったマスから一回ワープして到達できるマスを探索
# 3. 1, 2 を繰り返す


def bfs(que, warp_times):
    while que:
        i, j, times = que.popleft()
        # ワープ無しで到達できるマスの探索
        for di, dj in walk:
            i_adj, j_adj = i + di, j + dj
            if 0 <= i_adj < H and i <= j_adj < W and field[i_adj][j_adj] == '.':
                if warp_times[i_adj][j_adj] > times:
                    warp_times[i_adj][j_adj] = times
                    que.appendleft((i_adj, j_adj, times))

        # ワープ有りで到達できるマスの探索
        for di, dj in warp:
            i_adj, j_adj = i + di, j + dj
            if 0 <= i_adj < H and i <= j_adj < W and field[i_adj][j_adj] == '.':
                if warp_times[i_adj][j_adj] > times + 1:
                    warp_times[i_adj][j_adj] = times + 1
                    # ワープ無しで到達できるマスを探索しきった後に探索するため、単に append
                    que.append((i_adj, j_adj, times + 1))


walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

warp_times = [[INF for j in range(W)] for i in range(H)]
que = deque()

warp_times[start_i][start_j] = 0
que.append((start_i, start_j, 0))

bfs(que, warp_times)

ans = warp_times[goal_i][goal_j] if warp_times[goal_i][goal_j] < INF else '-1'
print(ans)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


H, W = map(int, input().split())
start_i, start_j = map(lambda x: int(x) - 1, input().split())
goal_i, goal_j = map(lambda x: int(x) - 1, input().split())
field = [list(input()) for _ in range(H)]

# 1. bfs でワープなしで到達できるマスを探索
# 2. 1 で見つかったマスから一回ワープして到達できるマスを探索
# 3. 1, 2 を繰り返す


walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]


def bfs(que, warp_times):
    while que:
        i, j, times = que.popleft()
        # ワープ無しで到達できるマスの探索
        for di, dj in walk:
            i_adj, j_adj = i + di, j + dj
            if 0 <= i_adj < H and i <= j_adj < W and field[i_adj][j_adj] == '.':
                if warp_times[i_adj][j_adj] > times:
                    warp_times[i_adj][j_adj] = times
                    que.appendleft((i_adj, j_adj, times))

        # ワープ有りで到達できるマスの探索
        for di, dj in warp:
            i_adj, j_adj = i + di, j + dj
            if 0 <= i_adj < H and i <= j_adj < W and field[i_adj][j_adj] == '.':
                if warp_times[i_adj][j_adj] > times + 1:
                    warp_times[i_adj][j_adj] = times + 1
                    # ワープ無しで到達できるマスを探索しきった後に探索するため、単に append
                    que.append((i_adj, j_adj, times + 1))


warp_times = [[INF for j in range(W)] for i in range(W)]
que = deque()

warp_times[start_i][start_j] = 0
que.append((start_i, start_j, 0))

bfs(que, warp_times)

ans = warp_times[goal_i][goal_j] if warp_times[goal_i][goal_j] < INF else '-1'
print(ans)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


H, W = map(int, input().split())
start_i, start_j = map(lambda x: int(x) - 1, input().split())
goal_i, goal_j = map(lambda x: int(x) - 1, input().split())
field = [list(input()) for _ in range(H)]

# 1. bfs でワープなしで到達できるマスを探索
# 2. 1 で見つかったマスから一回ワープして到達できるマスを探索
# 3. 1, 2 を繰り返す


walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]


def bfs(que, warp_times):
    while que:
        i, j, times = que.popleft()
        # ワープ無しで到達できるマスの探索
        for di, dj in walk:
            i_adj, j_adj = i + di, j + dj
            if 0 <= i_adj < H and i <= j_adj < W and field[i_adj][j_adj] == '.':
                if warp_times[i_adj][j_adj] > times:
                    warp_times[i_adj][j_adj] = times
                    que.appendleft((i_adj, j_adj, times))

        # ワープ有りで到達できるマスの探索
        for di, dj in warp:
            i_adj, j_adj = i + di, j + dj
            if 0 <= i_adj < H and i <= j_adj < W and field[i_adj][j_adj] == '.':
                if warp_times[i_adj][j_adj] > times + 1:
                    warp_times[i_adj][j_adj] = times + 1
                    # ワープ無しで到達できるマスを探索しきった後に探索するため、単に append
                    que.append((i_adj, j_adj, times + 1))


warp_times = [[INF for j in range(W)] for i in range(W)]
que = deque()

warp_times[start_i][start_j] = 0
que.append((start_i, start_j, 0))

bfs(que, warp_times)

ans = warp_times[goal_i][goal_j] if warp_times[goal_i][goal_j] < INF else '-1'
print(ans)

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


H, W = map(int, input().split())

start_i, start_j = map(int, input().split())
start_i -= 1
start_j -= 1

goal_i, goal_j = map(int, input().split())
goal_i -= 1
goal_j -= 1

field = []
for _ in range(H):
    line = list(input())
    field.append(line)
# print(field)

# bfs でワープなしで到達できるマスを探索
# 次に bfs でワープ
# i - 1 回目のワープで到達できる各マスから 5 x 5 の領域を探索したときに見つかる未到達のマスが i 回目のワープで到達できるマスになる


def adj(i, j):
    top, bottom = [i + 1, j], [i - 1, j]
    left, right = [i, j - 1], [i, j + 1]

    adj_list = []
    for i_adj, j_adj in top, bottom, left, right:
        if 0 <= i_adj <= H - 1 and 0 <= j_adj <= W - 1:
            if field[i_adj][j_adj] == '.':
                adj_list.append([i_adj, j_adj])

    return adj_list


def warp_adj(i, j):
    diff = [[i, j] for j in range(W) for i in range(H)]
    adj_set = set()

    for i_diff, j_diff in diff:
        i_adj = i + i_diff
        j_adj = j + j_diff
        if 0 <= i_adj <= H - 1 and 0 <= j_adj <= W - 1:
            if field[i_adj][j_adj] == '.':
                adj_set.add((i_adj, j_adj))

    return list(adj_set)


def bfs(que, warp_times):
    while que:
        i, j, times = que.popleft()
        # ワープ無しで到達できるマスの探索
        for i_adj, j_adj in adj(i, j):
            if warp_times[i_adj][j_adj] > times:
                warp_times[i_adj][j_adj] = times
                que.appendleft((i_adj, j_adj, times))

        # ワープ有りで到達できるマスの探索
        for i_adj, j_adj in warp_adj(i, j):
            if warp_times[i_adj][j_adj] > times + 1:
                warp_times[i_adj][j_adj] = times + 1
                # ワープ無しで到達できるマスを探索しきった後に探索するため、単にappendする
                que.append((i_adj, j_adj, times + 1))


warp_times = [[INF for j in range(W)] for i in range(W)]
que = deque()

warp_times[start_i][start_j] = 0
que.append((start_i, start_j, 0))

bfs(que, warp_times)

ans = warp_times[goal_i][goal_j] if warp_times[goal_i][goal_j] < INF else '-1'
print(ans)