「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]);
		}
	}
 }