【AcWing】1113. 红与黑（连通类问题）

74 阅读 0 评论 49 点赞

我是靠谱客的博主知性咖啡，这篇文章主要介绍【AcWing】1113. 红与黑（连通类问题），现在分享给大家，希望可以做个参考。

题目描述

求某个连通块里节点数量

输入格式

输出格式

数据范围

$1 \leq W, H \leq 20$

输入样例

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0

输出样例

复制代码

1
2
45

算法

特别注意m,n的含义，当时搞反了。

复制代码

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
#include <bits/stdc++.h>

using namespace std;
const int N = 30;
char mat[N][N];
bool st[N][N];
int m, n;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
// 从x, y能够走多少个格子
int dfs(int x, int y) {
    st[x][y] = true;
    
    int res = 1;
    for (int i = 0; i < 4; ++ i) {
        int xx = x + dx[i], yy = y + dy[i];
        if (0 <= xx && xx < m && 0 <= yy && yy < n && !st[xx][yy] && mat[xx][yy] == '.') {
            res += dfs(xx, yy);
        }
    }
    return res;
}
int main() {
    while (scanf("%d%d", &n, &m)) {
        if (m == 0 && n == 0) return 0;
        memset(st, false, sizeof st);
        for (int i = 0; i < m; ++ i) {
            scanf("%s", &mat[i]);
        }
        int x, y;
        for (int i = 0; i < m; ++ i)
            for (int j = 0; j < n; ++ j) {
                if (mat[i][j] == '@') {
                    x = i, y = j;
                }
            }
       cout << dfs(x, y) << endl;
    }
    return 0;
}