surrounded_regions
1# @leet start 2class Solution: 3 def solve(self, board: list[list[str]]) -> None: 4 """ 5 This problem says to capture any O's that are surrounded by X's and 6 turn them into X's. O's cannot be captured if they are 7 To do so, we DFS from the edges (where y == 0 or x == 0 or y == m - 1 or 8 n == n - 1). 9 10 For all the O's we find, we turn them into some other character, like '1' 11 in this case so we know that they're uncapturable. 12 Then at the end, we traverse the board one more time, turning the remaining 13 O's to X's (since they're capturable), and then turning the 1's to O's 14 (since they're uncapturable). 15 """ 16 m, n = len(board), len(board[0]) 17 visited = set() 18 19 def inbounds(y, x): 20 return 0 <= y < m and 0 <= x < n 21 22 def dfs(y, x): 23 if not inbounds(y, x) or (y, x) in visited or board[y][x] != "O": 24 return 25 visited.add((y, x)) 26 board[y][x] = "1" 27 dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)] 28 for dy, dx in dirs: 29 new_y, new_x = dy + y, dx + x 30 dfs(new_y, new_x) 31 32 for y in range(m): 33 for x in range(n): 34 if y == 0 or y == m - 1 or x == 0 or x == n - 1: 35 dfs(y, x) 36 37 for y in range(m): 38 for x in range(n): 39 if board[y][x] == "1": 40 board[y][x] = "O" 41 elif board[y][x] == "O": 42 board[y][x] = "X" 43 44 45# @leet end 46 47 48def test(): 49 assert 2 + 2 == 4
class
Solution:
3class Solution: 4 def solve(self, board: list[list[str]]) -> None: 5 """ 6 This problem says to capture any O's that are surrounded by X's and 7 turn them into X's. O's cannot be captured if they are 8 To do so, we DFS from the edges (where y == 0 or x == 0 or y == m - 1 or 9 n == n - 1). 10 11 For all the O's we find, we turn them into some other character, like '1' 12 in this case so we know that they're uncapturable. 13 Then at the end, we traverse the board one more time, turning the remaining 14 O's to X's (since they're capturable), and then turning the 1's to O's 15 (since they're uncapturable). 16 """ 17 m, n = len(board), len(board[0]) 18 visited = set() 19 20 def inbounds(y, x): 21 return 0 <= y < m and 0 <= x < n 22 23 def dfs(y, x): 24 if not inbounds(y, x) or (y, x) in visited or board[y][x] != "O": 25 return 26 visited.add((y, x)) 27 board[y][x] = "1" 28 dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)] 29 for dy, dx in dirs: 30 new_y, new_x = dy + y, dx + x 31 dfs(new_y, new_x) 32 33 for y in range(m): 34 for x in range(n): 35 if y == 0 or y == m - 1 or x == 0 or x == n - 1: 36 dfs(y, x) 37 38 for y in range(m): 39 for x in range(n): 40 if board[y][x] == "1": 41 board[y][x] = "O" 42 elif board[y][x] == "O": 43 board[y][x] = "X"
def
solve(self, board: list[list[str]]) -> None:
4 def solve(self, board: list[list[str]]) -> None: 5 """ 6 This problem says to capture any O's that are surrounded by X's and 7 turn them into X's. O's cannot be captured if they are 8 To do so, we DFS from the edges (where y == 0 or x == 0 or y == m - 1 or 9 n == n - 1). 10 11 For all the O's we find, we turn them into some other character, like '1' 12 in this case so we know that they're uncapturable. 13 Then at the end, we traverse the board one more time, turning the remaining 14 O's to X's (since they're capturable), and then turning the 1's to O's 15 (since they're uncapturable). 16 """ 17 m, n = len(board), len(board[0]) 18 visited = set() 19 20 def inbounds(y, x): 21 return 0 <= y < m and 0 <= x < n 22 23 def dfs(y, x): 24 if not inbounds(y, x) or (y, x) in visited or board[y][x] != "O": 25 return 26 visited.add((y, x)) 27 board[y][x] = "1" 28 dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)] 29 for dy, dx in dirs: 30 new_y, new_x = dy + y, dx + x 31 dfs(new_y, new_x) 32 33 for y in range(m): 34 for x in range(n): 35 if y == 0 or y == m - 1 or x == 0 or x == n - 1: 36 dfs(y, x) 37 38 for y in range(m): 39 for x in range(n): 40 if board[y][x] == "1": 41 board[y][x] = "O" 42 elif board[y][x] == "O": 43 board[y][x] = "X"
This problem says to capture any O's that are surrounded by X's and turn them into X's. O's cannot be captured if they are To do so, we DFS from the edges (where y == 0 or x == 0 or y == m - 1 or n == n - 1).
For all the O's we find, we turn them into some other character, like '1' in this case so we know that they're uncapturable. Then at the end, we traverse the board one more time, turning the remaining O's to X's (since they're capturable), and then turning the 1's to O's (since they're uncapturable).
def
test():