洛谷：P1596：Lake Counting S

题目

P1595：Lake Counting S

分析

DFS

先看DFS的解决思路。

题目规定了：从一个水坑（W）出发，任何八个方向中有水坑就视作同一个水坑。

DFS的思路是，选一个方向，如果这个方向上有水坑，就从这个点开始，继续沿着这个方向搜索；如果没有，换个方向继续DFS。直到所有方向都不是水坑……最后，这么多水坑构成一个水坑，计数加1。同时，被遍历的水坑可以标记为.，避免重复访问和死循环。

本题不用回溯，因为根据题意，任何连通的水坑其实都是一个坑。

核心代码：

void dfs(int x, int y)
{
    // 如果坐标超出边界，或者不是水，或者已经访问过
    if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] != 'W')
    {
        return;
    }

    // 标记当前格子为已访问（用'.'表示）
    grid[x][y] = '.';

    // 递归访问8个方向
    for (int i = 0; i < 8; i++)
    {
        dfs(x + dx[i], y + dy[i]);
    }
}

BFS

BFS的思路基本类似。但是会先考虑八个方向，再是这八个方向的八个方向……

核心代码：

void bfs(int x, int y)
{
    // 创建队列，存储要访问的坐标
    queue<pair<int, int>> q;
    q.push({x, y});

    // 标记起始点为已访问
    grid[x][y] = '.';

    while (!q.empty())
    {
        // 取出队列中的一个点
        int cur_x = q.front().first;
        int cur_y = q.front().second;
        q.pop();

        // 检查8个方向的相邻点
        for (int i = 0; i < 8; i++)
        {
            int new_x = cur_x + dx[i];
            int new_y = cur_y + dy[i];

            // 如果新坐标在网格内且是水
            if (new_x >= 0 && new_x < n && new_y >= 0 && new_y < m && grid[new_x][new_y] == 'W')
            {
                // 标记为已访问
                grid[new_x][new_y] = '.';
                // 将新坐标加入队列
                q.push({new_x, new_y});
            }
        }
    }
}        

仔细比较的话，会发现这两个算法，其核心是一样的——毕竟是要解决的问题是一样的。不同的是：

DFS注重的是返回条件，所以它的if判定是“越界或无法访问”——一旦越界或无法访问，就返回；BFS注重的是继续条件，所以它的if判定是“可以拓展”——可以拓展就压栈，作为下一个可以访问的点。

这是DFS和BFS的重要差异，在编程的时候需要注意。

1. DFS的思维方式是“遇到障碍就回头”。只有当所有可能的路径都走不通时，才会回溯。
2. BFS的思维方式是“能走就走”。只要发现新的可访问点，就立即加入队列。

答案

DFS答案

BFS答案

思考

DFS和BFS在某些情况下可以互换，但在其他情况下则不能。

可以互换的情况：

• 连通块问题（如本题）
• 只需要判断是否可达的问题
• 只需要遍历所有节点的问题

不能互换的情况：

• 最短路径问题：
  • BFS：保证找到最短路径（无权图）
  • DFS：不能保证找到最短路径