首页 > 搜索 > DFS搜索 > HDU 3220-Alice’s Cube-DFS-[解题报告]HOJ
2014
03-07

HDU 3220-Alice’s Cube-DFS-[解题报告]HOJ

Alice’s Cube

问题描述 :

Jammed Traffic

Alice has received a hypercube toy as her birthday present. This hypercube has 16 vertices, numbered from 1 to 16, as illustrated below. On every vertex, there is a light bulb that can be turned on or off. Initially, eight of the light bulbs are turned on and the other eight are turned off. You are allowed to switch the states of two adjacent light bulbs with different states (“on” to “off”, and “off” to “on”; specifically, swap their states) in one operation.

Given the initial state of the lights, your task is to calculate the minimum number of steps needed to achieve the target state, in which the light bulbs on the sub cube (1,2,3,4)-(5,6,7,8) are turned off, and the rest of them are turned on.

输入:

There are multiple test cases. The first line of the input contains an integer T, meaning the number of the test cases. There are about 13000 test cases in total.
For each test case there are 16 numbers in a single line, the i-th number is 1 meaning the light of the i-th vertex on the picture is on, and otherwise it’s off.

输出:

There are multiple test cases. The first line of the input contains an integer T, meaning the number of the test cases. There are about 13000 test cases in total.
For each test case there are 16 numbers in a single line, the i-th number is 1 meaning the light of the i-th vertex on the picture is on, and otherwise it’s off.

样例输入:

3
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 1
0 0 0 0 0 0 1 0 1 0 1 1 1 1 1 1

样例输出:

Case #1: 0
Case #2: 1
Case #3: more

题目请戳这里

题目大意:给一个超级立方体(具体看题目中的图),16个点,每个点有4个相邻点,图中有标识。现在每个点安一个灯泡。一共16个灯泡,有8盏亮8盏灭,现在可以交换任意相邻的2盏状态不同的灯的状态。求最少多少步能使编号1-8的8个灯泡亮,其他的灭。

题目分析:题目要求3步以内就够了。16个点,每个点有4个相邻点,16^4,不过case有13000+个。

可以考虑IDA*。将16个灯泡压缩成一个整数,根据图可以将每个点的相邻点保存下来。直接搜就可以了。

启发函数很显然,就是高8位1的个数,因为要保证高8位所有的数为0,只要高8位有一个1,那么至少要一步才能将其交换,所以高8位有多少1就至少要多少步。

其实不要这个启发函数其实也是可以过的。

不过写的时候卡在了按位与操作上了。。。还是状态压缩写少了。。。

详情请见代码:

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100000;

bool flag[N];
bool ok;
int ans;
int adj[16][4] =
{
    {1,2,4,8},
    {0,3,5,9},
    {0,3,6,10},
    {1,2,7,11},
    {0,5,6,12},
    {1,4,7,13},
    {2,4,7,14},
    {3,5,6,15},
    {0,9,10,12},
    {1,8,11,13},
    {2,8,11,14},
    {3,9,10,15},
    {4,8,13,14},
    {5,9,12,15},
    {6,10,12,15},
    {7,11,13,14},
};
int A(int x)
{
    int i;
    int ret = 0;
    for(i = 15;i >= 8;i --)
    {
        ret += (bool)(x&(1<<i));
    }
    return ret;
}
void dfs(int cur,int dp)
{
    if(cur == 255)
    {
        ok = true;
        return;
    }
    if(ok)
        return;
    if(dp + A(cur) > ans)
        return;
    int i,j,k;
    for(i = 15;i >= 0;i --)
    {
        if(cur&(1<<i))
        {
            for(j = 0;j < 4;j ++)
            {
                int tmp = 15 - adj[15-i][j];
                if(((cur>>tmp)&1)^((cur>>i)&1))//!!!!!
                {
                    int tp = cur;
                    tp ^= (1<<i);
                    tp ^= (1<<tmp);
                    if(flag[tp] == false)
                    {
                        flag[tp] = true;
                        dfs(tp,dp + 1);
                        flag[tp]= false;
                    }
                }
            }
        }
    }
}
int main()
{
    int t,i,cas = 0;
    scanf("%d",&t);
    int a[20];
    while(t --)
    {
        printf("Case #%d: ",++cas);
        for(i = 0;i < 16;i ++)
            scanf("%d",a + i);
        int tmp = 0;
        for(i = 0;i < 8;i ++)
            tmp += a[i];
        if(tmp > 3)
        {
            printf("more\n");
            continue;
        }
        tmp = 0;
        for(i = 15;i >= 0;i --)
        {
            if(a[i])
                tmp |= (1<<(15 - i));
        }
        ans = -1;
        while(1)
        {
            ans ++;
            ok = false;
            flag[tmp] = true;
            dfs(tmp,0);
            flag[tmp] = false;
            if(ok)
                break;
            if(ans >= 3)
            {
                ans ++;break;
            }

        }
        if(ans > 3)
            puts("more");
        else
            printf("%d\n",ans);
    }
    return 0;
}

参考:http://blog.csdn.net/ophunter_lcm/article/details/12836535


  1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。