题解 | 剪纸游戏

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int n,m;
bool visited[N][N]; 
char a[N][N];
int mov[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};

int dfs(int i,int j,int &x,int &y,int &x2,int &y2){
    if(i<0||j<0||i>=n||j>=m||a[i][j]=='*') return 0; //非法
    if(visited[i][j]) return 0; // 之前走过了
    visited[i][j] = 1; // 记录
    int d = 1; // 深度遍历树的子树中所有节点的度
    // 更新坐标
    x = min(x,i),y = min(y,j),x2 = max(x2,i),y2 = max(y2,j);
    for(int k=0;k<4;k++){
        d += dfs(i+mov[k][0],j+mov[k][1],x,y,x2,y2);
    }
    return d;
}

int main() {
    cin >> n >> m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++) cin >> a[i][j];
    }
    int ans = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(visited[i][j]) continue;
            if(a[i][j]=='.'){
                // 记录左上角和右下角的顶点
                int x=i,y=j,x2=i,y2=j,k;
                k = dfs(i,j,x,y,x2,y2);
                // 判断是否为长方形
                if(k==(x2-x+1)*(y2-y+1)){ //两顶点内的格子数应该为k
                    ans++;
                }
            }
        }
    }
    cout << ans;
}