题解：Oil Deposits（P1562）

一、题目分析

本题要求计算二维网格中连通的油藏数量。关键信息：

• 网格中$@$表示油藏，$*$表示无油
• 相邻的$@$（包括对角线）属于同一个油藏
• 需要统计独立油藏的数量

二、解题思路

1. 模型抽象：
   将问题转化为图的连通分量计数，每个$@$作为图中的节点，相邻关系为边。

2. 算法选择：

   • 每完成一次DFS，油藏计数+1

3. 遍历策略：
   遍历整个网格，对每个未访问的$@$启动DFS，确保不重复计数。

三、代码解析

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;

char map[101][101];  // 存储网格
int m, n, sum;       // m:行数，n:列数，sum:油藏计数

// 深度优先搜索，将当前油藏全部标记为'*'
void dfs(int i, int j) {
    if (map[i][j] != '@' || i < 0 || j < 0 || i >= m || j >= n)
        return;  // 越界或非油藏点，返回
    
    map[i][j] = '*';  // 标记为已访问
    
    // 向8个方向递归搜索
    dfs(i-1, j-1); dfs(i-1, j); dfs(i-1, j+1);
    dfs(i, j-1);                 dfs(i, j+1);
    dfs(i+1, j-1); dfs(i+1, j); dfs(i+1, j+1);
}

int main() {
    while (~scanf("%d %d", &m, &n)) {
        if (m == 0 || n == 0) break;  // 输入结束
        
        sum = 0;
        // 读取网格
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                cin >> map[i][j];
        
        // 遍历每个点，统计油藏数
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (map[i][j] == '@') {
                    dfs(i, j);  // 标记当前油藏
                    sum++;      // 油藏计数+1
                }
        
        cout << sum << endl;
    }
    return 0;
}

四、关键步骤解析

1. 输入处理

   • 读取网格尺寸$m$和$n$，当$m=0$时结束输入
   • 使用二维数组$map$存储网格状态

2. DFS搜索

   • 终止条件：坐标越界或当前点非$@$
   • 标记操作：将当前$@$标记为$*$，避免重复访问
   • 递归方向：向8个相邻方向（上下左右+对角线）扩展

3. 油藏计数

   • 遍历整个网格，每发现一个$@$，启动一次DFS
   • 每次DFS完成后，油藏数量+1

五、示例解析

以输入3 5的网格为例：

*@*@*
**@**
*@*@*

1. 初始状态：
   网格中有5个$@$，分布在两列。

2. DFS过程：

   • 从(0,1)开始DFS，标记相连的$@$：(0,1)→(1,2)→(2,1)，计数+1
   • 从(0,3)开始DFS，标记相连的$@$：(0,3)→(2,3)，计数+1
   • 所有$@$均被访问，最终计数为2。

3. 输出结果：
   该网格包含2个独立油藏，输出$2$。

六、注意事项

1. 标记策略：
   直接将访问过的$@$修改为$*$，无需额外的访问标记数组，节省空间。

2. 时间复杂度：
   每个点最多被访问一次，时间复杂度为O(m×n)，其中m和n为网格尺寸。

3. 空间复杂度：
   递归栈深度最大为O(m×n)（极端情况下整个网格为一个油藏），但题目限制油藏不超过100个点，实际空间开销较小。

七、可能的优化

1. BFS替代DFS：
   使用队列实现BFS，避免递归栈过深导致的栈溢出风险。

2. 并查集（Union-Find）：
   对于大规模数据，使用并查集统计连通分量可能更高效。

3. 输入优化：
   使用$scanf$替代$in$，提高大规模输入的读取效率。