200. Number of Islands

Published on April 6, 2023

Question

Given a two-dimensional array grid, 1 represents land, 0 represents sea water, a piece of connected land is called an island, and calculate how many islands there are. Connectivity can be understood as up, down, left, and right 1 and 1 are adjacent.

Input: grid = [
   ["1","1","1","1","0"],
   ["1","1","0","1","0"],
   ["1","1","0","0","0"],
   ["0","0","0","0","0"]
]
Output: 1

Algorithm

This topic is to start traversing each point, and the islands connected to it are marked as visited. Traverse the entire grid, if it is 1 and has not been traversed (does not belong to the previous island), you can add one to the result and start traversing a new island from then on.

Traversal can use recursive or iterative depth-first traversal or breadth-first traversal.

Code

class Solution {
    boolean[][] visited;
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
            return 0;
        }
        int res = 0;
        visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    dfs(grid, i, j, visited);
                    res++;
                }
            }
        }
        return res;
    }
    
    private void dfs(char[][] grid, int i, int j, boolean[][] visited) {
        Stack<int[]> stack = new Stack();
        stack.push(new int[]{i, j});
        visited[i][j] = true;
        while (!stack.isEmpty()) {
            int[] pair = stack.pop();
            int row = pair[0];
            int col = pair[1];
            if (row - 1 >= 0 && grid[row-1][col] == '1' && !visited[row-1][col]) {
                stack.push(new int[]{row-1, col});
                visited[row-1][col] = true;
            }
            if (row + 1 < grid.length && grid[row+1][col] == '1' && !visited[row+1][col]) {
                stack.push(new int[]{row+1, col});
                visited[row+1][col] = true;
            }
            if (col - 1 >= 0 && grid[row][col-1] == '1' && !visited[row][col-1]) {
                stack.push(new int[]{row, col-1});
                visited[row][col-1] = true;
            }
            if (col + 1 < grid[0].length && grid[row][col+1] == '1' && !visited[row][col+1]) {
                stack.push(new int[]{row, col+1});
                visited[row][col+1] = true;
            }
        }
    }
}

题目

给一个二维数组grid，1代表陆地，0代表海水，一块连通的陆地称为一个岛，计算有多少个岛屿。连通可以理解为上下左右1和1相邻。

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

算法

这个题目就是通过对每一个点开始进行遍历，与之相连的岛屿标记为visited。遍历整个grid，如果他是1且还没被遍历过（不属于之前的岛屿），则可以将结果加一并从此开始新一个岛屿的遍历。

遍历可以使用递归或者迭代形式的深度优先遍历或者广度优先遍历。

代码

class Solution {
    boolean[][] visited;
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
            return 0;
        }
        int res = 0;
        visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    dfs(grid, i, j, visited);
                    res++;
                }
            }
        }
        return res;
    }
    
    private void dfs(char[][] grid, int i, int j, boolean[][] visited) {
        Stack<int[]> stack = new Stack();
        stack.push(new int[]{i, j});
        visited[i][j] = true;
        while (!stack.isEmpty()) {
            int[] pair = stack.pop();
            int row = pair[0];
            int col = pair[1];
            if (row - 1 >= 0 && grid[row-1][col] == '1' && !visited[row-1][col]) {
                stack.push(new int[]{row-1, col});
                visited[row-1][col] = true;
            }
            if (row + 1 < grid.length && grid[row+1][col] == '1' && !visited[row+1][col]) {
                stack.push(new int[]{row+1, col});
                visited[row+1][col] = true;
            }
            if (col - 1 >= 0 && grid[row][col-1] == '1' && !visited[row][col-1]) {
                stack.push(new int[]{row, col-1});
                visited[row][col-1] = true;
            }
            if (col + 1 < grid[0].length && grid[row][col+1] == '1' && !visited[row][col+1]) {
                stack.push(new int[]{row, col+1});
                visited[row][col+1] = true;
            }
        }
    }
}