dfs例题 130. 被围绕的区域
dfs例题
:
130. 被围绕的区域
给你一个 m x n 的矩阵 board ,由若干字符 X 和 O ,找到所有被 X 围绕的区域,并将这些区域里所有的 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"]] 解释:被围绕的区间不会存在于边界上,换句话说,任何边界上的 O 都不会被填充为 X。
任何不在边界上,或不与边界上的 O 相连的 O 最终都会被填充为 X。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。
示例 2:
输入:board = [["X"]] 输出:[["X"]]
编辑于just now
嵌入
克隆
code.cpp919字节
class Solution { public: int m , n; void dfs(int x, int y,vector<vector<char>>& board){ if(x<0||y<0||x>=m||y>=n||board[x][y]!=O){ return; } board[x][y] = A; dfs(x-1, y, board); dfs(x+1, y, board); dfs(x, y-1, board); dfs(x, y+1, board); } void solve(vector<vector<char>>& board) { m = board.size(); n = board[0].size(); for(int i = 0; i < n; i++){ dfs(0, i, board); dfs(m-1, i, board); } for(int i = 0; i < m; i++){ dfs(i, 0, board); dfs(i, n-1, board); } for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(board[i][j]==A){ board[i][j] = O; }else if(board[i][j]==O){ board[i][j] = X; } } } } };