poj 1077 Eight

#include <iostream>#include <stack>#include <math.h>#include <stdio.h>#include <string.h>#include <stdlib.h>using namespace std;const    int        maxn = 10;char    ans[100];int        tot, dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};struct Node{    char    map[maxn];    int        g, move, xpos;}starts;void init(){    for (int i = 0; i < 9; i++)    {        starts.map[i] = ' ';        while (starts.map[i] == ' ') scanf("%c",&starts.map[i]);        if (starts.map[i] == 'x')        { starts.map[i] = 9; starts.xpos = i;        } else starts.map[i] -= '0';    }}int h(Node &a){    int        x1, x2, y1, y2, i, r = 0;    for (i = 0; i < 9; i++)    {        x1 = i / 3;        y1 = i % 3;        x2 = (a.map[i] - 1) / 3;        y2 = (a.map[i] - 1) % 3;        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 / 3 + dir[a][0];    y = currents.xpos % 3 + dir[a][1];    r.xpos = -1;    if (x < 0 || y < 0 || x > 2 || y > 2)        return r;    pos = x * 3 + y;    r.xpos = pos;    r.g = currents.g + 1;    r.move = a;    for (i = 0; i < 9; i++)        r.map[i] = currents.map[i];    r.map[pos] = 9;    r.map[currents.xpos] = currents.map[pos];    return r;}bool ida(){    int        pathlimit, i, temp, next;    bool    success = 0;    Node    currents, child;    next = h(starts)/2;    stack<Node> stk;    do    {        pathlimit = next;        if (pathlimit > 100) return false;        tot = 0;        starts.g = 0;        starts.move = -1;        next = 200;        stk.push(starts);        do        { currents = stk.top(); ans[currents.g] = currents.move; stk.pop(); temp = h(currents); if (temp == 0) {     tot = currents.g;     success = true; } else if (pathlimit >= currents.g + temp / 2) {     for (i = 0; i < 4; i++)     {         child = getchild(i, currents);         if (child.xpos != -1 && abs(child.move - currents.move) != 2)  stk.push(child);     } }else if (next > currents.g + temp / 2)     next = currents.g + temp / 2;        }while (!success && !stk.empty());    }while (!success);    return true;}void print(){    int        i;    for (i = 1; i <= tot; i++)        switch(ans[i])        { case 0: printf("u"); break; case 1: printf("r"); break; case 2: printf("d"); break; case 3: printf("l"); break;        }    printf("n");}int main(){    init();    if (ida())        print();    else        printf("unsolvablen");    return 0;}