【SSL 1457】翻币问题【广搜 BFS】

Description

有N个硬币(6<=N<=20000)全部正面朝上排成一排，每次将其中5个硬币翻过来放在原位置，直到最后全部硬币翻成反面朝上为止。试编程找出步数最少的翻法，输出最少步数及翻法。

Input

从键盘输入一个正整数N(6<=N<=20000)，表示硬币的数量。

Output

第1行：一个整数，表示最少步数

第2行至最后一行：先是一个整数，表示步骤序号（从0开始编号），后接一个":"，再接当前硬币的状态（用一个整数表示正面朝上的硬币的个数）

Sample Input

Sample Output

0:6   (第0步结果:6个硬币正面朝上)
1:1   (第1步结果:1个硬币正面朝上)
2:4   (第2步结果:4个硬币正面朝上)
3:3   (第3步结果:3个硬币正面朝上)
4:2   (第4步结果:2个硬币正面朝上)
5:5   (第5步结果:5个硬币正面朝上)
6:0   (第6步结果:0个硬币正面朝上)
6     (最少用6步实现全部反面朝上)
           

Hint

只输出最少次数,其变化过程仅作参考

分析：

这道题是一道BFS，关键点(及难点)在于找到翻币的规律或找出从当前状态如何变化到下一状态：

state[tail]:=state[head]-i*2+5;后面的就很简单了。

代码部分：

#include<iostream>
#include<cstdio>
using namespace std;
int n,s,stat[10001],head,fa[10001];
bool a[10001];
void print(int x){
	if(x==0) return;
	print(fa[x]);
	s++;
}
void bfs(){  //广搜
	int tail=1,head=0;
	a[n]=1;
	stat[1]=n;fa[1]=0;
	do{
		head++;
		for(int i=0;i<=5;i++){
			if(stat[head]>=i&&n-stat[head]>=5-i){
				tail++;
				fa[tail]=head;
				stat[tail]=stat[head]-i+5-i; //关键点
				if(!a[stat[tail]]) a[stat[tail]]=1;
					else tail--;
				if(stat[tail]==0) 
				{
					print(tail);  //输出单写函数
					return;
				}
			} 
		}
	}while(head<tail);
}
int main(){
	ios::sync_with_stdio(false);  //快读
	cin>>n;
	bfs();
	cout<<s-1;
	return 0;
}