郑州做网站首选九零后网络,珠海网络公司排名,线上做网站赚钱,珠海企业建站文章目录1. 题目2. 解题2.1 BFS2.2 DFS1. 题目
给定一个二维的矩阵#xff0c;包含 ‘X’ 和 ‘O’#xff08;字母 O#xff09;。
找到所有被 ‘X’ 围绕的区域#xff0c;并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
示例:
X X X X
X O O X
X X O X
X O X X
运行你的…
文章目录1. 题目2. 解题2.1 BFS2.2 DFS1. 题目
给定一个二维的矩阵包含 ‘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(vectorvectorchar 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((i0 || im-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(vectorvectorchar board, int i, int j){queuepairint,int q;vectorvectorint dir {{-1,0},{1,0},{0,1},{0,-1}};q.push({i,j});pairint,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(x0 xm y0 yn board[x][y]O){q.push({x,y});board[x][y] -;}}}}
};2.2 DFS
class Solution {int m, n;
public:void solve(vectorvectorchar board) {if(board.empty())return;m board.size(), n board[0].size();int i, j;vectorvectorint dir {{-1,0},{1,0},{0,1},{0,-1}};for(i 0; i m; i){for(j 0; j n; j){if((i0 || im-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(vectorvectorchar board, int i, int j, vectorvectorint 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(x0 xm y0 yn board[x][y]O)DFS(board,x,y,dir);}}
};
