結果

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int MOD = 998244353;

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

    vector<vector<int>> dp(W, vector<int>(H, 0));
    dp[1][1] = 1;

    for (int i = 0; i < H; i++) {
        vector<vector<int>> dp_d(W, vector<int>(H, 0));
        for (int j = 0; j < W; j++) {
            for (int k = 0; k < H; k++) {
                int t = i + j - k;
                if (t < 0 || t >= W) continue;

                for (int d = 0; d < 4; d++) {
                    int i_ = i, j_ = j, k_ = k, t_ = t;
                    if (d % 2 == 0) t_++;
                    else k_++;
                    if (d / 2 == 0) i_++;
                    else j_++;

                    if (!(i_ < H && j_ < W && t_ < H && k_ < W)) continue;

                    if (S[i_][j_] == '.' && S[k_][t_] == '.' &&
                        ((i_ != k_ || j_ != t_) || (i_ == j_ && i_ == H - 1 && k_ == t_ && k_ == W - 1))) {
                        if (i == i_) {
                            dp[j_][k_] = (dp[j_][k_] + dp[j][k]) % MOD;
                        } else {
                            dp_d[j_][k_] = (dp_d[j_][k_] + dp[j][k]) % MOD;
                        }
                    }
                }
            }
        }
        if (i != H - 1) dp = dp_d;
    }

    cout << dp[W - 1][H - 1] << endl;
    return 0;
}
0