FloodFill算法——力扣被围绕的区域

本文主要是介绍FloodFill算法——力扣被围绕的区域，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

题目解析
算法解析
代码解析

题目解析

被围绕的区域
在这里插入图片描述
我们来解读一下这个题目，这个题目的意思就是求出被X围绕的O有多少个，那么什么是被围绕呢？也就是没有出路并且连通的O不能到四条边上，这就算是被围绕了，可是即使知道了这些信息我们依旧头大因为，太难分析了我们遇到一个O之后还得去看看这一块儿O是不是被围绕的如果不是被围绕的还得去将他们回复成原来的O很难的了。那么咱么办呢？

算法解析

那么我们就反其道而行之，怎么反其道而行之呢？很简单那就是求没有被围绕的O然后将这些O变成随便的一个字符只要不是X或者O就行然后再将此时剩下的O全部变成X把你当时转换的字符重新转换成O就可以了，那么我们就要知道哪些O是不能被围绕的呢？上面说了嘛只要是在四条边上的O肯定都不能被围绕所以我们只需要找到四条边上的O以及与四条边上的O相连的就可以了。

代码解析

class Solution {
public:int dx[4] = { 0,0,-1,1 };int dy[4] = { 1,-1,0,0 };void solve(vector<vector<char>>& board) {int m = board.size();int n = board[0].size();for (int j = 0; j < n; j++) {if(board[0][j]=='O'){board[0][j]='*';bfs(board,0,j);    }}for (int j = 0; j < m; j++) {if(board[j][0]=='O'){board[j][0]='*';bfs(board,j,0);    }}for (int j = 0; j <m; j++) {if(board[j][n-1]=='O'){board[j][n-1]='*';bfs(board,j,n-1);    }}for (int j = 0; j <n; j++) {if(board[m-1][j]=='O'){board[m-1][j]='*';bfs(board,m-1,j);    }}for(int i=0;i<m;i++){for(int j=0;j<n;j++){//cout<<board[i][j]<<' ';if(board[i][j]=='O'){board[i][j]='X';}else if(board[i][j]=='*'){board[i][j]='O';}}//cout<<endl;}}void bfs(vector<vector<char>>& board, int i, int j) {queue<pair<int, int>>q;q.push({ i,j });while (q.size()) {auto [a, b] = q.front();q.pop();for (int i = 0; i < 4; i++) {int x = a + dx[i];int y = b + dy[i];if(x>=0&&y>=0&&x<board.size()&&y<board[0].size()&&board[x][y]=='O'){board[x][y]='*';q.push({x,y});}}}}
};