[STSC OI - 1B] 城墙 (walls) 题解

题目分析

本题要求我们给定一个 n * m 的地图，其中每个位置上可能是城墙（#）或者空地（.）。城墙和塔楼视为一体，题目要求我们统计出城墙被分成了多少个部分。一个部分是由相连的 # 组成的区域，# 之间可以通过八个方向（上下左右及四个对角线方向）相连。

解题思路

深度优先搜索（DFS）

对于这个问题，我们可以通过深度优先搜索（DFS）来遍历每个连通的 # 组成的区域。具体的思路如下：

1. 初始化：首先读取地图的尺寸 n 和 m，以及地图内容。然后初始化一个 visited 数组，记录每个位置是否已经被访问过。

2. DFS搜索：我们从每一个未被访问的 # 开始，进行深度优先搜索，标记所有连通的 # 为已访问。

3. 八个方向：为了考虑所有的相邻 #，我们需要设置八个方向的偏移量，这包括上下左右和四个对角线方向。

4. 统计部分数：每当发现一个未被访问的 # 时，表示找到了一个新的部分，进行 DFS 后计数增加。

5. 输出结果：最后输出计数的结果，即城墙被分成的部分数。

代码实现

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

int n, m;
vector<vector<char>> grid;
vector<vector<bool>> visited;

// 八个方向：上下左右及四个对角线
int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1}; 
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};

void dfs(int x, int y) {
    visited[x][y] = true;  
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && grid[nx][ny] == '#') {
            dfs(nx, ny);  
        }
    }
}

int main() {
    cin >> n >> m;
    grid.resize(n, vector<char>(m));
    visited.resize(n, vector<bool>(m, false));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    int parts = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '#' && !visited[i][j]) {
                dfs(i, j);  // 从未访问的 '#' 开始 DFS
                parts++;  // 找到一个新的部分
            }
        }
    }

    cout << parts << endl;

    return 0;
}