山洪暴发c++求题解

Question

题目描述
公元3023年4月1日，一场史无前例的暴雨袭来，这场暴雨不仅降雨强度大，还持续时间长，这对于坐落在山脚下的可达总部大楼无疑是一个巨大的灾难，大量的雨水在山上不断汇聚成凶猛的山洪，朝着可达总部大楼袭去，洪水之强以至于可达总部被淹没。

万幸的是，可达总部大楼在某些重要的地方立起了围墙。 如果一个区域四面都被围墙围住，那这个区域就可以免受洪水侵扰。在建设图图纸上围墙用 * 号表示，

可达总部大楼里还有许多重要区域，这些重要区域在设计图中用一个 0 表示。

现在给出可达总部的围墙建设图图纸，问有多少个没被洪水淹到的重要区域。

输入格式
第一行为两个正整数 x,y

接下来 x行，每行 y个整数，由 * 和 0 组成，表示 可达总部的建设图。

输出格式
输出没被水淹没的可达总部的 0 的数量。

输入数据 1
4 5
00000
0000
000
0000
输出数据 1
1
输入数据 2
5 5

---

00*
0
00*

---

输出数据 2
5
输入数据 3
4 5

---

000
000

---

输出数据 3
6 求c++完整解题代码

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

这是一个典型的二维数组处理问题，可以通过遍历二维数组，统计满足条件的区域数量来解决。我们可以使用深度优先搜索（DFS）算法来遍历每个区域，判断其是否被围墙包围。以下是C++的解题代码：

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

const int MAXN = 100; // 最大大小
vector<vector<int>> graph; // 二维数组
int countZero = 0; // 统计未被洪水淹没的重要区域数量
int x, y; // 行数和列数

void dfs(int i, int j) { // DFS函数，用于遍历每个区域
    if (i < 0 || i >= x || j < 0 || j >= y || graph[i][j] != 0) return; // 越界或者不是围墙直接返回
    graph[i][j] = 1; // 标记为已访问过（此时被视为已被围墙包围）
    dfs(i + 1, j); // 下
    dfs(i - 1, j); // 上
    dfs(i, j + 1); // 右
    dfs(i, j - 1); // 左
}

int main() {
    cin >> x >> y; // 输入行数和列数
    graph.resize(x, vector<int>(y)); // 创建二维数组并初始化大小
    for (int i = 0; i < x; ++i) { // 输入二维数组内容
        for (int j = 0; j < y; ++j) {
            cin >> graph[i][j];
        }
    }
    for (int i = 0; i < x; ++i) { // 对每个未被标记的区域进行DFS搜索，判断是否被围墙包围
        for (int j = 0; j < y; ++j) {
            if (graph[i][j] == 0 && graph[i][j] != 1) { // 如果当前位置是未被标记的围墙（即未被访问过）且为重要区域（值为0）则进行DFS搜索
                dfs(i, j); // 从该位置开始DFS搜索周围是否被围墙包围的区域
                countZero++; // 更新未被淹没的区域数量（+1）
            }
        }
    }
    cout << countZero << endl; // 输出未被淹没的重要区域数量
    return 0;
}

上述代码中，首先定义了一个二维数组graph来存储输入数据，然后使用深度优先搜索算法遍历每个区域，判断其是否被围墙包围。如果一个区域被围墙包围（即四个方向都被围墙包围），则将其标记为已访问过（此时视为已被围墙包围），并更新未被淹没的重要区域数量。最后输出未被淹没的重要区域数量即可。