結果
問題 | No.611 Day of the Mountain |
ユーザー |
![]() |
提出日時 | 2017-12-02 21:08:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 246 ms / 2,017 ms |
コード長 | 1,613 bytes |
コンパイル時間 | 939 ms |
コンパイル使用メモリ | 71,772 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-28 03:43:31 |
合計ジャッジ時間 | 2,600 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 9 |
ソースコード
#include <string> #include <vector> #include <iostream> #include <algorithm> using namespace std; const int inf = 1012345678; const int mod = 201712111; int H, W, a[509], b[509], dist[509], dp[4194313], dpn[4194313]; string s[509]; void input() { cin >> H >> W; for (int i = 0; i < H; i++) cin >> s[i]; } void initialize() { for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { a[(H >= W ? i * W + j : j * H + i)] = (s[i][j] == '?' ? 0 : s[i][j] - 48); } } if (H < W) swap(H, W); for (int i = 0; i < H * W; i++) { b[i] = (a[i] == 0 ? 1 : a[i]); } } void calc_dist() { for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { dist[i * W + j] = b[i * W + j] + (i + j == 0 ? 0 : min(i > 0 ? dist[i * W + j - W] : inf, j > 0 ? dist[i * W + j - 1] : inf)); } } } int solve() { dp[1] = 1; int sb = (1 << W) - 1; for (int i = 0; i < H * W - 1; i++) { for (int j = 0; j < 1 << W; j++) { bool flag = ((j >> (W - 1)) && dist[i - W + 1] + b[i + 1] == dist[i + 1]) || ((j & 1) && i % W + 1 != W && dist[i] + b[i + 1] == dist[i + 1]); dpn[(j * 2 + 1) & sb] += flag ? dp[j] : 0; dpn[(j * 2) & sb] = (dpn[(j * 2) & sb] + dp[j] * ((flag ? 0 : 1) + (a[i + 1] == 0 ? 8 : 0))) % mod; if (dpn[(j * 2 + 1) & sb] >= mod) dpn[(j * 2 + 1) & sb] -= mod; } for (int j = 0; j < 1 << W; j++) { dp[j] = dpn[j]; dpn[j] = 0; } } int ret = 0; for (int i = 1; i < 1 << W; i += 2) { ret += dp[i]; if (ret >= mod) ret -= mod; } return ret; } int main() { input(); initialize(); calc_dist(); int ret = solve(); cout << dist[H * W - 1] << '\n' << ret << '\n'; return 0; }