Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
A*老WA, 求助,我已经不知道哪里可错了!#include <cmath> #include <queue> #include <iostream> #include <algorithm> using namespace std; long long map; const int factorial[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; bool read() { char digit; for (int i = map = 0; i < 9; i++) { if (!(cin >> digit)) return false; if (digit == 'x') digit = '9'; map |= (long long)(digit - '0') << (i * 4); } return true; } bool mark[10]; int cantor(const long long &st) { int i, j, t, k, can = 0; for (j = 1; j <= 9; j++) mark[j] = 1; for (i = 0; i < 8; i++) { k = (st >> (i * 4)) & 15; for (j = 1, t = 0; j < k; j++) t += mark[j]; can += t * factorial[8 - i]; mark[k] = 0; } return can; } int calDist(int digit, int pos) { if (digit == 9) return 0; int x = pos / 3, y = pos % 3; int X = (digit - 1) / 3, Y = (digit - 1) % 3; return abs(X - x) + abs(Y - y); } struct Pair { long long first; int second; Pair(long long f = 0, int s = 0) : first(f), second(s) {} }; bool operator < (const Pair &A, const Pair &B) { return A.second > B.second; } Pair makePair(const long long &st, int step) { int d = 0; for (int i = 0; i < 9; i++) { int digit = (st >> (i * 4)) & 15; d += calDist(digit, i); } Pair tmp(st, d + step); return tmp; } long long swap(const long long &st, int i, int j) { long long tmp = st; long long ti = (st >> (i * 4)) & 15; long long tj = (st >> (j * 4)) & 15; tmp -= ti << (i * 4); tmp -= tj << (j * 4); tmp += ti << (j * 4); tmp += tj << (i * 4); return tmp; } int minDist[362880]; int par[362880], pace[362880]; char backtrace[362880]; void printTrace(int ind) { if (ind == -1) return; printTrace(par[ind]); cout << backtrace[ind]; } const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; const char *dir = "drul"; void solve() { long long st; int i, j, can; Pair r, s = makePair(map, 0); priority_queue<Pair> pq; pq.push(s); can = cantor(s.first); for (i = 0; i < 362880; i++) minDist[i] = 0x7f7f7f7f; minDist[can] = s.second; par[can] = -1; pace[can] = 0; while (!pq.empty()) { s = pq.top(); pq.pop(); int p = cantor(s.first); if (minDist[p] < s.second) continue; if (p == 0) { printTrace(0); cout << endl; return; } for (i = 0; 9 != ((s.first >> (i * 4)) & 15); i++); for (j = 0; j < 4; j++) { int nx = i / 3 + dx[j], ny = i % 3 + dy[j]; if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue; st = swap(s.first, i, nx * 3 + ny); r = makePair(st, pace[p] + 1); can = cantor(r.first); if (minDist[can] > r.second) { minDist[can] = r.second; par[can] = p; pace[can] = pace[p] + 1; backtrace[can] = dir[j]; pq.push(r); } } } cout << "unsolvable" << endl; } int main() { read(); solve(); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator