【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;
}