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考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容