扫雷游戏

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

题目描述

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

 

输入

第一行，一个整数N（２≤N≤４０），第二行有N个数字（以一个空格相隔），表示右列格子中的数字。输入数据保证正确有解。

 

输出

第一行是N个０、１数字（没有空格相隔），表示左列每格中有无地雷。第二行一个整数，表示地雷总数。

 

样例输入

复制样例数据

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;
}
/**/