比赛 |
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;
}