[力扣题解] 200. 岛屿数量
题目：200. 岛屿数量
思路
深度优先搜索、广度优先搜索、并查集；
代码
广度优先搜索
class Solution {
public:int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};queue<pair<int, int>> que;void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y){int cur_x, cur_y, next_x, next_y;int i, j;int m = grid.size(), n = grid[0].size();while(!que.empty()){pair cur = que.front();que.pop();cur_x = cur.first;cur_y = cur.second;for(i = 0; i < 4; i++){next_x = cur_x + dir[i][0];next_y = cur_y + dir[i][1];if(next_x < 0 || next_x >= m || next_y < 0 || next_y >= n){continue;}if(!visited[next_x][next_y] && grid[next_x][next_y] == '1'){visited[next_x][next_y] = true;que.push({next_x, next_y});}}}}int numIslands(vector<vector<char>>& grid) {int m = grid.size(), n = grid[0].size();int i, j;int result = 0;vector<vector<bool>> visited (m, vector<bool>(n, false));for(i = 0; i < m; i++){for(j = 0; j < n; j++){if(!visited[i][j] && grid[i][j] == '1'){visited[i][j] = true;que.push({i, j});result++;bfs(grid, visited, i, j);}}}return result;}
};
注意此时，只要加入队列就视为已遍历；
深度优先搜索
class Solution {
private:int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};void function(vector<vector<char>>& grid, vector<vector<int>>& visited, int x, int y){int i, j;int m = grid.size(), n = grid[0].size();int next_x, next_y;// 这里递归结束条件其实可以不用写// if()for(i = 0; i < 4; i++){next_x = x + dir[i][0];next_y = y + dir[i][1];// 检查是否还在框框里if(next_x < 0 || next_x >= m || next_y < 0 || next_y >= n){continue;}if(!visited[next_x][next_y] && grid[next_x][next_y] == '1'){visited[next_x][next_y] = true;function(grid, visited, next_x, next_y);}}}public:int numIslands(vector<vector<char>>& grid) {int i, j;int result = 0;int m = grid.size(), n = grid[0].size();vector<vector<bool>> visited(m, vector<bool>(n, false));for(i = 0; i < m; i++){for(j = 0; j < n; j++){if(!visited[i][j] && grid[i][j] == '1'){visited[i][j] = true;result++;function(grid, visited, i, j);}}}return result;}
};