AOJ Problem 0190 : Eleven Puzzle

問題文:404 Not Found

両側探索とかしてもメモリ死ぬしTLEするんで適当に枝狩しましょう的な問題。

「正しい位置との距離+現在にたどり着くまでのコスト>20」で枝狩した。前やったとき両側探索で死んだ。正しい0の位置は考慮せずに枝狩して通った。(むしろしない方が良い。)

テーブル化の重要さを学ぶ。

#include <iostream>
#include <map>
#include <queue>
#include <cstdlib>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int to[13][5] = {
	{2,-1},
	{2,5,-1},
	{0,1,3,6,-1},
	{2,7,-1},
	{5,-1},
	{1,4,6,9,-1},
	{2,5,7,10,-1},
	{3,6,8,11,-1},
	{7,-1},
	{5,10,-1},
	{6,9,11,12},
	{7,10,-1},
	{10,-1}
};
int X[]={2,1,2,3,0,1,2,3,4,1,2,3,2};
int Y[]={0,1,1,1,2,2,2,2,2,3,3,3,4};

int solve(vector<int> data){
	queue< vector<int> > Q;
	map<vector<int>,int> done;
	Q.push(data);
	done[Q.front()] = 0;
	
	while(Q.size()){
		vector<int> q = Q.front(); Q.pop();
		int dif = 0;
		rep(i,13)if(q[i])dif += abs(X[q[i]]-X[i])+abs(Y[q[i]]-Y[i]);
		if(dif==0)return done[q];;
		if(dif+done[q]>20)continue;
		int curcost = done[q];
		rep(x,13){
			if(q[x] == 0){
				rep(i,5){
					if(!~to[x][i])break;
					swap(q[x],q[to[x][i]]);
					if(done.find(q) == done.end() ){
						done[q] = curcost+1;
						Q.push(q);
					}
					swap(q[x],q[to[x][i]]);
				}
			}
		}
	}
	return 21;
}
int main(){
	vector<int> data(13);
	while(1){
		rep(i,13)if(!(cin >> data[i]))return 0;
		int ans = solve(data);
		if(ans > 20)cout << "NA" << endl;
		else cout << ans << endl;
	}
}