hdoj1241 油藏检测：深度优先搜索解法

"hdoj解题笔记1" 这篇解题笔记主要关注的是HDU(杭州电子科技大学)在线判题系统HDU OJ中的一道题目——"油藏"（问题编号hdoj1241），这是一个典型的图论问题，需要求解在一个二维网格中，相同字符（代表油藏）相邻的连通区域的数量。题目描述了一个地质勘测公司如何分析土地以确定油藏的位置，并要求计算出有多少个不同的油藏。 题目给出的输入格式包括一个或多个矩形网格，每个网格由m行n列组成，用m和n定义网格的大小，接着是m行n个字符，其中'*'代表没有油，'@'代表有油。输入以m=0结束。输出应为每个网格中不同油藏的数量，相邻的油藏被视为同一个。 解题的关键在于理解相邻的概念，不仅包括水平、垂直相邻，还包括对角线方向上的相邻。题目限制了每个油藏最多可以有100个单元格。因此，解题策略需要能够有效地识别并标记连通的油藏区域。 解题的基础知识涉及数据结构和算法。尽管在这个案例中没有特别的数据结构要求，但算法方面，一种常见的解决方案是使用深度优先搜索(Depth First Search, DFS)。DFS是一种用于遍历或搜索树或图的算法，适用于寻找连通组件。在这里，可以从发现的第一个油藏单元格开始，通过DFS访问所有与其相邻的油藏单元格，并在这过程中标记这些单元格，以避免重复计数。不同的油藏会通过使用不同的标记进行区分。 提供的C语言代码片段展示了如何实现这一方法。它定义了一个二维数组`map`来存储地图信息，以及一个二维数组`next`来表示从当前位置可能移动的方向。`dfs`函数被用来执行深度优先搜索，接收当前位置的坐标x和y作为参数。当找到一个油藏单元格时，函数会递归地遍历所有相邻的油藏单元格，改变它们的标记，表示它们属于同一个油藏。 这道题目考察了程序员对基本算法的理解，如深度优先搜索，以及在实际问题中应用这些算法的能力。解题的关键在于正确地识别和标记连通区域，并确保所有相邻的油藏都被视为一个整体。通过这种方式，可以有效地计算出不同油藏的数量。