游客 注册 | 登录
中文 | En

3125 - 排排坐

通过次数

0

提交次数

0

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

小B喜欢在蓝心网玩游戏,一天他玩到了这个游戏: http://boolean93.blog.163.com/blog/static/164414291201010445255950/ ，他感觉 非常好玩....于是他就YY出了一个类似的简易模型.... 游戏规则：每次点击一个小朋友，他和他的周围的小朋友都会改变状态（蹲下的变成 了站起来的，站起来的变成了蹲下的）

我们将这个抽象成如下图所示的 1*N的图.对于一个单元格,黑色表示小朋友是站起来的, 反之,蹲下的小朋友是是白色的.Source表示初始状态,Target 表示目标状态.


<img src="http://tk.hustoj.com:80/attached/image/20140901/20140901081332_42852.png" alt="" />


现在小B有点偷懒,希望作为神牛的你帮小B算出初始状态到目标状态的最少点击数.&nbsp;


<br />

题目输入

第一行为N表示小朋友的个数. N<=10 

第二行是初始状态,有N个数,每个数不是0就是1.(0表示小朋友是蹲下的,1表示小朋友 是站起来的) 

第三行的结构跟第二行类似,表示目标状态. 

题目输出

一个数 X,表示初始状态到目标状态的最少点击数。

 如果无法到达目标,则请输出"Boring"  


PS:只需要点击第二个和第六个点即可。<br />
<div>
	<br />
</div>

输入/输出样例

输入格式

9 
0 1 0 0 0 1 0 0 0 
1 0 1 0 1 0 1 0 0

输出格式

2

C++解答

#include<cstdio>
#include<cmath>
const int Max=4028800;
int nodedir=0,exdir=0,n;  
bool flag=true,visit[60353607]={0};
struct Node{
	bool a[10];int step;
} map[Max],temp,end;
int hash(Node &x){
	int sum=0;
	for(int i=0;i<n;i++)
	sum+=x.a[i]*pow(6,i);
	return sum;
}
bool equal(Node &x,Node &y){
	for(int i=0;i<n;i++)
	if(x.a[i]!=y.a[i]) return false;
	return true;
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	scanf("%d",&map[0].a[i]);
	for(int i=0;i<n;i++)
	scanf("%d",&end.a[i]);
	map[0].step=0;
	while(nodedir<=exdir&&exdir<Max&&flag){
		for(int i=0;i<n;i++){
			temp=map[nodedir];temp.a[i]=!temp.a[i];
			if(i==0)	 temp.a[i+1]=!temp.a[i+1];
			else if(i==n-1) temp.a[i-1]=!temp.a[i-1];
			else {temp.a[i-1]=!temp.a[i-1];temp.a[i+1]=!temp.a[i+1];
			}
			temp.step++;
			if(equal(temp,end)){
				printf("%d\n",temp.step);
				flag=false; break;
			}
			if(!visit[hash(temp)]){
				visit[hash(temp)]=true;
				map[++exdir]=temp;
			}
		}
		nodedir++;
	}
	if(flag)  printf("Boring\n");
	return 0;
}
请先登陆