题解 | 剪纸游戏

#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <unordered_map>
using namespace std;
//广度搜索中队列替换成栈， 获取到所有链接的格子，组内x坐标数*y坐标数 == 格子数则为长方形
struct Pt {
    int y;
    int x;
};
struct Node : Pt {
    int lastId;
};
int main() {
    int n, m;
    cin >> n >> m;
    vector<string> map(n);
    for(auto& v : map) {
        cin >> v;
    }
    int gId = 0;
    // empty, block
    list<Node> eq, bq;
    if(map[0][0] == '*') {
        eq.push_back(Node{0,0,0});
    } else {
        gId++;
        bq.push_back(Node{0,0,gId});
    }
    vector<Pt> round = {
        {-1,0},{1,0},{0,-1},{0,1}
    };
    vector<vector<bool>> visited(n, vector<bool>(m));
    unordered_map<int,vector<Pt>> group;
    while(eq.size() + bq.size()) {
        list<Node>* q;
        auto isBlock = false;
        if(bq.size()) {
            q = &bq;
            isBlock = true;
        }else {
            q = &eq;
        }
        auto node = q->back();
        q->pop_back();
        if(visited[node.y][node.x]) {
            continue;
        }
        int id = node.lastId;
        if(isBlock){
            if(id == 0) {
                gId++;
                id = gId;
            }
            group[id].push_back(Pt{node.y, node.x});
        }
        visited[node.y][node.x] = true;
        for(auto& v : round) {
            auto y = node.y + v.y;
            auto x = node.x + v.x;
            if(x < 0 || x >= m || y < 0 || y >= n) {
                continue;
            }
            if(visited[y][x]) {
                continue;
            }
            if(map[y][x] == '*') {
                eq.push_back(Node{y,x,0});
            } else {
                bq.push_back(Node{y,x,id});
            }
        }
    }
    // for(auto& it : group) {
    //     printf("id:[%d] ", it.first);
    //     for(auto& pt : it.second) {
    //         printf("[%d:%d], ", pt.y, pt.x);
    //     }
    //     cout << endl;
    // }
    int cnt = 0;
    for(auto& it : group) {
        unordered_map<int,int> xCnt, yCnt;
        for(auto& pt : it.second) {
            xCnt[pt.x]++;
            yCnt[pt.y]++;
        }
        if(xCnt.size() * yCnt.size() == it.second.size()) {
            ++cnt;
        }
    }
    cout << cnt << endl;
}
// 64 位输出请用 printf("%lld")