結果

問題 No.3504 Insert Maze
コンテスト
ユーザー The Forsaking
提出日時 2026-04-17 23:32:42
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,713 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,683 ms
コンパイル使用メモリ 218,132 KB
実行使用メモリ 67,328 KB
最終ジャッジ日時 2026-04-17 23:34:33
合計ジャッジ時間 92,143 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 69 WA * 6 TLE * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;
using ll = long long;
const int N = 2000010, MOD = 998244353, INF = 0x3f3f3f3f;
int n, m, w[N];

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

char s[2010][2010];
int d[2010][2010], p[2010][2010], q[2010][2010];
bool st[2010][2010][3];
void solve() {
    memset(d, 0x3f, sizeof d);
    memset(p, 0x3f, sizeof p);
    memset(q, 0x3f, sizeof q);
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n + 1; i++) scanf("%s", s[i] + 1);
    priority_queue<array<int, 4>, vector<array<int, 4> >, greater<array<int, 4> > > pq;
    for (int i = 1; i < n + 1; i++)
        for (int j = 1; j < m + 1; j++)
            if (s[i][j] == 'S') {
                d[i][j] = 0;
                pq.push({0, i, j, 0});
            }
    while (pq.size()) {
        int v = pq.top()[0], x = pq.top()[1], y = pq.top()[2], op = pq.top()[3]; pq.pop();
        if (st[x][y][op]) continue;
        st[x][y][op] = 1;
        if (!op && s[x][y] == 'G') {
            printf("%d\n", d[x][y]);
            return;
        }
        if (!op) {
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx > n || ny > m || nx < 1 || ny < 1 || s[nx][ny] == '#') continue;
                if (d[nx][ny] > v + 1) d[nx][ny] = v + 1, pq.push({v + 1, nx, ny, 0});
            }
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx > n || ny > m || nx < 1 || ny < 1) continue;
                if (dy[i] && p[nx][ny] > v + 2) p[nx][ny] = v + 2, pq.push({v + 2, nx, ny, 1});
                if (dx[i] && q[nx][ny] > v + 2) q[nx][ny] = v + 2, pq.push({v + 2, nx, ny, 2});
            }
            if (p[x][y] > v + 2) p[x][y] = v + 2, pq.push({v + 2, x, y, 1});
            if (q[x][y] > v + 2) q[x][y] = v + 2, pq.push({v + 2, x, y, 2});
        } else if (op == 1) {
            if (s[x][y] != '#' && p[x][y] < d[x][y]) d[x][y] = p[x][y], pq.push({d[x][y], x, y, 0});
            if (x > 1 && p[x - 1][y] > p[x][y] + 1) p[x - 1][y] = p[x][y] + 1, pq.push({p[x - 1][y], x - 1, y, 1});
            if (x < n && p[x + 1][y] > p[x][y] + 1) p[x + 1][y] = p[x][y] + 1, pq.push({p[x + 1][y], x + 1, y, 1});
        } else {
            if (s[x][y] != '#' && q[x][y] < d[x][y]) d[x][y] = q[x][y], pq.push({d[x][y], x, y, 0});
            if (y > 1 && q[x][y - 1] > q[x][y] + 1) q[x][y - 1] = q[x][y] + 1, pq.push({q[x][y - 1], x, y - 1, 2});
            if (y < m && q[x][y + 1] > q[x][y] + 1) q[x][y + 1] = q[x][y] + 1, pq.push({q[x][y + 1], x, y + 1, 2});
        }
    }
}

int main() {
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}
0