首页 > 搜索 > DFS搜索 > HDU 3419-The Three Groups-DFS-[解题报告]HOJ
2014
03-23

HDU 3419-The Three Groups-DFS-[解题报告]HOJ

The Three Groups

问题描述 :

There appeared in “Nouvelles Annales de Mathematiques” the following puzzle as a modification of any of my “Canterbury Puzzles.” Arrange the nine digits in three groups of two, three, and four digits, so that the first two numbers when multiplied together make the third. Thus, 12 * 483 = 5,796. I now also propose to include the cases where there are one, four and four digits, such as 4 * 1,738 = 6,952. Can you find all possible solutions in both cases?”- Amusement in Mathematics, by Ernest Dudeney.

Now we want to arrange some of the nine digits (without ‘0’) in three groups of a, b and c digits, so that the first two numbers when multiplied together make the third. In addition, no digit can be used more than once in a single multiplication. You have to find how many solution exist there for given a, b and c.

输入:

There are multiple test cases. In addition, each test case is consisting of three integers a, b, c separated by spaces.(a , b , c >= 0 && a + b + c <= 9) Meaning of a, b, and c are described in the problem statement. The last case contains exactly three 0’s for all of a, b, c and indicates the end of input stream. This line should not be processed.

输出:

There are multiple test cases. In addition, each test case is consisting of three integers a, b, c separated by spaces.(a , b , c >= 0 && a + b + c <= 9) Meaning of a, b, and c are described in the problem statement. The last case contains exactly three 0’s for all of a, b, c and indicates the end of input stream. This line should not be processed.

样例输入:

2 3 4
1 1 1
0 0 0

样例输出:

7
4


Note:
The valid solutions for the second sample input-output are as following:
2*3 =6
2*4 =8
3*2 =6
4*2 =8

对几种情况加了特判就过了。

#include<stdio.h>
#include<string.h>
#define N 10
int vis[N],mark[N][N][N];
int a,b,c;
int x,y,z;
int cnt;
void dfs(int t,int f,int k)
{
    if(k==1&&f==a)
        x=t,f=0,k++,t=0;
    else if(k==2&&f==b)
        y=t,f=0,k++,t=0;
    else if(k==3&&f==c)
    {
        z=t;
        if(x*y==z) cnt++;
        return ;
    }
    for(int i=1;i<=9;i++)
    {
        if(vis[i]==0)
        {
            vis[i]=1;
            dfs(t*10+i,f+1,k);
            vis[i]=0;
        }
    }
    return ;
}
int main()
{
    memset(mark,0,sizeof(mark));
    while(scanf("%d%d%d",&a,&b,&c),a+b+c)
    {
        if(a+b<c)
        {
            printf("0\n");
            continue;
        }
        if(a>c||b>c)
        {
            printf("0\n");
            continue;
        }
        if(a+b-c>1)
        {
            printf("0\n");
            continue;
        }
        if(mark[a][b][c])
        {
            printf("%d\n",mark[a][b][c]);
            continue;
        }
        cnt=0;
        memset(vis,0,sizeof(vis));
        dfs(0,0,1);
        mark[a][b][c]=cnt;
        printf("%d\n",mark[a][b][c]);
    }
    return 0;
}

参考:http://blog.csdn.net/zizaimengzhongyue/article/details/14120875


,
  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  2. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  3. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks