Leetcode-岛屿数量（中等）

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和 / 或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

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

//先类比二叉树的遍历
/*void traverse(TreeNode root) {
    if (root == null) {  // 判断 base case
        return;
    }

traverse(root.left);// 访问两个相邻结点：左子结点、右子结点
traverse(root.right);
*/

//------------------------------------------
dfs的退出条件是：超出边界；遇到海水；遇到已遍历过的岛屿
遍历方向：上下左右
0 —— 海洋格子
1 —— 陆地格子（未遍历过）
2 —— 陆地格子（已遍历过）
遍历前标记该点为2（已遍历）

主函数中for循环遍历每个点，判断该点不是海水且未被遍历时dfs
dfs一次可以标记一整块岛屿
所以count++

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {//判断是否是未被遍历的陆地部分
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    void dfs(vector<vector<char>>& grid, int i, int j) {
        if (contour(grid, i, j)) return;//到达边界时退出 判断 base case
        if (grid[i][j] != '1') return;//海水时退出；已被遍历过退出；

        grid[i][j] = '2';//标记已被遍历过
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);//四个方向走
    }
    bool contour(vector<vector<char>>& grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size())
            return true;
        else return false;
    }
};