比赛 20101116 评测结果 AATTTTTTTA
题目名称 剪切矩形 最终得分 30
用户昵称 Citron酱 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-11-16 10:59:37
显示代码纯文本
#include <fstream>

#define I_F "rectangle.in"
#define O_F "rectangle.out"
#define MAX 1000

using namespace std;

long map[MAX][MAX];
int n,m;
long ans;

void Input();
void Ycl();
long Pd(int x1, int y1, int x2, int y2);
void Search();
void Output();

int main()
{
	Input();
	Ycl();
	Search();
	Output();
	return 0;
}

void Input()
{
	ifstream fin(I_F);
	int i,j;
	char t;
	fin>>n>>m;
	for (i=0; i<n; i++)
		for (j=0; j<m; j++)
		{
			fin>>t;
			if (t=='*')
				map[i][j]=1;
		}
	fin.close();
}

void Ycl()
{
	int i,j;
	for (i=1; i<n; i++)
		map[i][0]+=map[i-1][0];
	for (j=1; j<m; j++)
		map[0][j]+=map[0][j-1];
	for (i=1; i<n; i++)
		for (j=1; j<m; j++)
			map[i][j]=map[i-1][j]+map[i][j-1]-map[i-1][j-1]+map[i][j];
}

long Pd(int x1, int y1, int x2, int y2)
{
	long t=map[x2][y2];
	if (x1>0)
		t-=map[x1-1][y2];
	if (y1>0)
		t-=map[x2][y1-1];
	if ((x1>0)&&(y1>0))
		t+=map[x1-1][y1-1];
	return t;
}

void Search()
{
	int i,j,k,l;
	for (i=0; i<n; i++)
		for (j=i; j<n; j++)
			for (k=0; k<m; k++)
				for (l=k; l<m; l++)
					if (Pd(i,k,j,l)==0)
						ans++;
}

void Output()
{
	ofstream fout(O_F);
	fout<<ans<<'\n';
	fout.close();
}