题解 | 剪纸游戏

#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;

//判断传入的连通块是否是矩形
int check(set<pair<int,int>> s){
    pair<int,int> a = *s.begin();
    pair<int,int> b = *s.rbegin();
    //找出最小外接长方形的四个顶点
    int min_first = a.first;
    int max_first = b.first;
    int min_second = a.second;
    int max_second = a.second;
    for(const auto& it : s){
        if(it.second < min_second){
            min_second = it.second;
        }
        if(it.second > max_second){
            max_second = it.second;
        }
    }
    //判断最小外接长方形是否每个顶点都在s内
    for(int i = min_first; i <= max_first; i++){
        for(int j = min_second; j <= max_second; j++){
            if(!s.count({i, j})){
                return 0;
            }
        }
    }
    return 1;
}


int main() {
    //输入数据
    int n, m;
    cin >> n >> m;
    vector<vector<int>> v(n, vector<int>(m));
    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;
               set<pair<int,int>> s;
               queue<pair<int,int>> q;
               q.push({i, j});
               s.insert({i, j});
               //遍历邻接点,bfs
               vector<int> a = {-1, 0, 0, 1};
               vector<int> b = {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){
                        v[ti][tj] = 2;
                        q.push({ti, tj});
                        s.insert({ti, tj});
                    }
                }
               }
               if(check(s)){
                count++;
               }
            }
        }
    }
    //输出结果
    cout << count << endl;
    return 0;
}