比赛 20101116 评测结果 AAAAAAATAA
题目名称 剪切矩形 最终得分 90
用户昵称 .Xmz 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-11-16 09:44:39
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

const int oo=2000000000;
char st[1001];
bool a[1001][1001];
bool yy;
int s[1001],n,m;
long long ans;
int main()
{
	freopen("rectangle.in","r",stdin);
	freopen("rectangle.out","w",stdout);
	scanf("%d%d\n",&n,&m);
	for (int i=1;i<=n;i++)
	{
		scanf("%s",st);
		for (int j=1;j<=m;j++)
		if (st[j-1]!='*') a[i][j]=true;
		else {a[i][j]=false;yy=true;}
	}
	
	if (!yy)
	{
		printf("%lld",(long long)n*(n+1)*m*(m+1)/4);
		return 0;
	}
	
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			int mins=oo;
			for (int k=j;k<=m;k++)
			{
				if (!a[i][k]) break;
				if (s[k]<mins) mins=s[k];
				ans+=(mins+1);
			}
			if (a[i][j]) s[j]+=1;
			else s[j]=0;
		}
	}
	printf("%lld\n",ans);
	return 0;
}