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

using namespace std;

const int MAXN=1010;

int n,m,a[MAXN][MAXN],map[MAXN][MAXN],i,j,k,x,y,ans=0,t;
char ch;

void init()
{
	freopen("rectangle.in","r",stdin);
	freopen("rectangle.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
	{
		scanf("%c",&ch);
		for (j=1;j<=m;j++)
		{
			scanf("%c",&ch);
			if (ch=='.') map[i][j]=1;
			else map[i][j]=0;
			a[i][j]=a[i-1][j]+a[i][j-1]+map[i][j]-a[i-1][j-1];
		}
	}
}

void solve()
{
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
		{
			t=m;
			for (x=i;x<=n;x++)
			{
				if (!map[x][j]) break;
				for (y=j;y<=t;y++)
				{
					if (a[x][y]-a[i-1][y]-a[x][j-1]+a[i-1][j-1]==(x-i+1)*(y-j+1)) ans++;
					else 
					{
						t=y;
						break;
					}
				}
			}
		}
}

void p()
{
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			ans+=(n-i+1)*(m-j+1);
}

int main()
{
	init();
	if (a[n][m]<n*m)
		solve();
	else p();
	printf("%d\n",ans);
	return 0;
}