1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // [1] 全局变量定义 int n, m; // n-农场行数,m-农场列数 char arr[110][110]; // 存储农场每个格子的状态(W/.) int brr[110][110]; // 访问标记数组,1表示已访问,0表示未访问 // [2] 定义四个方向的偏移量(右、左、下、上) int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; // [3] 深度优先搜索函数:标记当前格子所在的连通池塘为已访问 void dfs(int x, int y) { // 如果当前格子已访问 或 不是积水(W),直接返回 if (brr[x][y] == 1 || arr[x][y] == '.') return; brr[x][y] = 1; // 标记当前格子为已访问 // 遍历四个方向的相邻格子 for (int i = 0; i < 4; i++) { int tx = x + dx[i]; // 计算相邻格子的行坐标 int ty = y + dy[i]; // 计算相邻格子的列坐标 // 确保相邻格子在农场范围内(行1~n,列1~m) if (tx >= 1 && tx <= n && ty >= 1 && ty <= m) { dfs(tx, ty); // 递归访问相邻格子 } } } int main() { // [4] 输入农场的行数n和列数m cin >> n >> m; // [5] 输入每一行的格子状态 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> arr[i][j]; } } int sum = 0; // 统计池塘的数量,初始化为0 // [6] 遍历农场的每个格子 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { // 如果当前格子未访问 且 是积水(W),说明找到一个新池塘 if (brr[i][j] == 0 && arr[i][j] == 'W') { sum++; // 池塘数加1 dfs(i, j); // 标记该池塘的所有连通格子为已访问 } } } // [7] 输出最终的池塘数量 cout << sum; return 0; }
- 1
信息
- ID
- 1277
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者