ACM-DFS之Another Eight Puzzle——hdu2514

题目：http://acm.hdu.edu.cn/showproblem.php?pid=2514

Problem Description

Case 3: No answer

很有意思的一道DFS，感觉有点类似于数独了。。

看图更明白一些，就是向图中每个圈圈都放一个数字（1~8）

使得每个线段相邻的圈圈的数字不能是连续的

比如A和B、C、D是相连的，那么如果A是2，B，C，D中任何一个都不能是1或者3

解题的关键在于判断是否是连续的数字，

我的处理启发与题目中的相连，每次都从A开始找，找到最后，这样因为A和B搜索过，B就不需要再搜索A，

怎么实现？用一个for加switch就可以搞定啦，(*^__^*) 嘻嘻……

我的dfs函数传递参数只有一个就是n，代表要填第几个数，如果当前数不为0，dfs（n+1），如果为0，从vis搜索，

看哪一个没用过，就用哪一个，恢复现场的时候，不仅要恢复vis数组，还需要恢复原来数组为0，不回复0，下一次搜索发现当前不为0直接进行下一个，肯定就WA啦。。

恩，就是这样。。我switch写的有点麻烦的感觉，但是条例上应该蛮清晰的，不知道是否有更简练的。。

#include <iostream>
#include <string.h>
using namespace std;
int a[9],b[9];
bool isun,isan,vis[9];

// 自己做一个 求绝对值的函数= =。
int abs(int a)
{
    return a<0?-a:a;
}

bool je(int x,int y)
{
    // 如果两者任意一个是0  要按正确处理，让下一次判断来筛掉
    if(!a[x] || !a[y])  return false;
    if(abs(a[x]-a[y])==1)  return true;
    return false;
}

// 判断每个位置是否满足题意
bool judge(int wz)
{
    bool is;
    int i;
    for(i=1;i<=wz;++i)
    {
        switch(i)
        {
        case 1:
            {
                if(!je(1,2) && !je(1,3) && !je(1,4))  is=1;
                else    is=0;
            };break;
        case 2:
            {
                if(!je(2,3) && !je(2,5) && !je(2,6))  is=1;
                else    is=0;
            };break;
        case 3:
            {
                if(!je(3,4) && !je(3,5) && !je(3,6) && !je(3,7))  is=1;
                else    is=0;
            };break;
        case 4:
            {
                if(!je(4,6) && !je(4,7))  is=1;
                else    is=0;
            };break;
        case 5:
            {
                if(!je(5,6) && !je(5,8))  is=1;
                else    is=0;
            };break;
        case 6:
            {
                if(!je(6,7) && !je(6,8))  is=1;
                else    is=0;
            };break;
        case 7:
            {
                if(!je(7,8))  is=1;
                else    is=0;
            };break;
        default:break;
        }
        if(!is) return false;
    }
    if(!is)  return false;
    return true;
}

void dfs(int n)
{
    int i;
    if(isun)    return;
    if(n==9 && isan==1){isun=1;return;}
    if(n==9)
    {
        // 将正确的数存起来
        for(int j=1;j<=8;++j)
            b[j]=a[j];
        isan=1;
        return;
    }

    if(a[n]!=0) dfs(n+1);
    else
    {
        for(i=1;i<=8;++i)
        {
            if(vis[i]==0 && judge(n))
            {
                vis[i]=1;
                a[n]=i;
                dfs(n+1);
                // 不止vis数组恢复为0，a[n]也要恢复
                a[n]=0;
                vis[i]=0;
            }
        }
    }
}

int main()
{
    int total,i;
    cin>>total;
    for(int num=1;num<=total;++num)
    {
        memset(vis,0,sizeof(vis));
        for(i=1;i<=8;++i)
        {
            cin>>a[i];
            if(a[i]!=0) vis[a[i]]=1;
        }

        // isun表示是否有多个答案   isan表示是否有答案
        isun=0;
        isan=0;
        dfs(1);

        cout<<"Case "<<num<<":";

        if(isan==0 && isun==0)    cout<<" No answer"<<endl;
        else if(isun==1 && isan==1)  cout<<" Not unique"<<endl;
        else if(isun==0 && isan==1)
        {
            for(i=1;i<=8;++i)
                cout<<" "<<b[i];
            cout<<endl;
        }
    }
    return 0;
}

ACM-DFS之Another Eight Puzzle——hdu2514,布布扣,bubuko.com

ACM-DFS之Another Eight Puzzle——hdu2514

原文：http://blog.csdn.net/lttree/article/details/23170493