130. Surrounded Regions
你得到一個 m x n 的矩陣 board，其中包含字母 'X' 和 'O'，請捕獲被包圍的區域：
連接：一個單元格可以水平或垂直連接到相鄰的單元格。 區域：連接每個 'O' 單元格來形成一個區域。 包圍：如果你可以用 'X' 單元格包圍這個區域，並且該區域中的所有單元格都不在棋盤的邊緣，那麼這個區域就被包圍了。 被包圍的區域通過將輸入矩陣 board 中的所有 'O' 替換為 'X' 來捕獲。
範例：
輸入：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"]]
解釋：
在上圖中，底部的區域沒有被捕獲，因為它在棋盤的邊緣，不能被包圍。
Python
from typing import List
class Solution:
def solve(self, board: List[List[str]]) -> None:
if not board or not board[0]:
return
rows, cols = len(board), len(board[0])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != 'O':
return
board[r][c] = 'A'
for dr, dc in directions:
dfs(r + dr, c + dc)
# Step 1: Mark the 'O's that are connected to the borders
for i in range(rows):
if board[i][0] == 'O':
dfs(i, 0)
if board[i][cols - 1] == 'O':
dfs(i, cols - 1)
for j in range(cols):
if board[0][j] == 'O':
dfs(0, j)
if board[rows - 1][j] == 'O':
dfs(rows - 1, j)
# Step 2: Replace all 'O's with 'X's and 'A's back to 'O's
for i in range(rows):
for j in range(cols):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == 'A':
board[i][j] = 'O'
17.96MB, 128ms
C++
#include <vector>
using namespace std;
class Solution {
public:
void solve(vector<vector<char>>& board) {
if (board.empty() || board[0].empty()) return;
int rows = board.size();
int cols = board[0].size();
vector<vector<int>> directions{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// Helper function to perform DFS
function<void(int, int)> dfs = [&](int r, int c) {
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != 'O') return;
board[r][c] = 'A'; // Mark this 'O' as visited and connected to the border
for (auto& dir : directions) {
dfs(r + dir[0], c + dir[1]);
}
};
// Step 1: Mark the 'O's that are connected to the borders
for (int i = 0; i < rows; ++i) {
if (board[i][0] == 'O') dfs(i, 0);
if (board[i][cols - 1] == 'O') dfs(i, cols - 1);
}
for (int j = 0; j < cols; ++j) {
if (board[0][j] == 'O') dfs(0, j);
if (board[rows - 1][j] == 'O') dfs(rows - 1, j);
}
// Step 2: Replace all 'O's with 'X's and 'A's back to 'O's
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
} else if (board[i][j] == 'A') {
board[i][j] = 'O';
}
}
}
}
};
13.71MB, 7ms
Javascript
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solve = function(board) {
if (!board || board.length === 0) return;
const rows = board.length;
const cols = board[0].length;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const dfs = (r, c) => {
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== 'O') return;
board[r][c] = 'A'; // Mark this 'O' as visited and connected to the border
for (const [dr, dc] of directions) {
dfs(r + dr, c + dc);
}
};
// Step 1: Mark the 'O's that are connected to the borders
for (let i = 0; i < rows; ++i) {
if (board[i][0] === 'O') dfs(i, 0);
if (board[i][cols - 1] === 'O') dfs(i, cols - 1);
}
for (let j = 0; j < cols; ++j) {
if (board[0][j] === 'O') dfs(0, j);
if (board[rows - 1][j] === 'O') dfs(rows - 1, j);
}
// Step 2: Replace all 'O's with 'X's and 'A's back to 'O's
for (let i = 0; i < rows; ++i) {
for (let j = 0; j < cols; ++j) {
if (board[i][j] === 'O') {
board[i][j] = 'X';
} else if (board[i][j] === 'A') {
board[i][j] = 'O';
}
}
}
};
54.57MB, 74ms
