408算法题leetcode--第22天

200. 岛屿数量

• 200. 岛屿数量
• 时间：O(mn)；空间：O(min(m, n))，队列最大入队个数，可以想象从左上到右下，第一次入队1个，第二次出队1，入队2，第三次出队2，入队3…

class Solution {
public:int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};  // 右，下，左，上int count = 0;int row;int column;void bfs(vector<vector<char>>& grid, int x, int y){queue<pair<int, int>>q;q.push({x, y});while(!q.empty()){auto t = q.front();q.pop();for(int i = 0; i < 4; i++){int new_x = t.first + dir[i][0], new_y = t.second + dir[i][1];if(new_x < 0 || new_x >= row || new_y < 0 || new_y >= column){continue;}if(grid[new_x][new_y] != '1'){continue;}grid[new_x][new_y] = '0';  // 访问q.push({new_x, new_y});}}}int numIslands(vector<vector<char>>& grid) {// bfsrow = grid.size(), column = grid[0].size();for(int i = 0; i < row; i++){for(int j = 0; j < column; j++){if(grid[i][j] == '1'){bfs(grid, i, j);++count;}}}return count;}
};

695. 岛屿的最大面积

• 695. 岛屿的最大面积
• 同上，bfs

class Solution {
public:int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};  // 右，下，左，上int ret = 0;int row;int column;int bfs(vector<vector<int>>& grid, int x, int y){grid[x][y] = 0;queue<pair<int, int>>q;q.push({x, y});int square = 1;while(!q.empty()){auto t = q.front();q.pop();for(int i = 0; i < 4; i++){int new_x = t.first + dir[i][0], new_y = t.second + dir[i][1];if(new_x < 0 || new_x >= row || new_y < 0 || new_y >= column){continue;}if(grid[new_x][new_y] != 1){continue;}grid[new_x][new_y] = 0;  // 访问++square;q.push({new_x, new_y});}}return square;}int maxAreaOfIsland(vector<vector<int>>& grid) {// bfsrow = grid.size(), column = grid[0].size();for(int i = 0; i < row; i++){for(int j = 0; j < column; j++){if(grid[i][j] == 1){int temp = bfs(grid, i, j);ret = max(ret, temp);}}}return ret;}
};

547. 省份数量

• 547. 省份数量
• 思路：修改bfs的访问

class Solution {
public:int count = 0;int row;int column;void bfs(vector<vector<int>>& grid, int x, int y){grid[x][y] = grid[y][x] = 0;queue<pair<int, int>>q;q.push({x, y});while(!q.empty()){auto t = q.front();q.pop();int new_x = t.first;for(int i = 0; i < column; i++){if(grid[new_x][i] == 0){continue;}grid[new_x][i] = grid[i][new_x] = 0;  // 访问q.push({i, new_x});}}}int findCircleNum(vector<vector<int>>& isConnected) {// bfsrow = isConnected.size(), column = isConnected[0].size();for(int i = 0; i < row; i++){for(int j = 0; j < column; j++){if(isConnected[i][j] == 1){bfs(isConnected, i, j);++count;}}}return count;}
};