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

题目描述

求某个连通块里节点数量

输入格式

输出格式

数据范围

$1\le W,H\le 20$

输入样例

6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0

输出样例

45

算法

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

#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;
}

最后

以上就是知性咖啡最近收集整理的关于【AcWing】1113. 红与黑（连通类问题）的全部内容，更多相关【AcWing】1113.内容请搜索靠谱客的其他文章。