結果

問題 No.3679 なんかでっかい虫リターンズ
コンテスト
ユーザー yas_yasyu
提出日時 2026-09-05 13:40:57
言語 PyPy3
(7.3.23)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 97 ms / 2,000 ms
+ 319µs
コード長 2,403 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 237 ms
コンパイル使用メモリ 96,200 KB
実行使用メモリ 85,456 KB
最終ジャッジ日時 2026-09-05 13:41:31
合計ジャッジ時間 3,320 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque

DIRECT = [0, 1, 0, -1, 0]

H, W = map(int, input().split())
A, B = map(lambda x: int(x) - 1, input().split())
t, l, b, r = map(lambda x: int(x) - 1, input().split())
P, Q = map(lambda x: int(x) - 1, input().split())


dist = [[H * W + 1] * W for _ in range(H)]
que = deque([(A, B)])
dist[A][B] = 0
destroy_point = (-1, -1)
step1 = -1
if t <= A <= b and l <= B <= r:
    destroy_point = (A, B)
    step1 = 0
else:
    # step 1
    while que:
        ci, cj = que.popleft()
        for d in range(4):
            di, dj = DIRECT[d], DIRECT[d + 1]
            ni, nj = ci + di, cj + dj
            if not (0 <= ni < H and 0 <= nj < W):
                continue
            if dist[ni][nj] <= dist[ci][cj] + 1:
                continue

            dist[ni][nj] = dist[ci][cj] + 1
            if t <= ni <= b and l <= nj <= r:
                step1 = dist[ni][nj]
                destroy_point = (ni, nj)
                que = []
                break

            que.append((ni, nj))

# step 2
step2 = 0

# step 3
que = deque([destroy_point])
dist = [[H * W + 1] * W for _ in range(H)]
di, dj = destroy_point
dist[di][dj] = 0
step3 = -1
if destroy_point == (P, Q):
    step3 = 0
else:
    while que:
        ci, cj = que.popleft()
        for d in range(4):
            di, dj = DIRECT[d], DIRECT[d + 1]
            ni, nj = ci + di, cj + dj
            if not (0 <= ni < H and 0 <= nj < W):
                continue
            if dist[ni][nj] <= dist[ci][cj] + 1:
                continue

            dist[ni][nj] = dist[ci][cj] + 1
            if (P, Q) == (ni, nj):
                step3 = dist[ni][nj]
                que = []
                break

            que.append((ni, nj))

# step 4
que = deque([(P, Q)])
dist = [[H * W + 1] * W for _ in range(H)]
dist[P][Q] = 0
step4 = -1

if (P, Q) == (A, B):
    step4 = 0
else:
    while que:
        ci, cj = que.popleft()
        for d in range(4):
            di, dj = DIRECT[d], DIRECT[d + 1]
            ni, nj = ci + di, cj + dj
            if not (0 <= ni < H and 0 <= nj < W):
                continue
            if dist[ni][nj] <= dist[ci][cj] + 1:
                continue

            dist[ni][nj] = dist[ci][cj] + 1
            if (A, B) == (ni, nj):
                step4 = dist[ni][nj]
                que = []
                break

            que.append((ni, nj))

print(step1 + step2 + step3 + step4)
0