扫雷游戏(dfs+枚举第一个位置的状态)

扫雷游戏

时间限制: 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;
}
/**/

 

全部评论

相关推荐

我是没经验的毕业生,这啥情况啊会不会是hr在刷kpi
JamesGosli...:字节boss属于是群发了,我都快入职字节了,其他部门还在和我boss打招呼
点赞 评论 收藏
分享
zYvv:双一流加大加粗再标红,然后广投。主要是获奖荣誉不够,建议开始不用追求大厂,去别的厂子刷下实习。
点赞 评论 收藏
分享
牛客刘北:如果暑期实习是27届的话,你要晚一年才会毕业,企业为什么会等你呢?要搞清时间逻辑呀!27届现在实习只能是在暑假实习,这是日常实习,不是暑期实习。所以多去投日常实习吧,暑期实习肯定不会要你的
点赞 评论 收藏
分享
看到这个内容真是闹麻了。。。。。。现在有了AI以后很多人面试都会作弊吗?&nbsp;那对老老实实面试的人岂不是不公平....
程序员牛肉:公平那是对小孩子讲的童话故事,成年人的世界只有能不能接受失败的后果。 你要是能接受面试作弊被发现之后多家公司联合永久拉黑的后果,你就搞。
你找工作的时候用AI吗?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务