题解 | 剪纸游戏

#include <iostream>
#include <queue>
#define maxsize 1000
using namespace std;

//判断传入的连通块是否是矩形，传入外接最小矩形四个顶点，检测矩形中是否有值为1（表示*）的点即可
int check(int max_i, int max_j, int min_i, int min_j, int v[maxsize][maxsize]){
    for(int i = min_i; i <= max_i; i++){
        for(int j = min_j; j <= max_j; j++){
            if(v[i][j] == 1){
                return 0;
            }
        }
    }
    return 1;
}

int main() {
    //输入数据
    int n, m;
    cin >> n >> m;
    int v[maxsize][maxsize];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char tmp;
            cin >> tmp;
            if(tmp == '*'){
                v[i][j] = 1;
            }
            else{
                v[i][j] = 0;
            }
        }
    }
    int count = 0;//结果计数
    //对每一个0点找出所在的连通图(bfs)的最小外接矩形的四个顶点并标记访问，再判断连通图是否为长方形
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(v[i][j] == 0){
               v[i][j] = 2;
               //四个顶点
               int min_i = i;
               int max_i = i;
               int min_j = j;
               int max_j = j;
               //遍历邻接点,bfs
               queue<pair<int,int>> q;
               q.push({i, j});
               int a[4] = {-1, 0, 0, 1};
               int b[4] = {0, -1, 1, 0};
               while(!q.empty()){
                pair<int, int> current = q.front();
                q.pop();
                for(int k = 0; k < 4; k++){
                    int ti = current.first + a[k];
                    int tj = current.second + b[k];
                    if(ti >= 0 && ti < n && tj >= 0 && tj < m && v[ti][tj] == 0){
                        //是0标记，入队列并更新4个顶点的值
                        v[ti][tj] = 2;
                        q.push({ti, tj});
                        max_i = max(max_i, ti);
                        max_j = max(max_j, tj);
                        min_i = min(min_i, ti);
                        min_j = min(min_j, tj);
                    }
                }
               }
               if(check(max_i, max_j, min_i, min_j, v)){
                count++;
               }
            }
        }
    }
     
    cout << count << endl;
    return 0;
}