题解 | 剪纸游戏

Modern Cpp

Flood Fill模型，考虑bfs。对于每一个四方向连通块，判断左上角和右下角坐标围成范围的格子数量是否等于连通块的数量，答案就是每次判断符合条件累加的结果。

#include <iostream>
#include <vector>
#include <string>
#include <array>
#include <queue>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int n, m;
  std::cin >> n >> m;

  std::vector g(n, std::string(m, '?'));
  for(int i = 0; i < n; i++){
    std::cin >> g[i];
  }

  constexpr std::array dx = {-1, 1, 0, 0};
  constexpr std::array dy = {0, 0, -1, 1};

  std::vector vis(n, std::vector<bool>(m));
  auto bfs = [&](int sx, int sy){
    using Node = std::array<int, 2>;
    std::queue<Node> q;
    std::array<int, 5> res = {1, sx, sy, sx, sy};

    vis[sx][sy] = true;
    q.push({sx, sy});
    
    while(q.size()){
      auto [x, y] = q.front();
      q.pop();

      for(int i = 0; i < 4; i++){
        int u = x + dx[i], v = y + dy[i];
        if(u < 0 || u >= n || v < 0 || v >= m || vis[u][v] || g[u][v] == '*'){
          continue;
        }

        vis[u][v] = true;
        res[0]++;
        res[1] = std::min(res[1], u);
        res[2] = std::min(res[2], v);
        res[3] = std::max(res[3], u);
        res[4] = std::max(res[4], v);
        q.push({u, v});
      }
    }

    return res;
  };

  int ans = 0;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(g[i][j] == '.' && !vis[i][j]){
        auto res = bfs(i, j);
        if((res[3] - res[1] + 1) * (res[4] - res[2] + 1) == res[0]){
          ans++;
        }
      }
    }
  }

  std::cout << ans << "\n";

  return 0;
}