poj1077

题意：给出一个八数码问题，求解法，不可解则输出unsolvable。

分析：可以用ida*算法，估价函数可以使用每个数码到其最终位置的最短距离之和。对于不可解的判断，我这里用迭代深度大于100时判定为不可解。

还有一种更高级的无解判断方法。就是将八数码矩阵中的空格忽略，然后将8个数字排成一排，第二行接在第一行后面，第三行接在第二行后面，通过观察我们发现移动空格不会影响这个8个数字组成的数列中逆序数队的奇偶性，因此如果逆序数对的奇偶性与目标状态不同则一定无解。至于为什么奇偶性相同就一定有解，我就不知道为什么了，不过这个命题确实是正确的。

可以将这种方法做适当修改并推广至15数码问题。

#include <iostream>

#include <stack>

#include <cmath>

using namespace std;

const    int        maxn = ;

char    ans[];

int        tot, dir[][] = {{-,},{,},{,},{,-}};

struct Node

{

    char    map[maxn];

    int        g, move, xpos;

}starts;

void init()

{

    for (int i = ; i < ; i++)

    {

        starts.map[i] = ' ';

        while (starts.map[i] == ' ')

            scanf("%c",&starts.map[i]);

        if (starts.map[i] == 'x')

        {

            starts.map[i] = ;

            starts.xpos = i;

        } else

            starts.map[i] -= '';

    }

}

int h(Node &a)

{

    int        x1, x2, y1, y2, i, r = ;

    for (i = ; i < ; i++)

    {

        x1 = i / ;

        y1 = i % ;

        x2 = (a.map[i] - ) / ;

        y2 = (a.map[i] - ) % ;

        r += abs(x1 - x2) + abs(y1 - y2);

    }

    return r;

}

Node getchild(int a, Node &currents)

{

    int        x, y, pos, i;

    Node    r;

    x = currents.xpos /  + dir[a][];

    y = currents.xpos %  + dir[a][];

    r.xpos = -;

    if (x <  || y <  || x >  || y > )

        return r;

    pos = x *  + y;

    r.xpos = pos;

    r.g = currents.g + ;

    r.move = a;

    for (i = ; i < ; i++)

        r.map[i] = currents.map[i];

    r.map[pos] = ;

    r.map[currents.xpos] = currents.map[pos];

    return r;

}

bool ida()

{

    int        pathlimit, i, temp, next;

    bool    success = ;

    Node    currents, child;

    next = h(starts)/;

    stack<Node> stk;

    do

    {

        pathlimit = next;

        if (pathlimit > )

            return false;

        tot = ;

        starts.g = ;

        starts.move = -;

        next = ;

        stk.push(starts);

        do

        {

            currents = stk.top();

            ans[currents.g] = currents.move;

            stk.pop();

            temp = h(currents);

            if (temp == )

            {

                tot = currents.g;

                success = true;

            }

            else if (pathlimit >= currents.g + temp / )

            {

                for (i = ; i < ; i++)

                {

                    child = getchild(i, currents);

                    if (child.xpos != - && abs(child.move - currents.move) != )

                        stk.push(child);

                }

            }else if (next > currents.g + temp / )

                next = currents.g + temp / ;

        }while (!success && !stk.empty());

    }while (!success);

    return true;

}

void print()

{

    int        i;

    for (i = ; i <= tot; i++)

        switch(ans[i])

        {

            case : printf("u"); break;

            case : printf("r"); break;

            case : printf("d"); break;

            case : printf("l"); break;

        }

    printf("\n");

}

int main()

{

    //freopen("t.txt", "r", stdin);

    init();

    if (ida())

        print();

    else

        printf("unsolvable\n");

    return ;

}

巴特西

poj1077

最新文章

热门文章