首页 > ACM题库 > HDU-杭电 > HDU 3344-Kakuro Extension Extension-模拟-[解题报告]HOJ
2014
03-16

HDU 3344-Kakuro Extension Extension-模拟-[解题报告]HOJ

Kakuro Extension Extension

问题描述 :

You know ,I’m a lazy guy and write problem description is a very very boring thing.So , I would not repeat the rule of Kakuro again , Please look at this.But things are different again,contray to the problem above,this time you should work out the input file according to the output file.

输入:

The first line of the inputs is T, which stands for the number of test cases you need to solve.
Then T case follow:
Each test case starts with a line contains two numbers N,M (2<=N,M<=100)and then N lines follow, each line contains M columns, either ‘_’ or 1~9. You can assume that the first column of the first line is ’_’.

输出:

The first line of the inputs is T, which stands for the number of test cases you need to solve.
Then T case follow:
Each test case starts with a line contains two numbers N,M (2<=N,M<=100)and then N lines follow, each line contains M columns, either ‘_’ or 1~9. You can assume that the first column of the first line is ’_’.

样例输入:

2
6 6
_ _ _ _ _ _
_ _ 5 8 9 _
_ 7 6 9 8 4
_ 6 8 _ 7 6
_ 9 2 7 4 _
_ _ 7 9 _ _
5 8
_ _ _ _ _ _ _ _
_ 1 9 9 1 1 8 6
_ _ 1 7 7 9 1 9
_ 1 3 9 9 9 3 9
_ 6 7 2 4 9 2 _

样例输出:

XXXXXXX XXXXXXX 028\XXX 017\XXX 028\XXX XXXXXXX
XXXXXXX 022\022 ....... ....... ....... 010\XXX
XXX\034 ....... ....... ....... ....... .......
XXX\014 ....... ....... 016\013 ....... .......
XXX\022 ....... ....... ....... ....... XXXXXXX
XXXXXXX XXX\016 ....... ....... XXXXXXX XXXXXXX

XXXXXXX 001\XXX 020\XXX 027\XXX 021\XXX 028\XXX 014\XXX 024\XXX
XXX\035 ....... ....... ....... ....... ....... ....... .......
XXXXXXX 007\034 ....... ....... ....... ....... ....... .......
XXX\043 ....... ....... ....... ....... ....... ....... .......
XXX\030 ....... ....... ....... ....... ....... ....... XXXXXXX

点击打开链接

#include"stdio.h"
#include"string.h"
int map[111][111][3];
int n,m;
void fun(int x,int y)
{
    int i,j;
    int t;

    t=0;
    for(i=x+1;i<n;i++)
    {
        if(map[i][y][0]==1)
        {
            t+=map[i][y][1];
        }
        else break;
    }
    map[x][y][1]=t;


    t=0;
    for(j=y+1;j<m;j++)
    {
        if(map[x][j][0]==1)
        {
            t+=map[x][j][2];
        }
        else break;
    }
    map[x][y][2]=t;
}
int main()
{
    int t;
    int i,j,k;
    char s[250];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(map,0,sizeof(map));
        getchar();
        for(i=0;i<n;i++)
        {
            gets(s);
            j=0;
            for(k=0;s[k];k++)
            {
                if(s[k]==' ')continue;
                else if(s[k]=='_')
                {
                    map[i][j][0]=0;
                    map[i][j][1]=map[i][j][2]=0;
                    j++;
                }
                else 
                {
                    map[i][j][0]=1;
                    map[i][j][1]=map[i][j][2]=s[k]-'0';
                    j++;
                }                
            }
        }
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(map[i][j][0]==0)fun(i,j);
            }
        }
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(map[i][j][0]==0)
                {
                    if(map[i][j][1]==0&&map[i][j][2]==0)
                        printf("XXXXXXX");
                    else if(map[i][j][1]==0&&map[i][j][2]!=0)
                    {
                        printf("XXX\\%03d",map[i][j][2]);
                    }
                    else if(map[i][j][1]!=0&&map[i][j][2]==0)
                    {
                        printf("%03d\\XXX",map[i][j][1]);
                    }
                    else 
                    {
                        printf("%03d\\%03d",map[i][j][1],map[i][j][2]);
                    }
                }
                else if(map[i][j][0]==1)
                {
                    printf(".......");
                }
                if(j!=m-1)printf(" ");
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}

参考:http://blog.csdn.net/yangyafeiac/article/details/8797472


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  2. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮