/* *************************** Problem: UVa 652 Eight Author: chengouxuan Date: 2011-02-27 Status: Time Limit Exceeded *************************** */ #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cassert> using std::string; using std::cin; using std::cout; using std::vector; using std::swap; //#undef _DEBUG #define ID_NIL 0 #define HASH_TABLE_BUCKET_SIZE (1 << 12) #define HEAP_IND_NIL 0 #define IND_NIL -1 #define INT_INF 0x3fffffff class Direction { public: int dRow; int dCol; Direction(int r = 0, int c = 0): dRow(r), dCol(c) {} }; vector <Direction> dir(4); vector <char> opChar(4); enum Operation { up = 0, down, left, right, nil }; class Initializer { public: Initializer() { dir[down] = Direction(1, 0); dir[right] = Direction(0, 1); dir[up] = Direction(-1, 0); dir[left] = Direction(0, -1); opChar[down] = 'd'; opChar[right] = 'r'; opChar[up] = 'u'; opChar[left] = 'l'; } }; Initializer init; class State { public: /* *************************************************** x xxxx xxx xxx xxx xxx xxx xxx xxx xxx xxx u xPos 9 8 7 6 5 4 3 2 1 The storage of a 32 bit integer for parId and id, where u means unused, xPos means the position of x, i means the ith tile's number. *************************************************** */ int parId; int id; Operation oper; int f, g; int heapInd; State(): parId(ID_NIL), id(ID_NIL), oper(nil), f(0), g(0), heapInd(HEAP_IND_NIL) {} void SetF() { int xPos = id >> 27; int h = 0; for(int i=0; i<9; ++i) { if(i == xPos) continue; int tile = (07 & (id >> (i * 3))); int r = tile / 3; int c = tile % 3; int oR = i / 3; int oC = i % 3; h += abs(r - oR) + abs(c - oC); } f = g + h; } void GetMat() { int xPos; id = 0; int n = 0; while(n < 9) { char c = cin.get(); if(! cin) exit(0); if(c == 'x') { xPos = n; ++n; } else if('1' <= c && c <= '8') { id |= ((c - '0' - 1) << n * 3); ++n; } } id |= (xPos << 27); g = 0; parId = ID_NIL; oper = nil; SetF(); } State Move(Operation op) { int oldXPos = id >> 27; int newRow = oldXPos / 3 + dir[op].dRow; int newCol = oldXPos % 3 + dir[op].dCol; if(! (0 <= newRow && newRow < 3 && 0 <= newCol && newCol < 3)) return *this; State ret = *this; int newXPos = newRow * 3 + newCol; // tile to be moved int tile = (id >> (newXPos * 3)) & 07; // set the moved tile to its new position ret.id |= (tile << (oldXPos * 3)); // set the new position of x to be 0 ret.id &= (~(07 << (newXPos * 3))); // reset xPos ret.id &= (~(0xf << 27)); ret.id |= (newXPos << 27); ret.g = g + 1; ret.parId = id; ret.SetF(); ret.oper = op; ret.heapInd = HEAP_IND_NIL; return ret; } bool IsSolvable() const { // in reverse order number int rev = 0; int xPos = id >> 27; for(int i=0; i<9; ++i) { if(i == xPos) continue; int tile = (id >> (i * 3)) & 07; for(int k=0; k<i; ++k) { if(k == xPos) continue; int tileK = (id >> (k * 3)) & 07; if(tileK > tile) ++rev; } } return rev % 2 == 0; } static size_t NextStSize() { return dir.size(); } bool IsTargetState() const { // 010076543210 is target state's id return 010076543210 == id; } }; class HashTable { public: vector <vector <State> > bucket; size_t size; HashTable(size_t bucketSize = HASH_TABLE_BUCKET_SIZE): bucket(bucketSize), size(0) {} // not tested, I think the hash function is ok. int IDHash(int id) { int h = 0; h ^= id >> 16; h ^= id >> 15; h ^= id >> 14; h ^= id >> 13; h ^= id >> 12; h ^= id >> 11; h ^= id >> 10; h ^= id >> 9; h ^= id >> 8; h ^= id >> 7; h ^= id >> 6; h ^= id >> 5; h ^= id >> 4; h ^= id >> 3; h ^= id >> 2; h ^= id >> 1; h ^= id; return h % bucket.size(); return ((id >> 8) ^ (id >> 6) ^ (id >> 4) ^ (id >> 2) ^ (id)) % bucket.size(); } int IndexInBucket(int b, int id) { for(size_t i=0; i<bucket[b].size(); ++i) { if(bucket[b][i].id == id) return i; } return IND_NIL; } State FindByID(int id) { int h = IDHash(id); int i = IndexInBucket(h, id); if(i != IND_NIL) return bucket[h][i]; return State(); } void UpdateState(const State &newSt) { int h = IDHash(newSt.id); int i = IndexInBucket(h, newSt.id); if(i != IND_NIL) bucket[h][i] = newSt; } bool IsInTable(int id) { return FindByID(id).id == id; } void Insert(const State &st) { int h = IDHash(st.id); bucket[h].push_back(st); ++size; } void Delete(const State &st) { int h = IDHash(st.id); int i = IndexInBucket(h, st.id); if(i != IND_NIL) { swap(bucket[h][i], const_cast <State &> (bucket[h].back())); bucket[h].pop_back(); --size; } } #ifdef _DEBUG double ASL() { if(size == 0) return 0; double asl = 0; for(size_t i=0; i<bucket.size(); ++i) { int n = bucket[i].size(); asl += n * (n + 1) / 2; } asl /= size; return asl; } #endif }; class MinHeap { public: vector <State> vecSt; HashTable hashTab; MinHeap(): vecSt(1), hashTab(1 << 12) {} int ParentInd(int ind) { return ind / 2; } int LChildInd(int ind) { return ind * 2; } int RChildInd(int ind) { return ind * 2 + 1; } #ifdef _DEBUG void CheckMinHeap() { for(size_t i=1; i<vecSt.size(); ++i) { int parInd = ParentInd(i); assert(parInd == HEAP_IND_NIL || vecSt[parInd].f <= vecSt[i].f); assert(vecSt[i].heapInd != HEAP_IND_NIL); assert(vecSt[i].id != ID_NIL); State st = FindByID(vecSt[i].id); assert(st.id == vecSt[i].id); assert(st.parId == vecSt[i].parId); assert(st.f == vecSt[i].f); assert(st.g == vecSt[i].g); assert(st.heapInd == vecSt[i].heapInd); assert(st.oper == vecSt[i].oper); } assert(vecSt.size() - 1 == hashTab.size); } #endif void Swap(int indA, int indB) { swap(vecSt[indA], vecSt[indB]); vecSt[indA].heapInd = indA; vecSt[indB].heapInd = indB; hashTab.UpdateState(vecSt[indA]); hashTab.UpdateState(vecSt[indB]); } void UpdateState(const State &st) { int ind = FindByID(st.id).heapInd; assert(ind != HEAP_IND_NIL); assert(st.f <= vecSt[ind].f); vecSt[ind] = st; hashTab.UpdateState(vecSt[ind]); int parInd = ParentInd(ind); while(parInd != HEAP_IND_NIL && vecSt[parInd].f > vecSt[ind].f) { Swap(parInd, ind); ind = parInd; parInd = ParentInd(ind); } } void Insert(const State &st) { State t = st; t.f = INT_INF; t.heapInd = vecSt.size(); vecSt.push_back(t); hashTab.Insert(t); t.f = st.f; UpdateState(t); } void FixDown(size_t ind) { if(ind >= vecSt.size()) return; size_t lChInd = LChildInd(ind); size_t rChInd = RChildInd(ind); size_t fixInd = ind; if(lChInd < vecSt.size() && vecSt[lChInd].f < vecSt[fixInd].f) fixInd = lChInd; if(rChInd < vecSt.size() && vecSt[rChInd].f < vecSt[fixInd].f) fixInd = rChInd; if(fixInd != ind) { Swap(fixInd, ind); FixDown(fixInd); } } bool IsEmpty() { return vecSt.size() <= 1; } State Extract() { assert(! IsEmpty()); State ret = vecSt[1]; Swap(1, vecSt.size() - 1); hashTab.Delete(vecSt.back()); vecSt.pop_back(); FixDown(1); return ret; } bool IsInHeap(int id) { return hashTab.IsInTable(id); } State FindByID(int id) { return hashTab.FindByID(id); } }; void PrintPath(const State &st, HashTable &tab) { if(st.parId == ID_NIL) return; // Print st's parent before print st PrintPath(tab.FindByID(st.parId), tab); cout << opChar[st.oper]; } void AStar(const State &startState) { if(! startState.IsSolvable()) { cout << "unsolvable/n"; return; } HashTable close(1 << 13); MinHeap open; open.Insert(startState); while(! open.IsEmpty()) { // Pop a state with minimum f State curSt = open.Extract(); close.Insert(curSt); #ifdef _DEBUG // open.CheckMinHeap(); if(open.hashTab.size % 1000 == 0) cout << "/nopen.hashTab.size = " << open.hashTab.size << "/nopen.hashTab.ASL() = " << open.hashTab.ASL() << "/n"; if(close.size % 1000 == 0) cout << "/nclose.size = " << close.size << "/nclose.ASL() = " << close.ASL() << "/n"; #endif if(curSt.IsTargetState()) { PrintPath(curSt, close); cout << "/n"; return; } // Expand the popped state for(size_t i=0; i<curSt.NextStSize(); ++i) { State nextSt = curSt.Move(Operation(i)); if(close.IsInTable(nextSt.id)) continue; State st = open.FindByID(nextSt.id); if(st.id != ID_NIL && nextSt.f < st.f) open.UpdateState(nextSt); if(st.id == ID_NIL) open.Insert(nextSt); }// End for }// End while cout << "unsolvable/n"; } int main() { int cs; cin >> cs; for(int c=0; c<cs; ++c) { State st; st.GetMat(); if(c != 0) cout << "/n"; AStar(st); } return 0; }
