打卡信奥刷题（2514）用C++实现信奥 P1950 长方形

P1950 长方形

题目描述

小明今天突发奇想，想从一张用过的纸中剪出一个长方形。

为了简化问题，小明做出如下规定：

（1）这张纸的长宽分别为n,mn,mn,m。小明将这张纸看成是由n×mn\times mn×m个格子组成，在剪的时候，只能沿着格子的边缘剪。

（2）这张纸有些地方小明以前在上面画过，剪出来的长方形不能含有以前画过的地方。

（3）剪出来的长方形的大小没有限制。

小明看着这张纸，想了好多种剪的方法，可是到底有几种呢？小明数不过来，你能帮帮他吗？

输入格式

第一行两个正整数n,mn,mn,m，表示这张纸的长度和宽度。

接下来有nnn行，每行mmm个字符，每个字符为*或者.。

字符*表示以前在这个格子上画过，字符.表示以前在这个格子上没画过。

输出格式

仅一个整数，表示方案数。

输入输出样例 #1

输入 #1

6 4 .... .*** .*.. .*** ...* .***

输出 #1

38

说明/提示

【数据规模】

对10%10\%10%的数据，满足1≤n≤10,1≤m≤101\leq n\leq 10,1\leq m\leq 101≤n≤10,1≤m≤10

对30%30\%30%的数据，满足1≤n≤50,1≤m≤501\leq n\leq 50,1\leq m\leq 501≤n≤50,1≤m≤50

对100%100\%100%的数据，满足1≤n≤1000,1≤m≤10001\leq n\leq 1000,1\leq m\leq 10001≤n≤1000,1≤m≤1000

C++实现

#include<iostream>#include<cstdio>#include<cstring>#defineN1007#defineintlonglongusingnamespacestd;intn,m,now,ans;inthigh[N];signedmain(){scanf("%lld%lld",&n,&m);for(inti=1;i<=n;++i){for(intj=1;j<=m;++j){charin;scanf(" %c",&in);if(in=='.')++high[j];elsehigh[j]=0;}for(intj=1;j<=m;++j){now=high[j];for(intk=j;k<=m;++k){if(!high[k])break;now=min(now,high[k]);ans+=now;}}}printf("%lld",ans);return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容