#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y;
}a[1000005];
queue<node> q;
int n,m,ans,cnt;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
char c[1005][1005];
bool vis[1005][1005];
bool cmp(node x,node y){
if(x.x!=y.x) return x.x<y.x;
return x.y<y.y;
}
void bfs(int x,int y){
cnt=0;
q.push({x,y});
vis[x][y]=true;
while(!q.empty()){
node t=q.front();
a[++cnt]=t;
q.pop();
for(int i=0;i<4;i++){
int nx=t.x+dx[i],ny=t.y+dy[i];
if(nx<1||nx>n||ny<1||ny>m) continue;
if(vis[nx][ny]) continue;
if(c[nx][ny]=='*') continue;
vis[nx][ny]=true;
q.push({nx,ny});
}
}
return;
}
bool check(){
sort(a+1,a+cnt+1,cmp);
int h=a[cnt].x-a[1].x+1,w=a[cnt].y-a[1].y+1;
if(h*w==cnt) return true;
return false;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>c[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(c[i][j]=='.'&&!vis[i][j]){
bfs(i,j);
if(check()) ans++;
}
}
}
printf("%d",ans);
return 0;
}
说一下你的思路？
先bfs找连通块，然后将连通块中的每个点排序，如果最大的 x 减最小的 x （长）和最大的 y 减最小的 y （宽）的乘积等于这个连通块中点的数量，它就是长方形（不知道这个判定方法对不对）
可能是判断方法不对
那你有什么好的方法？
你每次清零cnt试试
你遍历的时候找四个边的极值，可能失误率低一些
你试试排两次序，一个按x，一个按y
1 个赞
方法是对的，你试试遍历的时候找最大最小的x,y
因为x，y的值要分开算
**.
**.
...
**.
这个你的左边就会错
如果有个这样的
...
*..
*.*
那么你的h就是3，w是2，但他并不是一个矩形
bu xiao xin de
已A，但是解决方案给董子豪还是给彭英哲呢？
等一会儿，我问问老师
首先，不要开数组记录，记录 x,y 的最大最小值即可；同时记录点的数量，最后判断矩阵大小是否等于点的数量即可！
那试试看找有三个联通的格子和两个联通的格子和一个联通的格子的关系
老师说晚上再看情况
ok