題目鏈接

Leetcode.130 被圍繞的區(qū)域 mid

題目描述

給你一個(gè) m x n的矩陣 board，由若干字符 'X'和 'O'，找到所有被 'X'圍繞的區(qū)域，并將這些區(qū)域里所有的 '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”]]
解釋：被圍繞的區(qū)間不會(huì)存在于邊界上，換句話說(shuō)，任何邊界上的 ‘O’ 都不會(huì)被填充為 ‘X’。 任何不在邊界上，或不與邊界上的 ‘O’ 相連的 ‘O’ 最終都會(huì)被填充為 ‘X’。如果兩個(gè)元素在水平或垂直方向相鄰，則稱它們是“相連”的。

示例 2：

輸入：board = [[“X”]]
輸出：[[“X”]]

提示：

• $m==board.length$
• $n==board[i].length$
• $1<=m,n<=200$
• board[i][j]為 'X'或 'O'

解法：dfs

我們先從 $board$ 的四周，與邊界相鄰的 $board[i][j]=$ ’O'的區(qū)域記錄下來(lái)，這些區(qū)域是不能被 'X'填充的。

接著，剩下的 $board[i][j]=$ ’O'的區(qū)域才是能被 'X'填充的。

時(shí)間復(fù)雜度： $O(mn)$

C++代碼：

class Solution {
public:void solve(vector<vector<char>>& g) {int m = g.size() , n = g[0].size();//記錄是否被訪問(wèn)過(guò)bool vis[m][n];memset(vis,false,sizeof vis);function<void(int ,int,bool)> dfs = [&](int i,int j,bool mode) -> void{if(i < 0 || i >= m || j < 0 || j >= n || vis[i][j]) return;if(g[i][j] == 'X') return;vis[i][j] = true;if(mode) g[i][j] = 'X';dfs(i + 1,j,mode);dfs(i - 1,j,mode);dfs(i,j + 1,mode);dfs(i,j - 1,mode);};//記錄從左右兩邊開(kāi)始的 不能被 'X' 填充的位置for(int i = 0;i < m;i++){if(g[i][0] == 'O' && !vis[i][0]) dfs(i,0,false);if(g[i][n-1] == 'O' && !vis[i][n-1]) dfs(i,n-1,false);}//記錄從上下兩邊開(kāi)始的 不能被 'X' 填充的位置for(int j = 0;j < n;j++){if(g[0][j] == 'O' && !vis[0][j]) dfs(0,j,false);if(g[m-1][j] == 'O' && !vis[m-1][j]) dfs(m-1,j,false);}//剩下的 g[i][j] == 'O' 并且沒(méi)有被訪問(wèn)過(guò)的位置 都可以被 'X'填充for(int i = 1;i < m - 1;i++){for(int j = 1;j < n - 1;j++){if(g[i][j] == 'O' && !vis[i][j]) dfs(i,j,true);}}}
};