【poj】2965 The Pilots Brothers

和poj1753类似，可能此题改变的状态比翻棋需要改变的点更多一点,如果每一位分别改变的话直接TLE.换成用数组先存状态转移量,改变状态时直接"异或"就会快很多

#include <stdio.h>

#define MAX 65536

typedef struct
{
    int state;
    int step;
}Queue;

Queue q[MAX] = {0}; //状态队列
int vis[MAX] = {0}; //判重数组
int fa[MAX] = {0}; //记录父状态
int fa_step[MAX]={0}; //父状态转移到子状态的步骤

//状态转移量
int change[16]=
{
    0x111F, 0x222F, 0x444F, 0x888F,
    0x11F1, 0x22F2, 0x44F4, 0x88F8,
    0x1F11, 0x2F22, 0x4F44, 0x8F88,
    0xF111, 0xF222, 0xF444, 0xF888
};

/*************************************
|func:递归反向输出成功得到结果的步骤
|args:当前状态cur
|retn:无返回
*************************************/
void OutPut(int cur)
{

    if (-1 != fa[cur])
    {
        OutPut(fa[cur]);
    }
    if (-1 != fa_step[cur])
    {
        printf("%d %dn", 4 - fa_step[cur] / 4, 4 - fa_step[cur] % 4);
    }
}

int main()
{
    int i = 0, cur_state = 0, front = -1, rear = 0;
    char c;

    while(i++ < 16)
    {
        c = getchar();
        cur_state += (c == '+' ? 0 : 1);
        cur_state <<= 1;
        if (0 == i % 4)
        {
            getchar();
        }
    }
    cur_state >>= 1;

    q[rear].state = cur_state;
    vis[cur_state] = 1;
    fa[cur_state] = -1;
    fa_step[cur_state] = -1;

    while(front < rear)
    {
        front = (front + 1) % MAX;
        if (0xFFFF == q[front].state)
        {
            printf("%dn", q[front].step);
            break;
        }

        for (i=1; i<17; i++)
        {
            cur_state = q[front].state;
            cur_state ^= change[16-i];
            if (!vis[cur_state])
            {
                vis[cur_state] = 1;
                rear = (rear + 1) % MAX;
                q[rear].state = cur_state;
                q[rear].step = q[front].step + 1;
                fa[cur_state] = q[front].state;
                fa_step[cur_state] = 16 - i;
            }
        }
    }
    //从终了状态递归查找父状态
    OutPut(0xFFFF);

    return 0;
}

     Source Code
     
     Problem: 2965  User: angrad 
     Memory: 1404K  Time: 266MS 
     Language: C  Result: Accepted 

2011-03-22 22:10 发表于百度空间，今搬至CU。