結果
問題 | No.3071 Double Speedrun |
ユーザー |
![]() |
提出日時 | 2025-03-21 22:59:59 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,448 ms / 6,000 ms |
コード長 | 1,775 bytes |
コンパイル時間 | 6,585 ms |
コンパイル使用メモリ | 332,988 KB |
実行使用メモリ | 10,492 KB |
最終ジャッジ日時 | 2025-03-21 23:00:34 |
合計ジャッジ時間 | 34,734 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
#include <atcoder/all> #include <bits/stdc++.h> using namespace std; using mint = atcoder::modint998244353; #define rep(i, a, b) for (int i = (a); i < (b); i++) int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int h, w; cin >> h >> w; vector<string> s(h); rep(i, 0, h) cin >> s[i]; int N = h * w; unordered_map<long long, mint> dp, ndp; dp.reserve(1 << 16); ndp.reserve(1 << 16); // 初期状態:flattened indices を key にパック (first*N + second) dp[(long long)1 * N + w] = 1; rep(dist, 1, h + w - 3) { ndp.clear(); for (auto &it : dp) { long long key = it.first; mint v = it.second; int p = key / N, q = key % N; int ai = p / w, aj = p % w; int bi = q / w, bj = q % w; rep(i, 0, 2) rep(j, 0, 2) { int nai = ai + i, naj = aj + 1 - i; int nbi = bi + j, nbj = bj + 1 - j; if (nai >= h || naj >= w || nbi >= h || nbj >= w) continue; if (s[nai][naj] == '#' || s[nbi][nbj] == '#') continue; if (nai == nbi && naj == nbj) continue; if (nai == bi && naj == bj) continue; if (ai == nbi && aj == nbj) continue; int np = nai * w + naj; int nq = nbi * w + nbj; long long newkey = (long long)np * N + nq; ndp[newkey] += v; } } dp.swap(ndp); } if (dp.empty()) { cout << 0 << "\n"; } else { for (auto &it : dp) { cout << it.second.val() << "\n"; } } return 0; }