結果

問題 No.3071 Double Speedrun
ユーザー detteiuu
提出日時 2025-03-21 22:51:11
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,112 bytes
コンパイル時間 3,779 ms
コンパイル使用メモリ 286,520 KB
実行使用メモリ 7,328 KB
最終ジャッジ日時 2025-03-21 22:51:18
合計ジャッジ時間 6,501 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 RE * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;
// グリッドの幅と高さ
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, ll> dp;
    dp[IDX(1, 0, 0, 1)] = 1;
    for (int i = 0; i < H + W - 3; ++i) {
        unordered_map<ll, ll> 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) % MOD;
            }
            // 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) % MOD;
            }
            // 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) % MOD;
            }
            // 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) % MOD;
            }
        }
        dp = move(ndp);
    }
    cout << dp[IDX(H - 1, W - 1, H - 1, W - 1)] << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0