比赛 |
20101116 |
评测结果 |
AAAAATTTTA |
题目名称 |
剪切矩形 |
最终得分 |
60 |
用户昵称 |
苏轼 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2010-11-16 09:33:55 |
显示代码纯文本
#include <cstdio>
const int MAXN=1005;
char map[MAXN][MAXN];
int tot[MAXN],sum[MAXN][MAXN];
int n,m,re;
int main()
{
freopen("rectangle.in","r",stdin);
freopen("rectangle.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
tot[i]=tot[i-1]+i;
for(int i=1;i<=n;i++)
{
// scanf("%s",map[i]+1);
scanf("%s",map[i]+1);
// printf("%s\n",map[i]+1);
for(int j=1;j<=m;j++)
sum[j][i]=sum[j][i-1]+(map[i][j]=='*');
}
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
{
bool flag[MAXN];
int len=0;
flag[0]=false;
for(int k=1;k<=m;k++)
{
flag[k]=((sum[k][j]-sum[k][i-1])==0);
if (flag[k]) ++len;
else if (flag[k-1])
{
re+=tot[len];
len=0;
}
}
if (len) re+=tot[len];
}
printf("%d\n",re);
return 0;
}