IAML's Blog

Find passion in coding
poj1840 Eqs
poj1184 聪明的打字员

poj1077 Eight

IAmL posted @ 2009年3月30日 06:49 in 解题报告 with tags poj1077 Eight解题报告 , 4220 阅读

经典的搜索题,可以用BFS,双向BFS,A*算法来写。 用单向BFS写的话,和普通的BFS没什么两样。唯一要注意的就是要压缩状态,可以用康托展开(或者直接用逆序数)+hash来判重。这样一共有9!种状态,比10^9少得多。另外如果是多case的话,可以从目标状态(12345678x)开始,先预处理,这样会快点。

======华丽的分割线=========

 

#include <iostream>
#include <cstring>
using namespace std;

#define N 362881

//bool snew[N], sold[N], tnew[N], told[N];
bool state[N];
int v[9], step[N];
const int fact[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
const int move[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
//0.r; 1.d; 2.l; 3.u

struct node
{
        long num;
        long pre;
        int dir;
}q[N];

long canto()
{
        int j, i, tmp;
        long ans;

        for (ans = 1, i = 0; i < 9; i++)
        {
                for (tmp = v[i] - 1, j = 0; j < i; j++)  
                        tmp -= (v[j] < v[i]);

                ans = ans + tmp * fact[8 - i];       
        }

        return ans;
}

void toArray(long num)
{
        int i = 8;

        while (num)
        {
                v[i--] = num % 10;
                num /= 10;
        }
}

long toNum()
{
        int i;
        long ans = 0;

        for (i = 0; i < 9; i++)
                ans = ans * 10 + v[i];

        return ans;
}

long BFS()
{
        memset(state, false, sizeof(state));
        long head, tail, val;
        int xx, xy, i, tx, ty, tmp, pos1, pos2;
        node p;

        head = tail = 0;       
        p.num = toNum();
        p.pre = -1;
        p.dir = 0;
        q[tail++] = p;

        val = canto();
        state[val] = true;

        while (head < tail)
        {
                p = q[head];

                toArray(p.num);
                val = canto();

                if (val == 1) return head;

                //find x
                for (i = 0; i < 9; i++)
                        if (v[i] == 9) break;
                       
                xy = i / 3;
                xx = i % 3;          

                //move
                tx = xx;
                ty = xy;
                for (i = 0; i < 4; i++)
                {
                        tx += move[i][0];
                        ty += move[i][1];

                        if (tx >= 0 && tx < 3 && ty >= 0 && ty < 3)
                        {
                                pos1 = tx + ty * 3;
                                pos2 = xx + xy * 3;

                                tmp = v[pos1];
                                v[pos1] = v[pos2];
                                v[pos2] = tmp;

                                val = canto();

                                if (!state[val])
                                {
                                        state[val] = true;
                                        p.num = toNum();
                                        p.pre = head;
                                        p.dir = i;
                                        q[tail++] = p;
                                }

                                tmp = v[pos2];
                                v[pos2] = v[pos1];
                                v[pos1] = tmp;
                        }

                        tx = xx;
                        ty = xy;
                }
               
                head++;
        }

        if (head >= tail) return -1;

        return head;
}

void print(long i)
{
        long pos = 0;
       
        while (q[i].pre != -1)
        {
                step[pos++] = q[i].dir;
                i = q[i].pre;
        }

        //0.r; 1.d; 2.l; 3.u
        for (i = pos - 1; i >= 0; i--)
        {
                switch (step[i])
                {
                case 0:
                        cout << 'r';
                        break;
                case 1:
                        cout << 'd';
                        break;
                case 2:
                        cout << 'l';
                        break;
                case 3:
                        cout << 'u';
                        break;     
                }
        }

        cout << endl;
}

int main()
{       
        int i;
        long tmp;
        char c;

        for (i = 0; i < 9; i++)
        {
                cin >> c;

                if (c == 'x') v[i] = 9;
                else v[i] = c - '0';
        }

        tmp = BFS();

        if (tmp == -1) cout << "unsolvable\n";
        else print(tmp);

        return 0;
}

 

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter