結果
問題 | No.2003 Frog on Grid |
ユーザー |
![]() |
提出日時 | 2022-07-29 15:07:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 282 ms / 2,000 ms |
コード長 | 1,149 bytes |
コンパイル時間 | 4,416 ms |
コンパイル使用メモリ | 256,860 KB |
最終ジャッジ日時 | 2025-01-30 14:54:04 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using mint = modint998244353;using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf 1000000001int main() {int H,W,K;cin>>H>>W>>K;vector dp(H,vector<mint>(W,0));vector sum(H,vector<mint>(W,0));vector<string> s(H);rep(i,H)cin>>s[i];rep(i,H){mint cs = 0;if(i!=0)cs += sum[i-1][0];if(i-K-1>=0)cs -= sum[i-(K+1)][0];rep(j,W){mint v = cs;if(i==0&&j==0)v++;if(s[i][j]=='.'){dp[i][j] += v;sum[i][j] += v;}else v = 0;if(i!=0&&j!=W-1)dp[i][j] += dp[i-1][j+1];if(i!=0)sum[i][j] += sum[i-1][j];if(j!=W-1){cs += v;if(j-(K)>=0){int y = j-(K);int x = i;if(y>=0)cs -= dp[x][y];x -= (j+1)-y;y = j+1;if(x>=0 && y<W)cs += dp[x][y];}else{int y = 0;int x = i - ((K)-(j));if(x>=0)cs -= dp[x][y];x -= j+1;y += j+1;if(x>=0&&y<W)cs += dp[x][y];}if(i!=0)cs += sum[i-1][j+1];if(i-(K+1)>=0)cs -= sum[i-(K+1)][j+1];}}}cout<<dp[H-1][W-1].val()<<endl;return 0;}