結果

問題 No.3679 なんかでっかい虫リターンズ
コンテスト
ユーザー rrrr
提出日時 2026-09-07 21:14:54
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 2 ms / 2,000 ms
+ 643µs
コード長 3,353 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,595 ms
コンパイル使用メモリ 365,100 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2026-09-07 21:15:02
合計ジャッジ時間 4,163 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)


int main() {
    int H, W; cin >> H >> W;
    int A, B; cin >> A >> B;
    A--; B--;
    int R1, C1, R2, C2; cin >> R1 >> C1 >> R2 >> C2;
    R1--; C1--; R2--; C2--;
    int P, Q; cin >> P >> Q;
    P--; Q--;
    
    int dy[4] = {1, 0, -1 ,0};
    int dx[4] = {0, 1,  0, -1};

    queue<pair<int, int>> q;
    vector<vector<int>> dist(H, vector<int> (W, -1));
    dist[A][B] = 0;
    q.push({A, B});

    int ans = 0;

    bool fg = false;
    int cx=B, cy=A;
    if (cy >= R1 && cy <= R2 && cx >= C1 && cx <= C2) {

    } else {
        while (!q.empty()) {
            auto [y, x] = q.front();
            q.pop();


            for (int k = 0; k < 4; k++) {
                int ny = y + dy[k];
                int nx = x + dx[k];

                if (ny < 0 || ny >= H) continue;
                if (nx < 0 || nx >= W) continue;

                if (dist[ny][nx] != -1) continue;

                dist[ny][nx] = dist[y][x] + 1;
                q.push({ny, nx});

                if (ny >= R1 && ny <= R2 && nx >= C1 && nx <= C2) {
                    cy = ny;
                    cx = nx;

                    ans += dist[ny][nx];
                    fg = true;
                    break;
                }
                
            }

            if (fg) break;
        }
    }
    


    queue<pair<int, int>> q2;
    vector<vector<int>> dist2(H, vector<int> (W, -1));
    dist2[cy][cx] = 0;
    q2.push({cy, cx});

    bool fg2 = false;

    if (cy == P && cx == Q) {

    } else {
        while (!q2.empty()) {
            auto [y, x] = q2.front();
            q2.pop();
    
    
            for (int k = 0; k < 4; k++) {
                int ny = y + dy[k];
                int nx = x + dx[k];
    
                if (ny < 0 || ny >= H) continue;
                if (nx < 0 || nx >= W) continue;
    
                if (dist2[ny][nx] != -1) continue;
    
                dist2[ny][nx] = dist2[y][x] + 1;
                q2.push({ny, nx});
    
                if (ny == P && nx == Q) {
                    cy = P;
                    cx = Q;
    
                    ans += dist2[ny][nx];
    
                    fg2 = true;
                }
                
            }
    
            if (fg2) break;
        }
    }

    queue<pair<int, int>> q3;
    vector<vector<int>> dist3(H, vector<int> (W, -1));
    dist3[cy][cx] = 0;
    q3.push({cy, cx});

    bool fg3 = false;

    if (cy == A && cx == B) {

    } else {

        while (!q3.empty()) {
            auto [y, x] = q3.front();
            q3.pop();
    
    
            for (int k = 0; k < 4; k++) {
                int ny = y + dy[k];
                int nx = x + dx[k];
    
                if (ny < 0 || ny >= H) continue;
                if (nx < 0 || nx >= W) continue;
    
                if (dist3[ny][nx] != -1) continue;
    
                dist3[ny][nx] = dist3[y][x] + 1;
                q3.push({ny, nx});
    
                if (ny == A && nx == B) {
                    cy = A;
                    cx = B;
    
                    ans += dist3[ny][nx];
    
                    fg3 = true;
                }
                
            }
    
            if (fg3) break;
        }
    }

    cout << ans << endl;

    return 0;
}
0