結果

問題 No.2430 Damage Zone
ユーザー 👑 Nachia
提出日時 2023-08-18 21:29:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 29 ms / 2,000 ms
コード長 1,027 bytes
コンパイル時間 963 ms
コンパイル使用メモリ 84,660 KB
最終ジャッジ日時 2025-02-16 09:37:19
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <atcoder/modint>
using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
const i64 INF = 1001001001001001001;

using Modint = atcoder::static_modint<998244353>;

int main(){
    int H, W, K; cin >> H >> W >> K; K--;
    vector<string> S(H); rep(y,H) cin >> S[y];
    vector dp(K+1, vector(H, vector(W, Modint(0))));
    rep(k,K+1) dp[k][0][0] = 1;
    for(int k=K; k>=0; k--) rep(y,H) rep(x,W){
        char c = S[y][x];
        if(c == '#') continue;
        int off = (c == 'o' ? 1 : 0);
        if(k+off > K) continue;
        if(y) dp[k][y][x] += dp[k+off][y-1][x];
        if(x) dp[k][y][x] += dp[k+off][y][x-1];
    }
    cout << dp[0][H-1][W-1].val() << endl;
    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;

0