Leetcode 200. 岛屿数量 c++

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

主要思路：
1.如果发现当前点是岛屿，就把当前点涂色，然后push到任务队列中。
2.遍历队列，如果队列中的点的上下左右有岛屿，也涂色，并push到任务队列中。
3.直到队列空为止。

class Solution {
public:
    int numIslands(vector<vector<char>>& grid)
    {
        if (grid.size() == 0 || grid[0].size() == 0) {
            return 0;
        }
        int ret = 0;
        int height = grid.size();
        int width = grid[0].size();

        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (grid[i][j] == '1') {
                    Coloring(grid, i, j);
                    ret++;
                }
            }
        }
        Restore(grid);
        return ret;
    }

private:
    struct Pos {
        int row;
        int column;
    };
    // 给岛屿涂色2
    void Coloring(vector<vector<char>>& grid, int row, int column)
    {
        int top = 0;
        int bottom = grid.size() - 1;
        int left = 0;
        int right = grid[0].size() - 1;
        grid[row][column] = '2';
        queue<Pos> task;
        task.push({ row, column });
        while (!task.empty()){
            Pos pos = task.front();
            int i = pos.row;
            int j = pos.column;
            if (pos.row > top) {
                if (grid[i - 1][j] == '1') {
                    grid[i - 1][j] = '2';
                    task.push({ i - 1, j });
                }
            }
            if (i < bottom) {
                if (grid[i + 1][j] == '1') {
                    grid[i + 1][j] = '2';
                    task.push({ i + 1, j });
                }
            }
            if (j > left) {
                if (grid[i][j - 1] == '1') {
                    grid[i][j - 1] = '2';
                    task.push({ i, j - 1 });
                }
            }
            if (j < right) {
                if (grid[i][j + 1] == '1') {
                    grid[i][j + 1] = '2';
                    task.push({ i, j + 1 });
                }
            }
            task.pop();
        }
    }

    // 恢复数据
    void Restore(vector<vector<char>>& grid)
    {
        int height = grid.size();
        int width = grid[0].size();
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (grid[i][j] == '2') {
                    grid[i][j] = '1';
                }
            }
        }
    }
};