結果
問題 |
No.2430 Damage Zone
|
ユーザー |
|
提出日時 | 2023-08-18 22:11:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 50 ms / 2,000 ms |
コード長 | 903 bytes |
コンパイル時間 | 4,239 ms |
コンパイル使用メモリ | 257,752 KB |
最終ジャッジ日時 | 2025-02-16 10:10:21 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using mint = atcoder::modint998244353; using namespace std; int dx[2] = {1, 0}; int dy[2] = {0, 1}; int main() { int H, W, K; cin >> H >> W >> K; vector<string> S(H); for (int i = 0; i < H; i++){ cin >> S[i]; } vector<vector<vector<mint>>> dp(H, vector<vector<mint>>(W, vector<mint>(K + 1))); dp[0][0][K] = 1; for (int i = 0; i < H; i++){ for (int j = 0; j < W; j++){ for (int k = 1; k <= K; k++){ for (int l = 0; l < 2; l++){ int px = i + dx[l], py = j + dy[l]; if (0 <= px and px < H and 0 <= py and py < W and S[px][py] != '#'){ if (S[px][py] == '.'){ dp[px][py][k] += dp[i][j][k]; } else { if (k > 1){ dp[px][py][k - 1] += dp[i][j][k]; } } } } } } } mint ans = 0; for (int i = 1; i <= K; i++){ ans += dp[H - 1][W - 1][i]; } cout << ans.val() << '\n'; }