Problem 0121 : Seven Puzzle

404 Not Found

やっと解けたっていうか昔から一応正しい答え出すソースあったんだけど、ずっとTLEしてた。

原因は毎回手数を探索していたからで、最初に"01234567"から遷移できる全ての状態に対する手数をメモってから、それを出力するようにしたら高速化した。

#include <iostream>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;
int di[]={1,-1,4,-4};
bool check(int n){return n<8 && n>=0;}

int main(){
	string t;
	map<string,int> done;
	queue<string> Q;
	Q.push("01234567");
	while(!Q.empty()){
		string q = Q.front();Q.pop();
		int x = q.find("0");
		for(int i=0;i<4;i++){
			if(x%4==0 && i==1)continue;
			if(x%4==3 && i==0)continue;
			if(!check(x+di[i]))continue;
			t = q , swap(t[x],t[x+di[i]]);
			if(done.find(t)!=done.end() )continue;
			Q.push(t); done[t] = done[q] + 1;
		}
	}
	while(getline(cin,t)){
		t.erase(remove(t.begin(),t.end(),' '),t.end());
		cout << done[t] << endl;
	}
}