問題文: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; } }