LeetCode 130. 被围绕的区域（图的BFS/DFS）
LeetCode 130. 被围绕的区域（图的BFS/DFS）
Michael阿明
发布于 2020-07-13 15:38:51
发布于 2020-07-13 15:38:51
1. 题目
给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。
找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
示例:
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解释: 任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/surrounded-regions 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- 对四周的
O进行BFS或者DFS，将其改为- - 最后将
O改成X，将-改成O
2.1 BFS
class Solution {
int m, n;
public:
void solve(vector<vector<char>>& board) {
if(board.empty())
return;
m = board.size(), n = board[0].size();
int i, j;
for(i = 0; i < m; ++i)
{
for(j = 0; j < n; ++j)
{
if((i==0 || i==m-1 || j == 0 || j == n-1) && board[i][j] == 'O')
BFS(board,i,j);
}
}
for(i = 0; i < m; ++i)
{
for(j = 0; j < n; ++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;
vector<vector<int>> dir = {{-1,0},{1,0},{0,1},{0,-1}};
q.push({i,j});
pair<int,int> tp;
board[i][j] = '-';
int k, x, y;
while(!q.empty())
{
tp = q.front();
q.pop();
for(k = 0; k < 4; ++k)
{
x = dir[k][0]+tp.first;
y = dir[k][1]+tp.second;
if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='O')
{
q.push({x,y});
board[x][y] = '-';
}
}
}
}
};2.2 DFS
class Solution {
int m, n;
public:
void solve(vector<vector<char>>& board) {
if(board.empty())
return;
m = board.size(), n = board[0].size();
int i, j;
vector<vector<int>> dir = {{-1,0},{1,0},{0,1},{0,-1}};
for(i = 0; i < m; ++i)
{
for(j = 0; j < n; ++j)
{
if((i==0 || i==m-1 || j == 0 || j == n-1) && board[i][j] == 'O')
DFS(board,i,j,dir);
}
}
for(i = 0; i < m; ++i)
{
for(j = 0; j < n; ++j)
{
if(board[i][j] == 'O')
board[i][j] = 'X';
else if(board[i][j] == '-')
board[i][j] = 'O';
}
}
}
void DFS(vector<vector<char>>& board, int i, int j, vector<vector<int>> &dir)
{
board[i][j] = '-';
int x, y;
for(int k = 0; k < 4; ++k)
{
x = dir[k][0]+i;
y = dir[k][1]+j;
if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='O')
DFS(board,x,y,dir);
}
}
};
在这里插入图片描述
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-10-30 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录