結果

問題 No.3504 Insert Maze
コンテスト
ユーザー The Forsaking
提出日時 2026-04-17 23:49:55
言語 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,876 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,366 ms
コンパイル使用メモリ 216,628 KB
実行使用メモリ 67,200 KB
最終ジャッジ日時 2026-04-17 23:50:16
合計ジャッジ時間 19,978 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 79 WA * 6
権限があれば一括ダウンロードができます

ソースコード

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;
    deque<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_back({0, i, j, 0});
            }
    while (pq.size()) {
        int v = pq.front()[0], x = pq.front()[1], y = pq.front()[2], op = pq.front()[3]; pq.pop_front();
        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_back({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 (m >= 2 && dy[i] && p[nx][ny] > v + 1) p[nx][ny] = v + 1, pq.push_back({v + 1, nx, ny, 1});
                if (n >= 2 && dx[i] && q[nx][ny] > v + 1) q[nx][ny] = v + 1, pq.push_back({v + 1, nx, ny, 2});
            }
            if (m >= 2 && p[x][y] > v + 1) p[x][y] = v + 1, pq.push_back({v + 1, x, y, 1});
            if (n >= 2 && q[x][y] > v + 1) q[x][y] = v + 1, pq.push_back({v + 1, x, y, 2});
        } else if (op == 1) {
            if (s[x][y] != '#' && p[x][y] + 1 < d[x][y]) d[x][y] = p[x][y] + 1, pq.push_back({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_back({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_back({p[x + 1][y], x + 1, y, 1});
        } else {
            if (s[x][y] != '#' && q[x][y] + 1 < d[x][y]) d[x][y] = q[x][y] + 1, pq.push_back({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_back({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_back({q[x][y + 1], x, y + 1, 2});
        }
    }
}

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