結果

問題 No.611 Day of the Mountain
ユーザー Sebastian KingSebastian King
提出日時 2017-12-11 01:14:52
言語 C++11
(gcc 11.4.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,397 bytes
コンパイル時間 1,668 ms
コンパイル使用メモリ 145,996 KB
実行使用メモリ 13,748 KB
最終ジャッジ日時 2023-08-20 10:02:43
合計ジャッジ時間 2,970 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 RE -
testcase_04 WA -
testcase_05 RE -
testcase_06 AC 5 ms
12,560 KB
testcase_07 AC 4 ms
13,748 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘ll upd(ll&, ll)’:
main.cpp:31:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int MM = 201712111;
const double eps = 1e-8;
const int MAXN = 2000 + 10;

int n, m;

void prework(){

}

void read(){

}

int a[MAXN][MAXN];
ll d[MAXN][MAXN];
const ll INF = 1ll << 60;
char s[MAXN];

ll f[20][131072];

ll upd(ll &x, ll y){
	x = (x + y) % MM;
}

void solve(int casi){
//	cout << "Case #" << casi << ": ";
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++){
		scanf("%s", s + 1);
		for (int j = 1; j <= m; j++)
			a[i][j] = ((s[j] == '?') ? 0 : (s[j] - '0'));
	}
	if (m >= 18){
		// m > n
		for (int i = 1; i <= m; i++)
			for (int j = i + 1; j <= m; j++)
				swap(a[i][j], a[j][i]);
		swap(n, m);
	}
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++)
			d[i][j] = INF;
	d[1][1] = (a[1][1] == 0) + a[1][1];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++){
			if (i != 1 || j != 1){
				d[i][j] = min(d[i-1][j], d[i][j-1]) + a[i][j] + (a[i][j] == 0);
			}
		}
	printf("%d\n", d[n][m]);
	if (m == 1){
		puts("1");
		return ;
	}
	int o = 1 << m;
	for (int i = 0; i < o; i++)
		f[1][i] = 0;
	f[1][1] = 1;
	int oo = o - 1;
	for (int cnt = 2; cnt <= n * m; cnt++){
		int x = (cnt - 1) / m + 1;
		int y = (cnt - 1) % m + 1;
		int py = (y == 1 ? m : y - 1);
		for (int i = 0; i < o; i++){
			f[y][i] = 0;
			//for (int j = 0; j < m; j++)
			//	f[y][i][j] = 0;
		}
		//cout << cnt << ' ' << x << ' ' << y << ' ' << py << endl;
		if (y == 1){
			if (a[x][y] == 0){
				for (int i = 0; i < o; i++){
					if ((d[x-1][y]+1==d[x][y] && ((i >> (y - 1)) & 1))){
						upd(f[y][i|(1<<(y-1))], f[py][i]);
						upd(f[y][i&(oo^(1<<(y-1)))], f[py][i]*8);
					}
					else{
						upd(f[y][i&(oo^(1<<(y-1)))], f[py][i]*9);
					}
				}
			}
			else{
				for (int i = 0; i < o; i++){
					if ((d[x-1][y]+a[x][y]==d[x][y] && ((i >> (y - 1)) & 1))){
						upd(f[y][i|(1<<(y-1))], f[py][i]);
					}
					else{
						upd(f[y][i&(oo^(1<<(y-1)))], f[py][i]);
					}
				}
			}
		}
		else{
			if (a[x][y] == 0){
				for (int i = 0; i < o; i++){
					if ((d[x-1][y]+1==d[x][y] && ((i >> (y - 1)) & 1)) || (d[x][y-1]+1==d[x][y] && ((i >> (y - 2)) & 1))){
						upd(f[y][i|(1<<(y-1))], f[py][i]);
						upd(f[y][i&(oo^(1<<(y-1)))], f[py][i]*8);
						/*
						for (int j = 0; j < m; j++){
							if (j != y - 1){
								upd(f[y][i][j], f[py][i][j]);
								upd(f[y][i^(1<<(y-1))], f[py][i][j]*8);
							}
						}
						upd(f[y][i][y-1], f[py][i][y-1] + f[py][i][y-2]);
						upd(f[y][i^(1<<(y-1))], )*/
					}
					else{
						upd(f[y][i&(oo^(1<<(y-1)))], f[py][i]*9);
					}
				}
			}
			else{
				for (int i = 0; i < o; i++){
					if ((d[x-1][y]+a[x][y]==d[x][y] && ((i >> (y - 1)) & 1)) || (d[x][y-1]+a[x][y]==d[x][y] && ((i >> (y - 2)) & 1))){
						upd(f[y][i|(1<<(y-1))], f[py][i]);
						//upd(f[y][i&(o^(1<<(y-1)))], f[py][i]*8);
					}
					else{
						upd(f[y][i&(oo^(1<<(y-1)))], f[py][i]);
					}
				}
			}
		}
		//for (int i = 0; i < o; i++)
		//	cout << f[y][i] << ' '; cout << endl;
	}
	
	//for (int i = 0; i < o; i++)
	//	cout << f[m][i] << ' '; cout << endl;
	
	ll ans = 0;
	for (int i = 0; i < o; i++)
		if ((i >> (m - 1)))
			upd(ans, f[m][i]);
	printf("%lld\n", ans);
}

void printans(){

}


int main(){
//	std::ios::sync_with_stdio(false);
	prework();
	int T = 1;
//	cin>>T;
	for(int i = 1; i <= T; i++){
		read();
		solve(i);
		printans();
	}
	return 0;
}
0