#1183202 (C++23) No.3679 なんかでっかい虫リターンズ

• 問題: No.3679 なんかでっかい虫リターンズ
• ユーザー: Riris
• 提出日時: 2026-09-05 13:20:50
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 3,156 bytes
• コンパイル時間: 2,161 ms
• コンパイル使用メモリ: 342,764 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-09-05 13:20:54
• 合計ジャッジ時間: 3,838 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge2_0

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

ソースコード

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
using namespace std;
// #include <atcoder/all>
// using namespace atcoder;

using ll = long long;  // 2^63-1まで 負の値は可
// using ull = unsigned long long;  // 0 <= ull <=2^64-1の範囲 負の値は不可
using vl = vector<ll>;
// using vvl = vector<vl>;
// using P = pair<ll, ll>;
template <typename T>
using MNPQ = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using MXPQ = priority_queue<T, vector<T>, less<T>>;

#define overload(a, b, c, d, e, ...) e
#define FOR1(i, n) for (int i = 0; i < n; i++)
#define FOR2(i, s, n) for (int i = s; i < n; i++)
#define FOR3(i, s, n, a) for (int i = s; i < n; i += a)
#define rep(...) overload(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR1_R(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR2_R(i, s, n) for (int i = s - 1; i >= n; i--)
#define FOR3_R(i, s, n, a) for (int i = s - 1; i >= n; i += a)
#define rrep(...) overload(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define nall(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define YN(flg) cout << (flg ? "Yes" : "No") << "\n"
#define out_grid(x, y, h, w) !(0 <= x && x < h && 0 <= y && y < w)
#define debug(x) cerr << #x << " = " << x << endl;
const long long INF = 4e18;

template <typename T>
istream& operator>>(istream& is, vector<T>& a) {
    for (auto& x : a) is >> x;
    return is;
}

template <typename T>
ostream& operator<<(ostream& os, vector<T>& a) {
    for (int i = 0; i < (int)a.size(); i++) os << a[i] << " ";
    return os;
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2>& p) {
    os << "{" << p.first << "," << p.second << "}";
    return os;
}

template <typename K, typename V>
ostream& operator<<(ostream& os, map<K, V>& a) {
    for (auto& [k, v] : a) os << "{key:" << k << ", item:" << v << "} ";
    return os;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll h, w;
    cin >> h >> w;
    ll a, b;
    cin >> a >> b;
    a--, b--;

    ll sr, sc, er, ec;
    cin >> sr >> sc >> er >> ec;
    sr--, sc--, er--, ec--;

    ll p, q;
    cin >> p >> q;
    p--, q--;

    const vl dx = {1, 0, -1, 0};
    const vl dy = {0, 1, 0, -1};

    vector<vector<ll>> to(h, vector<ll>(w, INF));
    queue<pair<ll, ll>> que;

    auto f = [&]() -> void {
        while (!que.empty()) {
            auto [vx, vy] = que.front();
            que.pop();

            rep(i, 4) {
                ll nx = dx[i] + vx, ny = dy[i] + vy;
                if (out_grid(nx, ny, h, w)) continue;
                if (to[nx][ny] != INF) continue;

                to[nx][ny] = to[vx][vy] + 1;
                que.emplace(nx, ny);
            }
        }
    };
    to[a][b] = 0;
    que.emplace(a, b);
    f();

    rep(i, h) rep(j, w) {
        if (sr <= i && i <= er && sc <= j && j <= ec) {
            que.emplace(i, j);
        } else {
            to[i][j] = INF;
        }
    }
    f();

    ll ans = to[p][q] + abs(p - a) + abs(q - b);
    cout << ans << endl;

    return 0;
}