Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

A*老WA, 求助,我已经不知道哪里可错了!

Posted by private_WXStudio at 2011-11-15 00:37:13 on Problem 1077
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator