結果
問題 | No.2430 Damage Zone |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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] */