首页 > ACM题库 > HDU-杭电 > HDU 4517-小小明系列故事――游戏的烦恼-模拟-[解题报告]HOJ
2015
07-17

HDU 4517-小小明系列故事――游戏的烦恼-模拟-[解题报告]HOJ

小小明系列故事――游戏的烦恼

问题描述 :

  小小明最近在玩一款游戏,它由n*m大小的矩阵构成,矩阵上会随机产生一些黑色的点,这些点它们可能会连在一起也可能会分开,这些点的个数没有限制,但是每个1*1方格中最多只可能有一个黑点产生。游戏要求玩家以最短的时间用x*y的小矩阵覆盖这个大矩阵,覆盖的要求有以下2点:
  1. x*y大小的小矩阵内必须有x*y个黑点。
  2. 多个小矩阵可以重叠,但是每个小矩阵放置的位置必须是独一无二的,即不同的小矩阵内的黑点不能完全相同。例如1*2的矩阵可以横着放,也可以竖着放,这两种方法是不同的,即使它们可能共用黑点。
  小小明是个粗心的孩子,他尝试了很多遍都无法将所有的符合要求的小矩阵找到,聪明的你,能不能告诉烦恼中的小小明这个大矩阵里有多少个满足要求的小矩阵呢?

输入:

题目有多组测试数据(不多于100个);
每组测试数据的第一行包含2个正整数n和m,然后第二行是x和y(n,m,x,y的意思如题),接下来n行,每行m个字符,其中’ * ’表示黑点,’ . ’表示空白。
n和m为0则结束输入。

[Technical Specification]
0 < n, m <= 2000
0 < x, y <= 1000

输出:

题目有多组测试数据(不多于100个);
每组测试数据的第一行包含2个正整数n和m,然后第二行是x和y(n,m,x,y的意思如题),接下来n行,每行m个字符,其中’ * ’表示黑点,’ . ’表示空白。
n和m为0则结束输入。

[Technical Specification]
0 < n, m <= 2000
0 < x, y <= 1000

样例输入:

2 3
1 2
**.
.**
0 0

样例输出:

3

HDU 4517

喜闻乐见中文题,开门见山,cnt[ i ][ j ]记录第i行第j列为终点,记录向左连续带*号的的长度,处理完毕一次之后,再从上到下按列处理一次,用len1,len2记录以第i行第j列为终点时候,每一行带*号的长度大于等于规定的长/宽的长度。相加就是答案。这里有个陷阱,就是当小矩阵行等于列的时候,要将答案除以2。做是做出来了,但是WA2次+耗时颇长,实力不够,再接再厉。

PS:师兄说用队列什么的来做会清晰一点,弱菜不会,只能用数组模拟了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 2005
int cnt[N][N];
int maps[N][N];
int main()
{
    int i,j,n,c,r,m;
    char ch[N];
    while(scanf("%d%d",&n,&m) && n + m)
    {
        scanf("%d%d",&c,&r);
        int ans = 0;
        for(i = 1;i <= n;i++)
        {
            scanf("%s",&ch);
            for(j = 1;j <= m;j++)
            {
                
                int flag = ch[j - 1] == '*'?1:0;
            //    cout<<ch[j - 1]<<endl;
                if(flag)
                    cnt[i][j] = cnt[i][j - 1] + 1;
                else
                    cnt[i][j] = 0;

            }
        }
        int len1,len2;
        for(i = 1;i <= m;i++)
        {
            len1 = len2 = 0;
            for(j = 1;j <= n;j++)
            {
            //    cout<<cnt[j][i]<<endl;
                if(cnt[j][i] >= c)
                {
                    len1++;
                }
                else
                {
                    len1 = 0;
                }
                if(len1 >= r)
                {
                    ans ++;
                }
                if(cnt[j][i] >= r)
                {
                    len2++;
                }
                else
                {
                    len2 = 0;
                }
                if(len2 >= c)
                {
                    ans++;
                }
            }
        }
        if(c == r)
            ans /= 2;
        printf("%d\n",ans);
    }
    return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/rssj_chlh/article/details/8711472