扫雷游戏(dfs+枚举第一个位置的状态)
扫雷游戏
时间限制: 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;
}
/**/
