200. 岛屿数量（DFS）

200. 岛屿数量

• 题目
• 解题思路
• 代码

题目

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 ‘0’ 或 ‘1’

解题思路

该题也是求可达性的一种问题，所以要用DFS来解决。加上本题和695题十分相似，于是只要稍加改动就可以了。
695是求岛屿最大面积，当时的做法是得到一个岛屿的面积就存到res，然后和下一个岛屿的面积相比较，只保留最大的那个
岛屿面积在res中。

试想一下，你每得到一个岛屿的面积就意味着那肯定有一个岛。该题要我们求岛的数量，我们就可以把每一个岛的岛屿面积存入一个LIST
到时候LIST中有几个数据 不就证明有几个岛。

代码

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

        if (grid.length == 0) {
            return 0;
        }

        List<Integer> res = new ArrayList<>();//用来存放结果

        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == '1') {
                    int area = DFS(grid, r, c);
                    res.add(area);//把每个岛屿的面积都添加岛res中
                }
            }


        }
        return res.size();
    }


    public int DFS(char[][] grid, int r, int c) {
        if (!(0 <= r && r < grid.length && 0 <= c && c < grid[0].length)) {//超出了边缘，走不下去了
            return 0;
        }

        if (grid[r][c] != '1') {//不是岛屿也返回，因为岛屿要相连的1，一旦出现0就要返回
            return 0;
        }

        grid[r][c] = '0';//沉岛

        int area = 1;

        area += DFS(grid, r - 1, c);//向上遍历
        area += DFS(grid, r + 1, c);//向下遍历
        area += DFS(grid, r, c - 1);//向左遍历
        area += DFS(grid, r, c + 1);//向右遍历


        return area;
    }
}