130. Surrounded Regions
Tags:
Medium
Skills:
Graph
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm tất cả các vùng ‘O’ bị bao quanh hoàn toàn bởi ‘X’ trên một ma trận 2D, sau đó đổi tất cả các ‘O’ trong vùng đó thành ‘X’. Tuy nhiên, các ‘O’ nằm trên biên hoặc kết nối với biên sẽ không bị đổi
Approach
Time and space complexity
Solution
1/**
2 Do not return anything, modify board in-place instead.
3 */
4function solve(board: string[][]): void {
5 if (board.length === 0) return;
6 const rows = board.length;
7 const cols = board[0].length;
8 const dirs = [
9 [1, 0], [0, 1], [0, -1], [-1, 0]
10 ]
11
12 function dfs(row: number, col: number): void {
13 if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] !== 'O') return;
14 board[row][col] = '#'
15 for (const [dx, dy] of dirs) {
16 const new_r = dx + row;
17 const new_c = dy + col;
18 dfs(new_r, new_c)
19 }
20 }
21
22 for (let i = 0; i < cols; i++) {
23 dfs(0, i);
24 dfs(rows - 1, i)
25 }
26
27 for (let i = 0; i < rows; i++) {
28 dfs(i, 0);
29 dfs(i, cols - 1)
30 }
31
32 for (let i = 0; i < rows; i++) {
33 for (let j = 0; j < cols; j++) {
34 if (board[i][j] === 'O') {
35 board[i][j] = 'X'
36 } else if (board[i][j] === '#') {
37 board[i][j] = 'O'
38 }
39 }
40 }
41};