200. 岛屿数量

深度优先搜索

class Solution {

    int m;
    int n;
    int sum;
    boolean[][] used;
    int[][] move = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int numIslands(char[][] grid) {

        m = grid.length;
        n = grid[0].length;
        used = new boolean[m][n];

        /**
         * 如果一个位置为1，则以其为起始节点开始进行搜索
         * 最终岛屿的数量就是进行深度优先搜索的次数
         */
        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                if (grid[i][j] == '1' && !used[i][j]){

                    sum++;
                    dfs(grid, i, j);
                }
            }
        }

        return sum;
    }

    /**
     * 每次遍历到一个1就标记为已使用
     * 再从四周寻找下一个没有遍历过的1
     */
    public void dfs(char[][] grid, int row, int col){

        used[row][col] = true;

        for (int i = 0; i < 4; i++) {

            int newRow = row + move[i][0];
            int newCol = col + move[i][1];

            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == '1' && !used[newRow][newCol]){
                dfs(grid, newRow, newCol);
            }
        }
    }
}

/**
 * 时间复杂度 O(m×n)
 * 空间复杂度 O(m×n)
 */

https://leetcode-cn.com/problems/number-of-islands/