题解 P6866 【[COCI2019-2020#5] Emacs】

_•́へ•́╬_ · 2020-10-25 00:22:58 · 题解

题目描述

给定一个 n\times m 的只含有 . 和 * 的矩阵。

矩阵中 * 形成一些长方形。

求长方形有多少个？

思路

不建议搜联通块。

可以找长方形上某一特殊点来确定长方形。

窝统计每个长方形左上角的点。

寻找方法：左边是 .（左边什么都没有也行）且上面是 .（上面什么都没有也行）。

理由：两个长方形是不接壤的。

code

#include<stdio.h>
int n,m,ans;char a[100][100];
main()
{
    scanf("%d%d",&n,&m);for(register int i=0;i<n;++i)scanf("%s",a[i]);
    for(register int i=0;i<n;++i)for(register int j=0;j<m;++j)
        if(a[i][j]=='*'&&(!i||a[i-1][j]=='.')&&(!j||a[i][j-1]=='.'))++ans;
    printf("%d",ans);
}