个人主页:C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创BFS解决FloodFill算法(4)_被围绕的区域
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记,欢迎大家在评论区交流讨论💌
目录
1. 题目链接
2. 题目描述
3. 解法
算法思路:
代码展示:
4. 算法总结
1. 题目链接
OJ链接 : 被围绕的区域https://leetcode.cn/problems/surrounded-regions/description/
2. 题目描述
给你一个 m x n
的矩阵 board
,由若干字符 'X'
和 'O'
组成,捕获 所有 被围绕的区域:
- 连接:一个单元格与水平或垂直方向上相邻的单元格连接。
- 区域:连接所有
'O'
的单元格来形成一个区域。 - 围绕:如果您可以用
'X'
单元格 连接这个区域,并且区域中没有任何单元格位于board
边缘,则该区域被'X'
单元格围绕。
通过将输入矩阵 board
中的所有 'O'
替换为 'X'
来 捕获被围绕的区域。
示例 1:
输入:board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出:[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释:
在上图中,底部的区域没有被捕获,因为它在 board 的边缘并且不能被围绕。
示例 2:
输入:board = [["X"]]
输出:[["X"]]
提示:
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j]
为'X'
或'O'
3. 解法
算法思路:
正难则反, 可以先利用bfs将与边缘相连的 '0'区域做上标记, 然后重新遍历矩阵, 将没有标记过的 '0'修改成 'X'即可.
代码展示:
class Solution {int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;
public:void solve(vector<vector<char>>& board) {n = board.size(), m = board[0].size();//将边缘'0'坐上标记for(int i = 0; i < m; i++){if(board[0][i] == 'O') bfs(board, 0, i);if(board[n -1][i] == 'O') bfs(board, n - 1, i);}for(int j = 0; j < n; j++){if(board[j][0] == 'O') bfs(board, j, 0);if(board[j][m - 1] == 'O') bfs(board, j, m - 1);}for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)if(board[i][j] == 'O') board[i][j] = 'X';else if(board[i][j] == '.') board[i][j] = 'O';}void bfs(vector<vector<char>>& board, int i, int j){queue<pair<int, int>> q;q.push({i, j});board[i][j] = '.';while(q.size()){auto [x, y] = q.front();q.pop();for(int k = 0; k < 4; k++){int a = dx[k] + x, b = dy[k] + y;if(a >= 0 && a < n && b >= 0 && b < m && board[a][b] == 'O'){q.push({a, b});board[a][b] = '.';}}}}
};
4. 算法总结
初始化方向数组:
定义两个数组 dx 和 dy 来表示四个方向(上下左右)的偏移。
获取矩阵的尺寸:
获取矩阵的行数 n 和列数 m。
标记边缘的 'O':
遍历矩阵的四条边(上、下、左、右),对每个边上的 'O' 进行 BFS 标记:
如果边缘的某个位置是 'O',则调用 BFS 函数,将该 'O' 及其所有相连的 'O' 标记为 '.'。
遍历整个矩阵:
再次遍历整个矩阵:
将仍为 'O' 的元素转换为 'X'(表示被包围)。
将标记为 '.' 的元素恢复为 'O'(表示未被包围)。
BFS 函数:
使用队列进行 BFS,从传入的起始坐标开始:
将当前坐标的 'O' 转换为 '.'。
遍历四个方向,若相邻位置为 'O',则将其加入队列并标记为 '.'。
总结 :
该算法通过 BFS 在边缘 'O' 的基础上进行标记, 确保与边缘相连的 'O' 不会被错误地转为 'X', 最后的遍历操作则负责将所有被包围的 'O' 转为 'X', 同时恢复未包围的 'O', 时间复杂度为 O(n * m), 其中n和m分别为矩阵的行和列数