文章目录
- 图像渲染
- 岛屿数量
- 岛屿的最大面积
- 被围绕的区域
FloodFill（洪水灌溉）
颜色填充
想Windows画图板中的油漆点一下可以把一个联通的块儿全部染色
本质就是找一块区域里性质相同的联通块
图像渲染
题目：图像渲染
思路
BFS一层一层搜索，等于修改的
C++代码
class Solution
{int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};
public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {int oldColor = image[sr][sc]; // 先标记需要修改的像素值if(oldColor == color) return image;queue<pair<int, int>> q;q.push({sr, sc});int m = image.size(), n = image[0].size();while(q.size()){auto [a, b] = q.front();q.pop();image[a][b] = color; // 修改当前位置的颜色for (int i = 0; i < 4; i++) {int x = a + dx[i];int y = b + dy[i];// 判断新的坐标是否越界，并且颜色与旧颜色相同if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == oldColor) {q.push({x, y});}}}return image;}
};
岛屿数量
题目：岛屿数量
思路
- 初始化
- 创建一个二维布尔数组
visited来跟踪哪些单元格已经被访问过 - 初始化岛屿计数器
ret = 0
- 使用两个嵌套的循环遍历网格中的每个单元格
- 对于每个单元格，检查它是否是陆地
1且尚未被访问过，如果满足条件，说明我们找到了一个新的岛屿 BFS从当前陆地单元格开始搜索整个岛屿，使用队列来迭代地访问它们，在搜索过程中，将访问过的单元格标记为已访问，即在visited数组中设置为true- 每次成功搜索完一个岛屿后，将岛屿计数器
ret++
C++代码
class Solution
{ // 方向数组 vector<int> dx = {0, 0, 1, -1}; vector<int> dy = {1, -1, 0, 0}; vector<vector<bool>> visited; int m, n; // m 表示行数，n 表示列数 int ret; // 岛屿数量 queue<pair<int, int>> q; void bfs(const vector<vector<char>>& grid, int i, int j) { q.push({i, j}); // 起点入队 visited[i][j] = true; // 标记已经遍历 while (!q.empty()) { auto [a, b] = q.front(); q.pop(); for (int k = 0; k < 4; ++k){ // 注意这里应该是 ++k 而不是 i++ int x = a + dx[k]; int y = b + dy[k]; // 判断新的坐标是否越界，并且是岛屿的一部分 if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] == '1' && !visited[x][y]) { q.push({x, y}); visited[x][y] = true; } } } } public: int numIslands(vector<vector<char>>& grid) { m = grid.size(); n = grid[0].size(); visited.resize(m, vector<bool>(n, false)); // 初始化 visited 数组 ret = 0; // 初始化岛屿数量 for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == '1' && !visited[i][j]) { ret++; // 发现新的岛屿，岛屿数量加一 bfs(grid, i, j); // 遍历、标记属于同一岛屿的位置 } } } return ret; }
};
岛屿的最大面积
题目：岛屿的最大面积
思路
- 初始化最大岛屿面积为0，以及获取网格的行数和列数
- 遍历网格中的每一个格子，如果当前格子是陆地
1，则调用bfs函数进行广度优先搜索，并更新最大岛屿面积
C++代码
class Solution
{// 方向数组 int dx[4] = {0, 0, 1, -1};int dy[4] = {-1, 1, 0, 0};queue<pair<int, int>> q; int m, n; // m 表示行数，n 表示列数 // BFS 函数，从起点 (i, j) 开始遍历并标记属于同一岛屿的所有位置int bfs(vector<vector<int>>& grid, int i, int j) {int count = 1; // 记录岛屿的大小q.push({i, j}); // 将起点入队grid[i][j] = 0; // 标记已经遍历过的位置while (q.size()) {auto [a, b] = q.front();q.pop();for (int k = 0; k < 4; ++k) {int x = a + dx[k], y = b + dy[k];// 判断新的坐标是否越界，并且是岛屿的一部分if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] == 1) {grid[x][y] = 0; // 标记已经遍历过的位置count++; // 增加岛屿的大小q.push({x, y}); // 将相邻的岛屿位置入队}}}return count;}public:int maxAreaOfIsland(vector<vector<int>>& grid) {int ret = 0; // 记录最大岛屿面积m = grid.size(); // 获取行数n = grid[0].size(); // 获取列数// 遍历整个网格for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == 1) {ret = max(ret, bfs(grid, i, j)); // 更新最大岛屿面积}}}return ret; }
};
被围绕的区域
题目：被围绕的区域
思路
- 从矩阵的边界开始，遍历所有边界上的元素
- 如果边界上的元素是
O，则使用BFS遍历所有与该O相连的元素，并将它们标记为已访问（替换为S） - 在完成边界上的所有
O的遍历后，矩阵中剩余的O即为被围绕的区域 - 最后，将剩余的
O替换为X，并将之前标记为已访问的字符（如S）还原为O
C++代码
class Solution
{const int dx[4] = {0, 0, 1, -1}; const int dy[4] = {-1, 1, 0, 0};int m, n; // m 表示行数，n 表示列数queue<pair<int, int>> q; // BFS 函数，从起点 (i, j) 开始遍历并标记属于同一区域的所有位置void bfs(vector<vector<char>>& board, int i, int j) {q.push({i, j}); // 将起点入队board[i][j] = 'S'; // 标记已经遍历过的位置while (q.size()) {auto [a, b] = q.front();q.pop();for (int k = 0; k < 4; ++k) {int x = a + dx[k], y = b + dy[k];// 判断新的坐标是否越界，并且是未被围绕的区域if (0 <= x && x < m && 0 <= y && y < n && board[x][y] == 'O') {board[x][y] = 'S'; // 标记已经遍历过的位置q.push({x, y}); // 将相邻的未被围绕的区域位置入队}}}}public:void solve(vector<vector<char>>& board) {m = board.size(); n = board[0].size(); // 对边界上的'O'进行BFS遍历，标记为'S'for (int i = 0; i < n; ++i) {if (board[0][i] == 'O') bfs(board, 0, i);if (board[m - 1][i] == 'O') bfs(board, m - 1, i);}for (int i = 1; i < m - 1; ++i) {if (board[i][0] == 'O') bfs(board, i, 0);if (board[i][n - 1] == 'O') bfs(board, i, n - 1);}// 遍历整个网格，将未被标记的'O'修改为'X'，已经标记的'S'修改回'O'for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (board[i][j] == 'S') board[i][j] = 'O';else if (board[i][j] == 'O') board[i][j] = 'X';}}}
};
