結果

問題 No.611 Day of the Mountain
ユーザー e869120e869120
提出日時 2017-12-11 00:51:15
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 1,579 ms / 2,017 ms
コード長 2,403 bytes
コンパイル時間 1,469 ms
コンパイル使用メモリ 79,200 KB
実行使用メモリ 359,888 KB
最終ジャッジ日時 2023-08-20 10:01:47
合計ジャッジ時間 5,027 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 327 ms
359,848 KB
testcase_01 AC 320 ms
359,784 KB
testcase_02 AC 320 ms
359,888 KB
testcase_03 AC 1,579 ms
359,852 KB
testcase_04 AC 3 ms
7,948 KB
testcase_05 AC 3 ms
11,992 KB
testcase_06 AC 6 ms
10,728 KB
testcase_07 AC 4 ms
12,752 KB
testcase_08 AC 3 ms
7,956 KB
testcase_09 AC 2 ms
7,472 KB
testcase_10 AC 2 ms
7,428 KB
testcase_11 AC 3 ms
7,484 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int H, W, a[1009][1009], p[1009][1009], res[1009][1009], mod = 201712111;
int main() {
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			char c; cin >> c;
			if (c == '?')a[i][j] = -1;
			else a[i][j] = (c - '0');
			p[i][j] = a[i][j];
		}
	}
	if (H < W) {
		for (int i = 0; i < max(H, W); i++) {
			for (int j = i + 1; j < max(H, W); j++) { swap(a[i][j], a[j][i]); swap(p[i][j], p[j][i]); }
		}
		swap(H, W);
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) { if (p[i][j] == -1)p[i][j] = 1; res[i][j] = 100009; }
	}
	res[0][0] = p[0][0];
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (i == 0 && j == 0)continue;
			if (i != 0)res[i][j] = min(res[i][j], res[i - 1][j] + p[i][j]);
			if (j != 0)res[i][j] = min(res[i][j], res[i][j - 1] + p[i][j]);
		}
	}
	cout << res[H - 1][W - 1] << endl;
	vector<vector<vector<long long>>>dp(H + 1, vector<vector<long long>>(W + 1, vector<long long>((1 << W), 0LL)));
	dp[0][0][1] = 1;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			for (int k = 0; k < (1 << W); k++) {
				if (dp[i][j][k] == 0)continue;
				int fx = i, fy = j + 1; if (fy == W) { fy = 0; fx++; }
				int bit[17]; for (int l = 0; l < W; l++) { if ((k&(1 << l)) != 0)bit[l] = 1; else bit[l] = 0; }

				bool U1 = true; if (j == 0)U1 = false; else { if (bit[j - 1] == 0)U1 = false; if (res[i][j - 1] + p[i][j] != res[i][j])U1 = false; }
				bool U2 = true; if (bit[j] == 0)U2 = false; else { if (res[i - 1][j] + p[i][j] != res[i][j])U2 = false; }

				if (a[i][j] == -1) {
					if (U1 == true || U2 == true) {
						dp[fx][fy][k | (1 << j)] += dp[i][j][k]; dp[fx][fy][k | (1 << j)] %= mod;
						dp[fx][fy][k - bit[j] * (1 << j)] += dp[i][j][k] * 8LL; dp[fx][fy][k - bit[j] * (1 << j)] %= mod;
					}
					else {
						dp[fx][fy][k - bit[j] * (1 << j)] += dp[i][j][k] * 9LL; dp[fx][fy][k - bit[j] * (1 << j)] %= mod;
					}
				}
				else {
					if (U1 == true || U2 == true) {
						dp[fx][fy][k | (1 << j)] += dp[i][j][k]; dp[fx][fy][k | (1 << j)] %= mod;
					}
					else {
						dp[fx][fy][k - bit[j] * (1 << j)] += dp[i][j][k] * 1LL; dp[fx][fy][k - bit[j] * (1 << j)] %= mod;
					}
				}
			}
		}
	}
	long long ret = 0;
	for (int i = (1 << (W - 1)); i < (1 << W); i++)ret += dp[H][0][i];
	cout << ret % mod << endl;
	return 0;
}
0