LeetCode - 岛屿数量

200. 岛屿数量

第一种写法：遍历岛屿，当遇到岛屿的时候，就开始进行深搜，遇到岛屿就将岛屿从1变为0。

class Solution {
public:

    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};

    void dfs(int i, int j, vector<vector<char>>& grid)
    {
        grid[i][j] = '0';

        for (int t = 0; t < 4; t++)
        {
            int x = i + dx[t];
            int y = j + dy[t];
            if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == '1')
            {
                bfs(x, y, grid);
            }
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        int ans = 0;

        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {
                if (grid[i][j] == '1')
                {
                    dfs(i, j, grid);
                    ans++;
                }
            }
        }
        return ans;

    }
};

第二种写法：扫描网格，进行宽搜，遇到1之后，就将1周围的岛屿加入队列，

class Solution {
public:

    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};

    void bfs(int i, int j, vector<vector<char>>& grid)
    {
        queue<pair<int,int>> q;
        q.push({i, j});
        while (!q.empty())
        {
            auto t = q.front();
            q.pop();
            int x = t.first;
            int y = t.second;
            if (grid[x][y] == '1')
            {
                grid[x][y] = '0';
                for (int tt = 0; tt < 4; tt++)
                {
                    int xx = x + dx[tt];
                    int yy= y + dy[tt];
                    if (xx >= 0 && xx < grid.size() && yy >= 0 && yy < grid[0].size())
                    {
                        q.push({xx, yy});
                    }
                }
            }
            else 
            {
                ;
            }
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        int ans = 0;

        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {
                if (grid[i][j] == '1')
                {
                    bfs(i, j, grid);
                    ans++;
                }
            }
        }
        return ans;

    }
};