| ||||||||||
| 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