結果

問題 No.611 Day of the Mountain
コンテスト
ユーザー square1001
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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