526互联

闭合区域面积统计 题解

发布时间 2023-12-22 19:19:34作者: popcoount

题目描述

计算一个 \(10 \times 10\) 矩阵中由 \(1\) 围成的图形的面积。如下所示，在 \(10 \times 10\) 的二维数组中，\(1\) 围住了 \(15\) 个点，因此面积为 \(15\)。

0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0

思路

这道题一开始看上去没啥思路，但仔细想想，是不是拿一桶无限多的水随便往墙（\(1\) 围成的圈子）外的一个地方倒，再统计没有倒上的面积就可以了？

但是有一种例外，比如：

0 0 0 1 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0
0 0 1 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0 0 0
1 0 0 0 0 0 1 0 0 0
0 1 1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

如上，如果我们只在左上角流水，那么水就会被堵住，不能流遍该流到的地方，答案就错了。

这时有两种解决方法：

  1. 在四角都流一遍水。

  2. 在地图的外圈添加一圈 \(0\)，使得所有 \(0\) 都是联通的。

代码

#include <bits/stdc++.h>
using namespace std;
bool a[20][20];
struct Node {
    int x, y;
};
queue<Node> q;
bool vis[20][20];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main() {
    for (int i = 2; i <= 11; i++) 
        for (int j = 2; j <= 11; j++) 
            cin >> a[i][j];
    q.push({1, 1});
    vis[1][1] = 1;
    a[1][1] = 1;
    while (!q.empty()) {
        Node t = q.front();
        q.pop();
        if (t.x == 12 and t.y == 12) break;
        for (int i = 0; i < 4; i++) {
            int nx = t.x + dx[i], ny = t.y + dy[i];
            if (nx > 12 or nx < 1 or ny > 12 or ny < 1) continue;
            if (vis[nx][ny]) continue;
            if (a[nx][ny]) continue;
            a[nx][ny] = vis[nx][ny] = 1;
            q.push({nx, ny});
        }
    }
    int cnt = 0;
    for (int i = 1; i <= 12; i++) 
        for (int j = 1; j <= 12; j++) 
            if (!a[i][j]) 
                cnt++;
    cout << cnt << '\n';
    return 0;
}