#1183236 (PyPy3) No.3679 なんかでっかい虫リターンズ

• 問題: No.3679 なんかでっかい虫リターンズ
• ユーザー: Rino-program
• 提出日時: 2026-09-05 13:25:50
• 言語: PyPy3 (7.3.23)
• 結果: AC
• 実行時間: 175 ms / 2,000 ms
• コード長: 4,517 bytes
• コンパイル時間: 234 ms
• コンパイル使用メモリ: 95,948 KB
• 実行使用メモリ: 90,380 KB
• 最終ジャッジ日時: 2026-09-05 13:25:58
• 合計ジャッジ時間: 5,518 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
sample	AC * 3
other	AC * 17

ソースコード

# coding: utf-8
# AtCoder Competition Template v2.1 SHORT (PyPy 7.3.20 / Python 3.11)
# ↑ https://github.com/Rino-program/atcoder/blob/main/contests/.template/main.py
# oj test -c 'C:\Rino-program\AtCoder\.venv-pypy311\Scripts\python.exe maina.py' -d input/a
import sys
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, accumulate, product, chain
from bisect import bisect_left, bisect_right
from copy import deepcopy
import operator
import heapq
import math
import string

# ===== 入出力ヘルパ =====
def input() -> str:
    return sys.stdin.readline().rstrip()

def INT() -> int:
    return int(input())

def MAP():
    return map(int, input().split())

def LIST() -> list[int]:
    return list(MAP())

def TUPLE() -> tuple[int, ...]:
    return tuple(MAP())

def LISTS(n: int) -> list[list[int]]:
    return [LIST() for _ in range(n)]

def TUPLES(n: int) -> list[tuple[int, ...]]:
    return [TUPLE() for _ in range(n)]

def LISTSI(n: int) -> list[int]:
    return [INT() for _ in range(n)]

def STR() -> str:
    return input()

def STRS(n: int) -> list[str]:
    return [STR() for _ in range(n)]

def CHARS() -> list[str]:
    return list(STR())

def CHARSL(n: int) -> list[list[str]]:
    return [list(STR()) for _ in range(n)]

# ===== 定数 =====
INF = 10 ** 18
MOD = 998244353
# MOD = 10**9 + 7

# ===== 関数短縮 =====
pr = print
en = enumerate
hepu = heapq.heappush
hepo = heapq.heappop
bil = bisect_left
bir = bisect_right
dedict = defaultdict

# ===== 方向ベクトル =====
DIR4 = [(1, 0), (0, 1), (-1, 0), (0, -1)]
DIR8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]
DIR9 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1), (0, 0)]

# ===== 文字列のリスト =====
LOWER = list(string.ascii_lowercase) # 小文字 a-z の文字列リスト
UPPER = list(string.ascii_uppercase) # 大文字 A-Z の文字列リスト
DIGITS = list(string.digits) # 数字 0-9 の文字列リスト

# ===== よく使う出力関数 =====
def Yes(): print("Yes")
def No(): print("No")
def yes(): print("yes")
def no(): print("no")
def YES(): print("YES")
def NO(): print("NO")
def yn(cond: bool) -> None:
    """条件に応じてYes/No出力"""
    print("Yes" if cond else "No")

# ===== デバッグ =====
def debug(*args, **kwargs) -> None:
    """デバッグ出力（標準エラー）"""
    print("[DEBUG]", *args, **kwargs, file=sys.stderr)

def print_grid(grid: list[list], sep: str = '') -> None:
    """グリッド表示"""
    for row in grid:
        print(sep.join(map(str, row)))


# ==============================================
# =================== main =====================
# ==============================================

def main() -> None:
    # ここに解答を書く
    H, W = MAP()
    A, B = MAP()
    A -= 1; B -= 1
    R1, C1, R2, C2 = MAP()
    P, Q = MAP()
    P -= 1; Q -= 1
    d = deque([(A, B, 0)])
    ans = 0
    GMap = [[0 for i in range(W)] for i in range(H)]
    for i in range(R1-1, R2):
        for j in range(C1-1, C2):
            GMap[i][j] = 1
    f = [[1 for i in range(W)] for i in range(H)]
    f[A][B] = 0
    while d:
        x, y, now = d.popleft()
        if GMap[x][y]:
            ans += now
            d = deque([(x, y, 0)])
            break
        for dx, dy in DIR4:
            nx, ny = dx+x, dy+y
            if 0 <= nx < H and 0 <= ny < W and f[nx][ny]:
                f[nx][ny] = 0
                d.append((nx, ny, now+1))
    
    GMap = [[0 for i in range(W)] for i in range(H)]
    GMap[P][Q] = 1
    f = [[1 for i in range(W)] for i in range(H)]
    f[d[0][0]][d[0][1]] = 0
    while d:
        x, y, now = d.popleft()
        if GMap[x][y]:
            ans += now
            d = deque([(x, y, 0)])
            break
        for dx, dy in DIR4:
            nx, ny = dx+x, dy+y
            if 0 <= nx < H and 0 <= ny < W and f[nx][ny]:
                f[nx][ny] = 0
                d.append((nx, ny, now+1))

    PMap = [[0 for i in range(W)] for i in range(H)]
    PMap[A][B] = 1
    f = [[1 for i in range(W)] for i in range(H)]
    f[d[0][0]][d[0][1]] = 0
    while d:
        x, y, now = d.popleft()
        if PMap[x][y]:
            ans += now
            break
        for dx, dy in DIR4:
            nx, ny = dx+x, dy+y
            if 0 <= nx < H and 0 <= ny < W and f[nx][ny]:
                f[nx][ny] = 0
                d.append((nx, ny, now+1))
    print(ans)

















if __name__ == "__main__":
    main()