首页 > ACM题库 > HDU-杭电 > Hdu 1453 City hall[解题报告] C++
2013
12-11

Hdu 1453 City hall[解题报告] C++

City hall

问题描述 :

Because of its age, the City Hall has suffered damage to one of its walls. A matrix with M rows and N columns represents the encoded image of that wall, where 1 represents an intact wall and 0 represents a damaged wall (like in Figure-1).               1110000111
1100001111
1000000011
1111101111
1110000111Figure-1

To repair the wall, the workers will place some blocks vertically into the damaged area. They can use blocks with a fixed width of 1 and different heights of {1,2, …, M}.

For a given image of the City Hallˇs wall, your task is to determine how many blocks of different heights are needed to fill in the damaged area of the wall, and to use the least amount of blocks.

输入:

There is only one test case. The case starts with a line containing two integers M and N (1 <= M, N <= 200). Each of the following M lines contains a string with length of N, which consists of ¨1〃s and/or ¨0〃s. These M lines represent the wall.

输出:

You should output how many blocks of different heights are needed. Use separate lines of the following format:k Ck

where k�{1,2, …, M} means the height of the block, and Ck means the amount of blocks of height k that are needed. You should not output the lines where Ck = 0. The order of lines is in the ascending order of k.

样例输入:

5 10
1110000111
1100001111
1000000011
1111101111
1110000111

样例输出:

1 7
2 1
3 2
5 1


这道题不难,关键就在你是选择什么方法来计算需要加进去的砖块,是从小开始还是从大的开始。从小的开始虽然输出比较简单,但是算法不好实现。为了解决这个问题,最好还是新建一个数组用来存储从最大的砖头开始的砖头数,用数组的序号+1来表示砖头的size。

#include<cstdio>
#include<cstring>
#include <algorithm>
//using namespace std;
const int A=210;
int main()
{
    int m,n,i,j,ii,jj,c;
    scanf("%d %d",&m,&n);
    getchar();
    char p[A][A];
    int pp[A];
    for(i=0;i<m;i++)
    gets(p[i]);
    for(int k=m;k>=1;k--)
    {       
        int count=0;
        for(j=0;j<n;j++)
        for(i=0;i<m;i++)
        if(p[i][j]=='0')
        {
                          c=0;
                          for(jj=i;jj<m;jj++)
                          {
                                              if(p[jj][j]=='0') c++;
                                              else {jj--;break;}
                          }
                          if(c==k)
                          {
                                  count++;
                                  for(int jjj=i;jjj<=jj;jjj++) p[jjj][j]='1';                                 
                          }
                          i=jj;
        }
        pp[k-1]=count;
    }
    for(i=0;i<m;i++)
    {
                       if(pp[i]!=0) printf("%d %d\n",i+1,pp[i]);                     
    }
    return 0;
}

 


  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  2. 在方法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的边不是都没了吗?

  3. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept