「AOJ121～130」の編集履歴（バックアップ）一覧に戻る

AOJ121～130 - (2011/08/18 (木) 01:24:35) の編集履歴(バックアップ)

---

---

0121　Seven Puzzle

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0121
実行速度を重視したトリッキーなほうを掲載しようかと思ったけど分かりやすい方を掲載。
このコードなら中学生でもわかる。
速度重視は日数がたってから読んでみると自分で読んでも分かりづらい。

#include<stdio.h>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
std::map<std::string,int> states;
int ds[]={-4,4,-1,1};
void setData(){
std::string s="01234567";
std::queue<std::string> perm;
perm.push(s);
states[s]=0;
int p,np,tern;

while(perm.empty()==false){
	s=perm.front();
	perm.pop();
	tern=states[s];
	p=s.find('0',0);
	for(int i=0;i<4;i++){
		np=p+ds[i];
		if((np==3 && p==4)||(np==4 && p==3) ||np<0 || 7<np)continue;
		std::swap(s[p],s[np]);
		if(states.find(s)==states.end()){
			states[s]=tern+1;
			perm.push(s);
		}
		std::swap(s[p],s[np]);
	}
}
}
int main(){
setData();
int num;
std::string b="01234567";
while(scanf("%d",&num)!=EOF){
	b[0]=num+'0';
	for(int i=1;i<8;i++){
		scanf("%d",&num);
		b[i]=num+'0';
	}
	if(states.find(b)!=states.end()){
		printf("%d\n",states[b]);
	}
}
}