本文共 2247 字，大约阅读时间需要 7 分钟。

在Objective-C中实现“Number of Islands”算法的关键在于通过深度优先搜索（DFS）或广度优先搜索（BFS）来遍历二维网格中的岛屿。以下是完整的Objective-C示例代码，展示了如何计算网格中的岛屿数量。

Objective-C实现岛屿数量算法

算法概述

“Number of Islands”问题要求我们计算一个由0和1组成的二维网格中相邻相同数字区域的数量。通常，1表示水域，0表示陆地。目标是通过遍历网格，找出所有由1组成的连通区域的数量。

实现选择

在这个问题中，我们可以选择使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历岛屿。DFS适合递归处理，而BFS更适合使用队列来逐层扩展。以下使用DFS实现。

示例代码

#import 
   
    @interface Solution : NSObject-(NSInteger)numIslands:(NSArray
    
     )grid;@end@implementation Solution-(NSInteger)numIslands:(NSArray
     
      )grid {    if (!grid || grid.count == 0) return 0;        NSInteger rows = grid.count;    NSInteger cols = grid[0].length;        // visited矩阵用于记录已经访问过的单元格    BOOL** visited = (BOOL**)malloc(rows * cols);        NSInteger islandCount = 0;        for (NSInteger i = 0; i < rows; i++) {        for (NSInteger j = 0; j < cols; j++) {            if (grid[i][j] == '1' && !visited[i][j]) {                islandCount++;                // DFS遍历当前岛屿                [self dfs:i j:(int)j rows:rows cols:cols visited:visited grid:grid islandCount:(&islandCount)];            }        }    }        return islandCount;}// 深度优先搜索-(void)dfs:(NSInteger)i j:(NSInteger)j rows:(NSInteger)rows cols:(NSInteger)cols visited:(BOOL**)visited grid:(NSArray
      
       )grid islandCount:(NSInteger*)islandCount {    if (i < 0 || j < 0 || i >= rows || j >= cols) return;        if (grid[i][j] == '1' && !visited[i][j]) {        visited[i][j] = true;        // 遍历四个方向        [self dfs:i+1 j:(int)j rows:rows cols:cols visited:visited grid:grid islandCount:islandCount];        [self dfs:i-1 j:(int)j rows:rows cols:cols visited:visited grid:grid islandCount:islandCount];        [self dfs:i j:(int)j+1 rows:rows cols:cols visited:visited grid:grid islandCount:islandCount];        [self dfs:i j:(int)j-1 rows:rows cols:cols visited:visited grid:grid islandCount:islandCount];    }}@end
      
     
    
   

代码解释

实现细节

• 边界条件处理：在DFS函数中，首先检查当前坐标是否超出网格范围。
• 标记访问：在发现新岛屿时，立即标记为已访问，避免重复计数。
• 四向遍历：确保所有相邻的同一数字单元格都被访问到。

测试示例

假设输入网格如下：

"01""10"

此时，岛屿数量为2。

结论

通过上述方法，我们可以高效地计算二维网格中的岛屿数量。DFS算法的时间复杂度为O(rows * cols)，适用于大多数实际场景。

转载地址：http://bhnfk.baihongyu.com/