水池数目

coding>C++
1.2k 词

题目描述

安徽科技学院校园里有一些小河和一些湖泊，现在，我们把它们通一看成水池，假设有一张我们学校的某处的地图，这个地图上仅标识了此处是否是水池，现在，你的任务来了，请用计算机算出该地图中共有几个水池。

输入

第一行输入一个整数N，表示共有N组测试数据
每一组数据都是先输入该地图的行数n$(0<n<100)$与列数m$(0<m<100)$，然后，输入接下来的m行每行输入n个数，表示此处有水还是没水（1表示此处是水池，0表示此处是地面）

输出

输出该地图中水池的个数。

要注意，每个水池的旁边（上下左右四个位置）如果还是水池的话的话，它们可以看做是同一个水池。

样例输入

1
2
3
4
5
6
7
8
9
10
11
2
3 4
1 0 0 0 
0 0 1 1
1 1 1 0
5 5
1 1 1 1 0
0 0 1 0 1
0 0 0 0 0
1 1 1 0 0
0 0 1 1 1

样例输出

1
2
2
3

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>

using namespace std;
#define MAXN 105
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int mapp[MAXN][MAXN];
int m, n;

void dfs(int x, int y) {
    mapp[x][y] = -1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < m && ny >= 0 && ny <= n && mapp[nx][ny] == 1) {
            mapp[nx][ny] == -1;
            dfs(nx, ny);
        }
    }
}

int main() {
    int T;
    scanf("%d\n", &T);
    while (T--) {
        int ans = 0;
        scanf("%d%d", &m, &n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &mapp[i][j]);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mapp[i][j] == 1) {
                    dfs(i, j);
                    ans++;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}