LintCode 433. Number of Islands 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/number-of-islands/

[
  [1, 1, 0, 0, 0],
  [0, 1, 0, 0, 1],
  [0, 0, 0, 1, 1],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1]
]

解题思路

题意是相邻的1算作是同一个岛，求岛屿数量。

1. 这道题用DFS深度优先搜索的方法最为直观，也容易理解。
2. 两重循环遍历1的位置，0则忽略。然后从找到的1位置深度优先搜索，上下左右搜索，并把遇到的1都变成0。每进行一次DFS，岛屿计数+1。

参考代码

public class Solution { 
    /** 
     * @param grid a boolean 2D matrix 
     * @return an integer 
     */ 
      
    private int m; 
    private int n; 
    public int numIslands(boolean[][] grid) { 
        m = grid.length; 
        if (m == 0) { 
            return 0; 
        } 
        n = grid[0].length; 
        if (n == 0) { 
            return 0; 
        }         
         
        int count = 0; 
        for (int i = 0; i < m; i++) { 
            for (int j = 0; j < n; j++) { 
                if (!grid[i][j]) { 
                    continue; 
                } 
                count++; 
                dfs(grid, i, j); 
            } 
        } 
        return count; 
    } 
     
    private void dfs(boolean[][] grid, int i, int j) { 
        if (i < 0 || i >= m || j < 0 || j >= n) { 
            return; 
        } 
         
        if (grid[i][j]) { 
            grid[i][j] = false; 
            dfs(grid, i - 1, j); 
            dfs(grid, i + 1, j); 
            dfs(grid, i, j - 1); 
            dfs(grid, i, j + 1); 
        } 
    } 
}  

相关题目

LintCode All in One 原创题目讲解汇总