首页 > 搜索 > DFS搜索 > hdu 2514 Another Eight Puzzle-DFS-[解题报告]C++
2014
02-09

hdu 2514 Another Eight Puzzle-DFS-[解题报告]C++

Another Eight Puzzle

问题描述 :

Fill the following 8 circles with digits 1~8,with each number exactly once . Conntcted circles cannot be filled with two consecutive numbers.
There are 17 pairs of connected cicles:
A-B , A-C, A-D
B-C, B-E, B-F
C-D, C-E, C-F, C-G
D-F, D-G
E-F, E-H
F-G, F-H
G-H

Filling G with 1 and D with 2 (or G with 2 and D with 1) is illegal since G and D are connected and 1 and 2 are consecutive .However ,filling A with 8 and B with 1 is legal since 8 and 1 are not consecutive .

In this problems,some circles are already filled,your tast is to fill the remaining circles to obtain a solution (if possivle).

输入:

The first line contains a single integer T(1≤T≤10),the number of test cases. Each test case is a single line containing 8 integers 0~8,the numbers in circle A~H.0 indicates an empty circle.

输出:

The first line contains a single integer T(1≤T≤10),the number of test cases. Each test case is a single line containing 8 integers 0~8,the numbers in circle A~H.0 indicates an empty circle.

样例输入:

3
7 3 1 4 5 8 0 0
7 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0

样例输出:

Case 1: 7 3 1 4 5 8 6 2
Case 2: Not unique
Case 3: No answer

题意:题中给的图填上1~8 八个数字,相连的点不能填上连续的数字

分析:各种限制条件,直接dfs了

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
bool g[10][10],fil[10];
//g[10][10]记录点与点之间是否相连,fil[10]记录该数字是否已经选过
int a[10],ans[10],num;
//ans[]保存路径
void dfs(int deep,int move[])
{
    if(deep==8)//选完了
    {
        if(!num)//保存第一个答案
        {
            for(int i=0;i<8;i++)
                ans[i]=move[i];
        }
        num++;
        return ;
    }
    else if(a[deep]>0)//该点已经给定了数字,直接往下搜
    {
        move[deep]=a[deep];
        dfs(deep+1,move);
    }
    else {
        for(int i=1;i<=8;i++)//枚举8个数字
        {
            if(fil[i])//该数字已经选过
                continue;
            int flag=0;
            for(int j=0;j<8;j++)//枚举八个点
            {
                if(g[deep][j] && ((move[j]>0 &&abs(move[j]-i)==1)||(a[j]>0 && abs(a[j]-i)==1)) )//若该点与当前点相连&& 已经选了数字 && 差值等于1
                {
                    flag=1;break;
                }
            }
            if(flag) continue;
            move[deep]=i;fil[i]=true;
            dfs(deep+1,move);
            if(num>1)return ;
            move[deep]=0;fil[i]=false;
        }
    }
}

void init()
{
    memset(g,false,sizeof(g));
    for(int i=0;i<8;i++)
        g[i][i]=true;
    for(int i=1;i<=3;i++)
        g[i][0]=g[0][i]=true;
    g[1][2]=g[2][1]=true;
    g[1][4]=g[4][1]=true;
    g[1][5]=g[5][1]=true;
    for(int i=3;i<=6;i++)
        g[2][i]=g[i][2]=true;
    g[3][5]=g[5][3]=true;
    g[3][6]=g[6][3]=true;
    g[4][5]=g[5][4]=true;
    g[4][7]=g[7][4]=true;
    g[5][6]=g[6][5]=true;
    g[5][7]=g[7][5]=true;
    g[6][7]=g[7][6]=true;
}
int main()
{
    init();
    int cas=0,T;
    scanf("%d",&T);
    while(T--)
    {
        memset(fil,false,sizeof(fil));
        for(int i=0;i<8;i++)
        {
            scanf("%d",&a[i]);
            fil[a[i]]=true;
        }
        int move[10]={0};
        num=0;
        dfs(0,move);
        printf("Case %d: ",++cas); 
        if(num==0)
            printf("No answer\n");
        else if(num>1)
            printf("Not unique\n");
        else {
            printf("%d",ans[0]);
            for(int i=1;i<8;i++)
                printf(" %d",ans[i]);
            puts("");
        }
    }
    return 0;
}

 

解题转自:http://www.cnblogs.com/nanke/archive/2012/02/14/2351174.html


,
  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  3. 不考虑最后将结果排序的话,快排的时间复杂度是O(N) ,而堆排的是O(N*logK),这样比较看,快排快

  4. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

  5. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  6. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }