結果

問題 No.3071 Double Speedrun
コンテスト
ユーザー detteiuu
提出日時 2025-03-21 23:08:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,263 bytes
コンパイル時間 5,792 ms
コンパイル使用メモリ 333,436 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-21 23:09:10
合計ジャッジ時間 9,371 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 RE * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <atcoder/all>
#define pass (void)0
#define INF (1<<30)-1
#define INFLL (1LL<<60)-1
using namespace std;
using namespace atcoder;
using mint = modint998244353;
using ll = long long;

// グリッドの幅と高さ
int H, W;

// 座標を一意に識別するための関数
ll IDX(int h1, int w1, int h2, int w2) {
    return w1 + h1 * W + w2 * H * W + h2 * W * H * W;
}

// 座標の復元
tuple<int, int, int, int> IDXR(ll n) {
    int w1 = n % W;
    int h1 = (n / W) % H;
    int w2 = (n / (H * W)) % W;
    int h2 = (n / (W * H * W));
    return {h1, w1, h2, w2};
}

int main() {
    cin >> H >> W;
    vector<string> S(H);
    for (int i=0; i<H; i++) cin >> S[i];

    unordered_map<ll, mint> dp;
    dp[IDX(1, 0, 0, 1)] = 1;

    for (int i = 0; i < H + W - 3; ++i) {
        unordered_map<ll, mint> ndp;
        for (const auto& [key, val] : dp) {
            auto [h1, w1, h2, w2] = IDXR(key);

            // w1+1, w2+1への移動
            if (w1 + 1 < W && w2 + 1 < W && S[h1][w1 + 1] == '.' && S[h2][w2 + 1] == '.') {
                ndp[IDX(h1, w1 + 1, h2, w2 + 1)] = (ndp[IDX(h1, w1 + 1, h2, w2 + 1)] + val);
            }

            // h1+1, h2+1への移動
            if (h1 + 1 < H && h2 + 1 < H && S[h1 + 1][w1] == '.' && S[h2 + 1][w2] == '.') {
                ndp[IDX(h1 + 1, w1, h2 + 1, w2)] = (ndp[IDX(h1 + 1, w1, h2 + 1, w2)] + val);
            }

            // w1+1, h2+1への移動
            if (w1 + 1 < W && h2 + 1 < H && S[h1][w1 + 1] == '.' && S[h2 + 1][w2] == '.' && 
                ((h1 == H - 1 && w1 + 1 == W - 1) || make_pair(h1, w1 + 1) != make_pair(h2 + 1, w2))) {
                ndp[IDX(h1, w1 + 1, h2 + 1, w2)] = (ndp[IDX(h1, w1 + 1, h2 + 1, w2)] + val);
            }

            // h1+1, w2+1への移動
            if (h1 + 1 < H && w2 + 1 < W && S[h1 + 1][w1] == '.' && S[h2][w2 + 1] == '.' && 
                ((h1 + 1 == H - 1 && w1 == W - 1) || make_pair(h1 + 1, w1) != make_pair(h2, w2 + 1))) {
                ndp[IDX(h1 + 1, w1, h2, w2 + 1)] = (ndp[IDX(h1 + 1, w1, h2, w2 + 1)] + val);
            }
        }
        dp = ndp;
    }

    cout << dp[IDX(H - 1, W - 1, H - 1, W - 1)].val() << endl;

    return 0;
}
0