比赛 20101116 评测结果 AAAAATTTTA
题目名称 剪切矩形 最终得分 60
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-11-16 09:33:55
显示代码纯文本
#include <cstdio>
const int MAXN=1005;

char map[MAXN][MAXN];
int tot[MAXN],sum[MAXN][MAXN];
int n,m,re;

int main()
{
	freopen("rectangle.in","r",stdin);
	freopen("rectangle.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		tot[i]=tot[i-1]+i;
	for(int i=1;i<=n;i++)
	{
	//	scanf("%s",map[i]+1);
		scanf("%s",map[i]+1);
	//	printf("%s\n",map[i]+1);
		for(int j=1;j<=m;j++)
			sum[j][i]=sum[j][i-1]+(map[i][j]=='*');
	}
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
		{
			bool flag[MAXN];
			int len=0;
			flag[0]=false;
			for(int k=1;k<=m;k++)
			{
				flag[k]=((sum[k][j]-sum[k][i-1])==0);
				if (flag[k]) ++len;
				else if (flag[k-1])
				{
					re+=tot[len];
					len=0;
				}
			}
			if (len) re+=tot[len];
		}
	printf("%d\n",re);
	return 0;
}