PKU 1077-Eight

問題概要

8パズルを解け

解法

最良優先探索で適当な解を探す．最短解じゃなくても良いので簡単．

実装(C++)

#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
using namespace std;

typedef long long int lli;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)

int pow[9];
char d[4]={'l','r','u','d'};
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
struct State{
	char MAP[3][3];
	int hash;
	int zx,zy;
	int md;//
	void hash_calc(){
		hash=0;
		for(int i=0;i<9;i++){
			hash+=MAP[i%3][i/3]*pow[i];
		}
		md=0;
		for(int x=0;x<3;x++)for(int y=0;y<3;y++){
			int tx,ty;
			if(MAP[x][y]!=0){
				tx=(MAP[x][y]-1)%3,
				ty=(MAP[x][y]-1)/3;
			}else{
				tx=ty=2;
			}
			md+=abs(x-tx)+abs(y-ty);
		}
		for(int x=0;x<3;x++)for(int y=0;y<3;y++){
			if(MAP[x][y]==0){
				zx=x;zy=y;
			}
		}
	}
	bool next(int direction){
		int nx=zx+dx[direction],ny=zy+dy[direction];
		if(!(nx>=0&&nx<3&&ny>=0&&ny<3))return false;
		md-=abs(nx-(MAP[nx][ny]-1)%3)+abs(ny-(MAP[nx][ny]-1)/3);
		md-=abs(zx-2)+abs(zy-2);

		hash-=MAP[nx][ny]*pow[nx+ny*3];
		hash-=MAP[zx][zy]*pow[zx+zy*3];

		swap(MAP[nx][ny],MAP[zx][zy]);
		swap(zx,nx);swap(ny,zy);

		hash+=MAP[nx][ny]*pow[nx+ny*3];
		hash+=MAP[zx][zy]*pow[zx+zy*3];

		md+=abs(nx-(MAP[nx][ny]-1)%3)+abs(ny-(MAP[nx][ny]-1)/3);
		md+=abs(zx-2)+abs(zy-2);


		return true;
	}
};
bool operator<(const State &a,const State&b){
	return a.md>b.md;
}
ostream &operator<<(ostream &os,const State &a){
	REP(y,3){
		REP(x,3){
			cout<<" "<<(int)a.MAP[x][y];
		}
		cout<<endl;
	}
	return os;
}
map<int,int> ac;
map<int,int> back;

int main(){
	pow[0]=1;
	for(int i=0;i<8;i++){
		pow[i+1]=pow[i]*9;
	}
	State start;
	for(int i=0;i<9;i++){
		string tmp;
		cin>>tmp;
		if(tmp=="x")tmp="0";
		start.MAP[i%3][i/3]=atoi(tmp.c_str());
	}
	//cout<<start<<endl;

	start.hash_calc();
	//cout<<start.hash<<endl;
	ac[start.hash]=0;
	priority_queue<State> que;
	que.push(start);
	while(!que.empty()){
		State st=que.top();que.pop();
		//cout<<st<<st.md<<endl;
		//out<<st.zx<<","<<st.zy<<endl;
		int now=ac[st.hash];
		if(st.md==0){
			string res=string(now,' ');
			for(int i=0;i<now;i++){
				res[now-i-1]=d[back[st.hash]];
				st.next(back[st.hash]^1);
			}
			cout<<res<<endl;
			return 0;
		}
		for(int i=0;i<4;i++){
			State next(st);
			if(next.next(i)){
				if(ac.find(next.hash)==ac.end()){
					ac[next.hash]=now+1;
					back[next.hash]=i;
					que.push(next);
				}
			}
		}
	}
	cout<<"unsolvable"<<endl;
	return 0;
}