結果
問題 | No.3071 Double Speedrun |
ユーザー |
![]() |
提出日時 | 2025-03-21 22:33:04 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,045 ms / 6,000 ms |
コード長 | 1,530 bytes |
コンパイル時間 | 3,381 ms |
コンパイル使用メモリ | 284,168 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-21 22:33:24 |
合計ジャッジ時間 | 19,035 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint> using namespace std; using namespace atcoder; using ll = long long; using mint = modint998244353; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); int H, W, y1, y2, nx1, ny1, nx2, ny2; cin >> H >> W; vector<string> S(H); int dx[2] = {0, 1}, dy[2] = {1, 0}; for (int i=0; i<H; i++) cin >> S[i]; vector dp(H, vector<mint>(H)); dp[0][0] = 1; auto check=[&](int x, int y){ return 0 <= x && x < H && 0 <= y && y < W; }; for (int i=0; i<=H+W-4; i++){ vector pd(H, vector<mint>(H)); for (int x1=0; x1<H; x1++){ y1 = i-x1; if (!check(x1, y1)) continue; for (int x2=0; x2<H; x2++){ y2 = i-x2; if (!check(x2, y2)) continue; for (int j=0; j<2; j++){ nx1 = x1+dx[j]; ny1 = y1+dy[j]; if (!check(nx1, ny1)) continue; if (S[nx1][ny1] == '#') continue; for (int k=0; k<2; k++){ nx2 = x2+dx[k]; ny2 = y2+dy[k]; if (!check(nx2, ny2)) continue; if (S[nx2][ny2] == '#') continue; if ((nx1 == nx2) && (ny1 == ny2)) continue; pd[nx1][nx2] += dp[x1][x2]; } } } } swap(dp, pd); } cout << ((dp[H-1][H-2]+dp[H-2][H-1]) / 2).val() << endl; return 0; }