7-2 寻宝图 分数 25 作者 陈越 单位 浙江大学 给定一幅地图，其中有水域，有陆地。被水域完全环绕的陆地是岛屿。有些岛屿上埋藏有宝藏，这些有宝藏的点也被标记出来了。本题就请你统计一下，给定的地图上一共有多少岛屿，其中有多少是有宝藏的岛屿。

### 解决方案 对于计算地图中的岛屿数量以及有宝藏的岛屿数量的问题，可以通过深度优先搜索(DFS)或广度优先搜索(BFS)遍历二维网格来实现。这里采用的是基于连通分量的思想，在访问每一个未被标记过的陆地点时启动一个新的探索过程，并记录下遇到的具有特殊属性（如存在宝藏）的岛屿。 #### 算法思路 定义一个函数`numIslands(grid)`用于接收表示地图的数据结构——通常是一个由字符组成的矩阵，其中'1'代表土地而'0'则意味着水域；另一个辅助布尔型矩阵`visited[][]`用来跟踪哪些位置已经被处理过以防重复计数。每当找到一片新的未经访问的土地('1')即触发一次完整的子程序执行直至该片相连区域内的所有节点都被触及为止。如果在遍历过程中发现了特定条件下的元素（比如含有宝藏），就增加相应的计数器。 为了简化逻辑并提高效率，当完成对某一独立部分的操作之后应当立即将对应坐标的标志位设为已查证状态(`true`)从而避免后续不必要的循环操作。最终返回两个数值：一个是总的岛屿数目，另一个是有宝藏的岛屿的数量[^3]。 下面是具体的Python代码示例： ```python def numIslands(grid): def dfs(i, j, has_treasure=False): nonlocal island_count, treasure_island_count # 如果越界 或者 是水 ('0') 或 已经访问过了，则停止递归 if i<0 or i>=len(grid) or j<0 or j>=len(grid[0]) or grid[i][j]=='0' or visited[i][j]: return False # 将当前位置设置为已访问 visited[i][j]=True # 判断是否有宝藏 if grid[i][j] == 'T': # 假设'T'表示有宝藏的地方 has_treasure = True # 继续向四个方向扩展查找相邻的土地单元格 directions=[(-1,0),(1,0),(0,-1),(0,1)] for d in directions: ni=i+d[0]; nj=j+d[1] if not (ni<0 or ni>=len(grid) or nj<0 or nj>=len(grid[0])): dfs(ni,nj,has_treasure) # 更新全局变量 if not visited[i][j]: island_count += 1 if has_treasure: treasure_island_count += 1 return True m=len(grid); n=len(grid[0]) visited=[[False]*n for _ in range(m)] island_count=treasure_island_count=0 for row in range(m): for col in range(n): if grid[row][col]!='0' and not visited[row][col]: dfs(row,col) return f"Total Islands: {island_count}, Treasure Islands: {treasure_island_count}" ``` 此段脚本实现了上述提到的功能，通过调用`dfs()`方法深入挖掘每一块新发现的土地直到无法继续前进为止，并且同步更新有关岛屿总数目及其内含宝藏情况的信息。