比赛 20101116 评测结果 AAAAATTTTA
题目名称 剪切矩形 最终得分 60
用户昵称 lc 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-11-16 11:08:07
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<fstream>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn = 1010,maxm = 1010,INF = 1000000000;
char Map[maxn][maxn];
int S[maxn][maxn],SL[maxn][maxn],Stack[maxn];
int N,M;
long long Ans;



void prep()
{
	scanf("%d%d\n",&N,&M);
	for (int i=1; i<=N; i++)
	{
		for (int j=1; j<=M; j++)
		{
			scanf("%c",&Map[i][j]);
			S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + (Map[i][j] == '*');
		}
		scanf("\n");
	}
	for (int y=1; y<=M; y++)
		for (int x=1; x<=N; x++)
			SL[y][x] = SL[y][x-1] + (Map[x][y] == '*');
}

void work()
{
	for (int x1=1; x1<=N; x1++)
	{
		for (int x2=x1; x2<=N; x2++)
		{
			int top = 1;
			Stack[1] = 0;
			for (int t=1; t<=M; t++)
				if (SL[t][x2]-SL[t][x1-1]==0)
				{
					Stack[top] += 1;
				}
				else
				{
					top++; Stack[top] = 0;
				}
			for (int t=1; t<=top; t++)
				Ans += (long long)Stack[t]*(Stack[t]+1)/2;
			if (top==1 && Stack[top]==0) break;
		}
	}
	
	ofstream fout("rectangle.out");
	fout <<Ans <<endl;
	fout.close();
}

int main()
{
	freopen("rectangle.in","r",stdin);
	prep();
	work();
	return 0;
}