目录
- 一、图像渲染
- 二、岛屿数量
- 三、岛屿的最大面积
- 四、被环绕的区域
一、图像渲染
题目：
思路：
- 如果起始位置的颜色(数值)与color相同，直接返回该数组
- 上下左右一层一层的找与当前位置颜色相同的，并且该位置不越界，然后放入队列（是先不越界，再比较是否颜色相同）
- 一个位置上下左右找完，将该位置的颜色变成color，然后pop
- 注意：push到队列的下标有重复的可能，就continue，但是，continue前要pop，不然会死循环
代码：
class Solution {
public:int dx[4] = {-1,1,0,0};//行 上下左右int dy[4] = {0,0,-1,1};//列 上下左右vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {int prev = image[sr][sc];// 起始位置的数字if(prev == color) return image;int row = image.size(), col = image[0].size();queue<pair<int,int>> q;q.push({sr, sc});while(!q.empty()){int k = q.size();while(k--){int x1 = q.front().first;int y1 = q.front().second;if(image[x1][y1] == color){q.pop();//!continue;}for(int i=0;i<4;i++){int x2 = x1 + dx[i];int y2 = y1 + dy[i];if(x2 >= 0 && x2 < row && y2 >= 0 && y2 < col && image[x1][y1] == image[x2][y2]){q.push({x2, y2});}}image[x1][y1] = color;q.pop();}}return image;}
};
二、岛屿数量
题目：
思路：BFS+队列
- 多一个bool类型的vim数组，初始化为false
- 与上一题几乎相同，两层for循环，符合条件的就count++；不需要担心重复，因为有vim数组标记是否已经用过了
- 队列——一层一层找字符1，当前位置的上下左右不越界、为字符1、没使用过的就进队列，然后当前位置标记为true（使用过了），队列头pop
- 最后返回count
代码：
class Solution {
public:int dx[4] = {-1,1,0,0};int dy[4] = {0,0,-1,1};int n = 0, m = 0, count = 0;bool vim[300][300] = {false};int numIslands(vector<vector<char>>& grid) {n = grid.size();m = grid[0].size();for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(grid[i][j] == '1' && !vim[i][j]){count++;Bfs(grid, i, j);}}}return count;}void Bfs(vector<vector<char>>& grid, int x, int y){queue<pair<int, int>> q;q.push({x, y});while(!q.empty()){int k = q.size();while(k--){int x1 = q.front().first;int y1 = q.front().second;if(vim[x1][y1]){q.pop();continue;}for(int i=0; i<4; i++){int x2 = x1+dx[i];int y2 = y1+dy[i];if(x2>=0&&x2<n&&y2>=0&&y2<m && grid[x2][y2]=='1' && !vim[x2][y2]){q.push({x2, y2});}}vim[x1][y1] = true;q.pop();}}}
};
三、岛屿的最大面积
题目：
思路：BFS+队列
- 与上题思路相同，但是上题求的是岛屿数量，本题是岛屿的最大面积，都是用变量count计数，只是执行count++的位置不同。然后一个岛屿好了（队列为空）就更新下最大值
代码：
class Solution {
public:int dx[4] = {-1,1,0,0};int dy[4] = {0,0,-1,1};int n = 0, m = 0, Max = 0;bool vim[50][50] = {false};int maxAreaOfIsland(vector<vector<int>>& grid) {n = grid.size();m = grid[0].size();for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(grid[i][j] == 1 && !vim[i][j]){Bfs(grid, i, j);}}}return Max;}void Bfs(vector<vector<int>> &grid, int x, int y){queue<pair<int, int>> q;int count = 0;// 临时的 一个岛屿的面积q.push({x, y});while(!q.empty()){int k = q.size();while(k--){// push上下左右int x1 = q.front().first;int y1 = q.front().second;if(vim[x1][y1])//!{q.pop();continue;}for(int i=0; i<4; i++){int x2 = x1+dx[i];int y2 = y1+dy[i];if(x2>=0&&x2<n&&y2>=0&&y2<m && grid[x2][y2]==1 && !vim[x2][y2]){q.push({x2, y2});}}// count++;vim[x1][y1] = true;q.pop();}}// 更新Maxif(count > Max) Max = count;}
};
四、被环绕的区域
题目：
思路：Bfs+队列
- 与上题思路类似
- 正难则反，先从边界的位置入手，如果该岛屿是有临边界的，就不能变成X；反之，排除了边界的岛屿，那么只剩下中间的岛屿，就要全部变成X
- 是边界的岛屿还要用另一个bool数组标记，最终标记过的就不用变成X，其他的全都要变成X
代码：
class Solution {
public:int dx[4] = {-1,1,0,0};int dy[4] = {0,0,-1,1};int n = 0, m = 0;bool vim[200][200] = {false};// 是否使用过bool flag[200][200] = {false};// 是否要变成Xvoid solve(vector<vector<char>>& board) {n = board.size();m = board[0].size();for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(i>0 && i<n-1 && j>0 && j<m-1){continue;}if(board[i][j] == 'O' && !vim[i][j]){Bfs(board, i, j);}}}for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(!flag[i][j]){board[i][j] = 'X';}}}}void Bfs(vector<vector<char>>& board, int x, int y){queue<pair<int, int>> q;q.push({x, y});while(!q.empty()){int k = q.size();while(k--){int x1 = q.front().first;int y1 = q.front().second;if(vim[x1][y1]){q.pop();continue;}for(int i=0;i<4;i++){int x2 = x1+dx[i];int y2 = y1+dy[i];if(x2>=0&&x2<n&&y2>=0&&y2<m && board[x2][y2] == 'O' && !vim[x2][y2]){q.push({x2, y2});}}vim[x1][y1] = true;flag[x1][y1] = true;q.pop();}}}
};
