Java算法精讲：岛屿数量与DFS/BFS应用

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

/**
 * 岛屿数量 - DFS实现
 */
public class NumberOfIslandsDFS {
    
    /**
     * 计算岛屿数量
     * @param grid 二维字符网格，'1'表示陆地，'0'表示水
     * @return 岛屿的数量
     */
    public static int numIslands(char[][] grid) {
        // 边界条件检查
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        
        int rows = grid.length;
        int cols = grid[0].length;
        int count = 0;
        
        // 遍历整个网格
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 如果当前单元格是陆地
                if (grid[i][j] == '1') {
                    // 岛屿数量加1
                    count++;
                    // 使用DFS将与当前陆地相连的所有陆地标记为已访问
                    dfs(grid, i, j, rows, cols);
                }
            }
        }
        
        return count;
    }
    
    /**
     * DFS遍历与当前陆地相连的所有陆地，并标记为已访问
     * @param grid 二维字符网格
     * @param i 当前行索引
     * @param j 当前列索引
     * @param rows 网格的行数
     * @param cols 网格的列数
     */
    private static void dfs(char[][] grid, int i, int j, int rows, int cols) {
        // 边界条件检查或当前单元格是水
        if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == '0') {
            return;
        }
        
        // 将当前陆地标记为已访问（通过将其改为水）
        grid[i][j] = '0';
        
        // 递归访问上、下、左、右四个方向的相邻单元格
        dfs(grid, i - 1, j, rows, cols);  // 上
        dfs(grid, i + 1, j, rows, cols);  // 下
        dfs(grid, i, j - 1, rows, cols);  // 左
        dfs(grid, i, j + 1, rows, cols);  // 右
    }
    
    // 测试代码
    public static void main(String[] args) {
        // 测试用例1
        char[][] grid1 = {
            {'1', '1', '1', '1', '0'},
            {'1', '1', '0', '1', '0'},
            {'1', '1', '0', '0', '0'},
            {'0', '0', '0', '0', '0'}
        };
        System.out.println("测试用例1的岛屿数量: " + numIslands(grid1));  // 预期输出: 1
        
        // 测试用例2
        char[][] grid2 = {
            {'1', '1', '0', '0', '0'},
            {'1', '1', '0', '0', '0'},
            {'0', '0', '1', '0', '0'},
            {'0', '0', '0', '1', '1'}
        };
        System.out.println("测试用例2的岛屿数量: " + numIslands(grid2));  // 预期输出: 3
    }
}

import java.util.LinkedList;
import java.util.Queue;

/**
 * 岛屿数量 - BFS实现
 */
public class NumberOfIslandsBFS {
    
    /**
     * 计算岛屿数量
     * @param grid 二维字符网格，'1'表示陆地，'0'表示水
     * @return 岛屿的数量
     */
    public static int numIslands(char[][] grid) {
        // 边界条件检查
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        
        int rows = grid.length;
        int cols = grid[0].length;
        int count = 0;
        
        // 遍历整个网格
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 如果当前单元格是陆地
                if (grid[i][j] == '1') {
                    // 岛屿数量加1
                    count++;
                    // 使用BFS将与当前陆地相连的所有陆地标记为已访问
                    bfs(grid, i, j, rows, cols);
                }
            }
        }
        
        return count;
    }
    
    /**
     * BFS遍历与当前陆地相连的所有陆地，并标记为已访问
     * @param grid 二维字符网格
     * @param i 当前行索引
     * @param j 当前列索引
     * @param rows 网格的行数
     * @param cols 网格的列数
     */
    private static void bfs(char[][] grid, int i, int j, int rows, int cols) {
        // 创建队列，用于BFS
        Queue<int[]> queue = new LinkedList<>();
        // 将当前陆地加入队列
        queue.offer(new int[]{i, j});
        // 将当前陆地标记为已访问
        grid[i][j] = '0';
        
        // 定义四个方向的偏移量：上、下、左、右
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        // BFS遍历
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int row = current[0];
            int col = current[1];
            
            // 检查四个方向的相邻单元格
            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];
                
                // 检查边界条件和是否是陆地
                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] == '1') {
                    // 将相邻的陆地加入队列
                    queue.offer(new int[]{newRow, newCol});
                    // 将相邻的陆地标记为已访问
                    grid[newRow][newCol] = '0';
                }
            }
        }
    }
    
    // 测试代码
    public static void main(String[] args) {
        // 测试用例1
        char[][] grid1 = {
            {'1', '1', '1', '1', '0'},
            {'1', '1', '0', '1', '0'},
            {'1', '1', '0', '0', '0'},
            {'0', '0', '0', '0', '0'}
        };
        System.out.println("测试用例1的岛屿数量: " + numIslands(grid1));  // 预期输出: 1
        
        // 测试用例2
        char[][] grid2 = {
            {'1', '1', '0', '0', '0'},
            {'1', '1', '0', '0', '0'},
            {'0', '0', '1', '0', '0'},
            {'0', '0', '0', '1', '1'}
        };
        System.out.println("测试用例2的岛屿数量: " + numIslands(grid2));  // 预期输出: 3
    }
}