PKU 1077 Eight

問題

8-パズルの初期盤面が与えられる。
これが解けるならその手順を、そうでないならunsolvableを出力せよ。

方針

幅優先探索。
メモ化にmapを使うと間に合わないのでhashとかを使う。

ソースコード

適当に書いた自作hashmap

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
const char *dirs = "uldr";
char ans[10000];
int len;

template<class K, class V>struct Map{
	ll *hs;
	V *data;
	const static int SZ = 999983;
	Map(){
		hs = new ll[SZ]; data = new V[SZ];
		rep(i, SZ) hs[i] = ~0;
	}
	~Map(){ delete(hs); delete(data); }
	
	ll hash(const K &key) const{
		return key;
	}
	void set(const K &key, const V &value){
		ll h = hash(key), i = h % SZ;
		for(; hs[i] != h && hs[i] != ~0; i = i == SZ - 1 ? 0 : i + 1);
		hs[i] = h;
		data[i] = value;
	}
	const V& get(const K &key) const{
		ll h = hash(key), i = h % SZ;
		for(; hs[i] != h && hs[i] != ~0; i = i == SZ - 1 ? 0 : i + 1);
		if(hs[i] != h) throw 0; //no such key
		return data[i];
	}
	bool contain(const K &key)const{
		ll h = hash(key), i = h % SZ;
		for(; hs[i] != h && hs[i] != ~0; i = i == SZ - 1 ? 0 : i + 1);
		return hs[i] == h;
	}
};

int main()
{
	vi v;
	char c;
	int y, x;
	ll start = 0;
	rep(i, 9){
		cin >> c;
		v.pb(c == 'x' ? 0 : c - '0');
		if(v.back() == 0) y = i / 3, x = i % 3;
		start *= 9; start += v.back();
	}
	Map<ll, int> prev;
	queue<ll> q;
	q.push(start);
	prev.set(start, -1);
	
	while(!q.empty()){
		ll s = q.front(); q.pop();
		bool finish = 1;
		rep(i, 9) v[8 - i] = s % 9, s /= 9;
		
		rep(i, 9){
			if(v[i] != (i + 1) % 9) finish = 0;
			if(v[i] == 0) y = i / 3, x = i % 3;
		}
		if(finish){
			while(1){
				ll s = 0;
				rep(i, 9) s *= 9, s += v[i];
				if(s == start) break;
				
				int d = prev.get(s), ny = y - dy[d], nx = x - dx[d];
				ans[len++] = dirs[d];
				
				swap(v[ny * 3 + nx], v[y * 3 + x]);
				swap(ny, y); swap(nx, x);
			}
			reverse(ans, ans + len);
			cout << ans << endl;
			goto END;
		}
		
		rep(d, 4){
			int ny = y + dy[d], nx = x + dx[d];
			if(ny < 0 || nx < 0 || ny >= 3 || nx >= 3) continue;
			swap(v[ny * 3 + nx], v[y * 3 + x]);
			
			ll nh = 0;
			rep(i, 9) nh *= 9, nh += v[i];
			if(!prev.contain(nh)){
				prev.set(nh, d);
				q.push(nh);
			}
			swap(v[ny * 3 + nx], v[y * 3 + x]);
		}
	}
	cout << "unsolvable" << endl;
	END:;
	return 0;
}