【LeetCode热题100】【图论】岛屿数量

题目链接：200. 岛屿数量 - 力扣（LeetCode）

考察图的遍历，从岛上上下左右能到达的地方都是这个岛

首先需要判断图的边界，然后再上下左右继续深度遍历，并把遍历到的标记为已访问，可以原地修改图做标记

对于这道题来说，从是1的地方深度遍历，改写可以到达的地方，这样就是一个岛屿，如果还有1，说明还有岛屿

class Solution {
public:
    int rows, columns;
    vector<vector<char> > grid;

    bool isValid(int x, int y) {
        return x >= 0 && y >= 0 && x < rows && y < columns;
    }

    void dfs(int x, int y) {
        if (isValid(x, y) == false || grid[x][y] != '1')
            return;
        grid[x][y] = '2';
        dfs(x - 1, y);
        dfs(x + 1, y);
        dfs(x, y - 1);
        dfs(x, y + 1);
    }

    int numIslands(vector<vector<char> > &grid) {
        rows = grid.size();
        columns = grid[0].size();
        this->grid = move(grid);
        int ans = 0;
        for (int i = 0; i < rows; ++i)
            for (int j = 0; j < columns; ++j)
                if (this->grid[i][j] == '1') {
                    dfs(i, j);
                    ++ans;
                }
        return ans;
    }
};