結果

問題 No.2430 Damage Zone
コンテスト
ユーザー Kak1_n0_tane
提出日時 2023-08-14 12:33:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 20 ms / 2,000 ms
コード長 3,147 bytes
コンパイル時間 4,665 ms
コンパイル使用メモリ 258,700 KB
最終ジャッジ日時 2025-02-16 08:04:06
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ld = long double;
using ll = long long;
const ld pi = acos(-1.0);
const ld tau = 2*pi;

const ll MOD = 998244353;
using mint = modint998244353;

istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); }
istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); }
template<int m> istream &operator>>(istream &is, static_modint<m> &a) { long long v; is >> v; a = v; return is; }
template<int m> istream &operator>>(istream &is, dynamic_modint<m> &a) { long long v; is >> v; a = v; return is; }
template<int m> ostream &operator<<(ostream &os, const static_modint<m> &a) { return os << a.val(); }
template<int m> ostream &operator<<(ostream &os, const dynamic_modint<m> &a) { return os << a.val(); }

template<class T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<class T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }

#define Rep(parameter, start, end) for(int parameter = start; parameter < (ll)(end); parameter++)
#define rep(parameter, end) Rep(parameter, 0, end)
#define rRep(parameter, start, end) for(int parameter = (ll)(end)-1; parameter >= start; parameter--)
#define rrep(parameter, end) rRep(parameter, 0, end)

int main() {
    int H, W, K;
    cin >> H >> W >> K;
    vector<string> field(H);
    rep(i,H) cin >> field[i];
    vector<vector<vector<mint>>> dp(110, vector<vector<mint>>(110, vector<mint>(210, 0)));
    dp[0][0][K-1] = 1;
    rep(i,H){
        rep(j,W){
            if(i==0 && j==0) continue;
            rrep(k,K){
                // cout << i << ' ' << j << ' ' << k << endl;
                if(field[i][j] == '#'){
                    dp[i][j][k] = 0;
                }
                if(field[i][j] == '.'){
                    dp[i][j][k] = (i==0?0:dp[i-1][j][k]) + (j==0?0:dp[i][j-1][k]);
                }
                if(field[i][j] == 'o'){
                    dp[i][j][k] = (k==K-1?0:(i==0?0:dp[i-1][j][k+1]) + (j==0?0:dp[i][j-1][k+1]));
                }
            }
        }
    }
    // rep(i,H){
    //     rep(j,W){
    //         mint ans = 0;
    //         rep(k,K) ans += dp[i][j][k];
    //         cout << ans << (j!=W-1?' ':'\n');
    //     }
    // }
    // rep(i,H){
    //     rep(k,K){
    //         rep(j,W){
    //             printf("%2d", dp[i][j][k].val());
    //             if(j == W-1 && k == K-1) cout << endl;
    //             else if(j == W-1) cout << " : ";
    //             else cout << ' ';
    //         }
    //     }
    // }
    mint ans = 0;
    rep(i,K) ans += dp[H-1][W-1][i];
    cout << ans << endl;
}

/*

if field[i][j] == '#':
    dp[i][j][k] = 0
if field[i][j] == '.':
    dp[i][j][k] = dp[i-1][j][k] + dp[i][j-1][k]
if field[i][j] == 'o':
    dp[i][j][k] = dp[i-1][j][k-1] + dp[i][j-1][k-1]

*/
0