扫雷游戏

时间限制: 1 Sec  内存限制: 128 MB

题目描述

小Q空的时候挺喜欢玩玩电脑游戏的。自从编程技术提高后,他就想,要是自己也能开发出一款游戏来,那该多好啊!不过,小Q也不着急,先练好基本功再说。Windows中就有一款叫扫雷的小游戏,挺好玩的,不过想编出一个来,还真不容易。小Q就自己设想了一种简单的扫雷游戏:在n行2列的方格棋盘上,左列某些方格内埋有地雷,而右列每个方格中都有一个数字(0~3),第I格的数字表示:左列第I-1、I、I+1格(即:上、中、下三格)中埋雷的总数。如下所示:左图是初始状态,右图是扫雷完成状态(插小旗的方格内有雷)。
 
你的任务是:根据右列的数字分析出左列格子中的地雷(0表示无雷,1表示有雷),并且统计出左列格子中地雷的总数。
小Q想,如果这样的任务能完成了,相信编出更复杂的扫雷游戏也就为期不远了。

 

输入

第一行,一个整数N(2≤N≤40),第二行有N个数字(以一个空格相隔),表示右列格子中的数字。输入数据保证正确有解。

 

输出

第一行是N个0、1数字(没有空格相隔),表示左列每格中有无地雷。第二行一个整数,表示地雷总数。

 

样例输入

复制样例数据

7
1 2 3 2 2 2 2

样例输出

0111011
5
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n;
int a[55], ans[55];

bool dfs(int x){
	if(x == n){
		int num = ans[x] + ans[x - 1];
		if(num == a[x]){
			return true;
		}
		return false;
	}
	int num = ans[x - 1] + ans[x];
	if(num == a[x]){
		ans[x + 1] = 0;//没初始化就别省
		return dfs(x + 1);
	}else if(num > a[x]){
		return false;
	}else{
		ans[x + 1] = 1, num++;
		if(num < a[x]) return false;
		return dfs(x + 1);
	}
	return false;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 0; i < 4; i++){//表示00,01,10,11
		int num = (i & 1) + (i >> 1 & 1);
		if(num == a[1]){
			ans[1] = (i & 1), ans[2] = (i >> 1 & 1);
			if(dfs(2)) break;
		}
	}
	int sum = 0;
	for (int i = 1; i <= n; i++){
		printf("%d", ans[i]);
		if(ans[i] == 1) sum++;
	}
	printf("\n%d\n", sum);

	return 0;
}
/**/