結果
問題 | 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';}