結果

問題 No.611 Day of the Mountain
ユーザー square1001square1001
提出日時 2017-12-02 21:08:51
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 223 ms / 2,017 ms
コード長 1,613 bytes
コンパイル時間 783 ms
コンパイル使用メモリ 70,668 KB
実行使用メモリ 6,132 KB
最終ジャッジ日時 2023-08-18 20:07:29
合計ジャッジ時間 2,614 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 180 ms
5,888 KB
testcase_01 AC 177 ms
6,132 KB
testcase_02 AC 180 ms
5,856 KB
testcase_03 AC 223 ms
6,116 KB
testcase_04 AC 2 ms
5,328 KB
testcase_05 AC 2 ms
5,436 KB
testcase_06 AC 2 ms
5,612 KB
testcase_07 AC 2 ms
5,344 KB
testcase_08 AC 2 ms
5,324 KB
testcase_09 AC 2 ms
5,492 KB
testcase_10 AC 2 ms
5,328 KB
testcase_11 AC 2 ms
5,372 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0