hdu ---(4517)小小明系列故事——游戏的烦恼(Dp)

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

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 841    Accepted Submission(s): 296

Problem Description

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

Input

题目有多组测试数据(不多于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

Output

请计算并输出一共有多少个满足要求的小矩阵,每组输出占一行。

Sample Input

2 3 1 2

**.

.**

0 0

Sample Output

3

Source

2013腾讯编程马拉松初赛第三场(3月23日)

刚开始进行了个普通的匹配,O(∩_∩)O~,就知道会TLE,╮(╯▽╰)╭,就是这么无奈呀!

贴一下自己丑陋的代码吧..

代码:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 using namespace std;
 5 const int maxn=2005;
 6 char map[maxn][maxn];
 7 int n,m;
 8 bool match(int posx,int posy,int x,int y)
 9 {
10     int i,j;
11     if(posx+x>n||posx<0||posy+y>m||posy<0)
12         return 0;
13     for( i=posx; i<posx+x ; i++ ){
14       for( j=posy ; j<posy+y ; j++ ) {
15          if(map[i][j]!='*')return false;
16       }
17     }
18   return true;
19 }
20 
21 int work(int x,int y)
22 {
23   int i,j,cnt=0;
24   for(i=0;i<n;i++){
25       for(j=0;j<m;j++){
26      if(match(i,j,x,y)) cnt++;
27      if(match(i,j,y,x)) cnt++;
28     }
29   }
30   return cnt;
31 }
32 int main()
33 {
34   int x,y,i;
35   while(scanf("%d%d",&n,&m)!=EOF,n+m!=0)
36   {
37       scanf("%d%d",&x,&y);
38       for(i=0;i<n;i++)
39        scanf("%s",map[i]);
40     printf("%d\n",work(x,y));
41   }
42  return 0;
43 }

然后统计了一下,dp...简单的dp

代码: 不过依旧还是很挫,写到了680ms....

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 using namespace std;
 5 const int maxn=2005;
 6 char map[maxn][maxn];
 7 int dp[maxn][maxn];
 8 int n,m;
 9 void init()
10 {
11   int i,j,cnt=0;
12   memset(dp,0,sizeof(dp));
13   for(i=1;i<=n;i++) {
14       for(j=1;j<=m;j++) {
15       if(map[i][j-1]=='*')cnt++;
16         dp[i][j]=cnt+dp[i-1][j];
17     }
18     cnt=0;
19   }
20 }
21 int work(int x,int y){
22   int i,j,cnt=0;
23   for(i=1;i+x<=n;i++){
24       for(j=1;j+y<=m;j++){
25       int tem=dp[i+x][j+y]-dp[i-1][j+y]-dp[i+x][j-1]+dp[i-1][j-1];
26       if(tem==((x+1)*(y+1)))cnt++;
27     }
28   }
29   return cnt;
30 }
31 int main()
32 {
33   int x,y,i;
34   while(scanf("%d%d",&n,&m),n+m!=0)
35   {
36       scanf("%d%d",&x,&y);
37       x--,y--;
38       for(i=1;i<=n;i++)
39       scanf("%s",map[i]);
40       init();
41     if(x==y) printf("%d\n",work(x,y));
42     else printf("%d\n",work(x,y)+work(y,x));
43 
44   }
45  return 0;
46 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏智能计算时代

45测试深度学习基础知识的数据科学家的问题(以及解决方案)

原文:https://www.analyticsvidhya.com/blog/2017/01/must-know-questions-deep-learnin...

3596
来自专栏PPV课数据科学社区

【学习】七天搞定SAS(七):常用统计模型

其实最后一天,反而是任务最繁重的。这一天,需要纵览SAS的各个常用的统计模块。BTW,在用惯了ggplot2之后,再也不认为有任何理由用其他软件画图了...所以...

5206
来自专栏PPV课数据科学社区

深度学习( Deep Learning )软件资源列表

? 列表源自http://deeplearning.net/software_links/,本文进行分类整理。 星号代表对软件库的推荐度,考虑了适用范围、开发...

3027
来自专栏用户2442861的专栏

一、A*搜索算法

更多请参阅:十三个经典算法研究与总结、目录+索引。 ---------------------------------- 博主说明: 1、本经典算法研究...

4053
来自专栏互联网大杂烩

机器学习面试

线性回归的因变量是连续变量,自变量可以是连续变量,也可以是分类变量。如果只有一个自变量,且只有两类,那这个回归就等同于t检验。如果只有一个自变量,且有三类或更多...

1044
来自专栏iOSDevLog

ARKit和CoreLocation

演示代码 ARKit和CoreLocation:第一部分 ARKit和CoreLocation:第二部分 ARKit和CoreLocation:第三部分

1992
来自专栏封碎

当今世界最为经典的十大算法 博客分类: 经典文章转载 算法数据结构网络应用数据挖掘J#

本文转载自July CSDN博客:http://blog.csdn.net/v_JULY_v/archive/2011/03/07/6228235.aspx

1972
来自专栏机器学习实践二三事

Python-OpenCV(3)

上篇博客,写了个比较有意思的玩意,接下来几篇会写写基本的图像处理 首先我们要知道的是,cv2.imread(),读取的图像是个numpy矩阵 In [1]: i...

2379
来自专栏数据魔术师

基础算法 | 关于图论中最小生成树(Minimum Spanning Tree)那些不可告人的秘密

最近双11又快到了 有女朋友的忙着帮女朋友清空购物车 有男朋友的忙着叫男朋友帮清购物车 而小编就比较牛逼了 小编沉迷学习,已经无法自拔。 那么今天小编又给大家带...

5115
来自专栏小樱的经验随笔

利用向量积(叉积)计算三角形的面积和多边形的面积

利用向量积(叉积)计算三角形的面积和多边形的面积: 向量的数量积和向量积: (1)  向量的数量积 ? (1)  向量的向量积 两个向量a和b的叉积(向量积)可...

4069

扫码关注云+社区

领取腾讯云代金券