用python解决环绕的区域问题要求用深度优先算法和广度优先算法
时间: 2024-01-05 13:02:09 浏览: 14
环绕的区域问题是指给定一个由 'X' 和 'O' 组成的二维矩阵, 'X' 表示障碍物, 'O' 表示空地,要求将被 'X' 包围的 'O' 变成 'X'。例如,给定矩阵如下:
```
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 X X X
```
下面是深度优先算法和广度优先算法的Python实现:
深度优先算法:
```python
def dfs(board, i, j):
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != 'O':
return
board[i][j] = '#'
dfs(board, i-1, j)
dfs(board, i+1, j)
dfs(board, i, j-1)
dfs(board, i, j+1)
def solve(board):
if not board or not board[0]:
return
rows, cols = len(board), len(board[0])
for i in range(rows):
dfs(board, i, 0)
dfs(board, i, cols-1)
for j in range(cols):
dfs(board, 0, j)
dfs(board, rows-1, j)
for i in range(rows):
for j in range(cols):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == '#':
board[i][j] = 'O'
```
广度优先算法:
```python
from collections import deque
def bfs(board, i, j):
queue = deque([(i, j)])
while queue:
i, j = queue.popleft()
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != 'O':
continue
board[i][j] = '#'
queue.append((i-1, j))
queue.append((i+1, j))
queue.append((i, j-1))
queue.append((i, j+1))
def solve(board):
if not board or not board[0]:
return
rows, cols = len(board), len(board[0])
for i in range(rows):
bfs(board, i, 0)
bfs(board, i, cols-1)
for j in range(cols):
bfs(board, 0, j)
bfs(board, rows-1, j)
for i in range(rows):
for j in range(cols):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == '#':
board[i][j] = 'O'
```
这两种算法都是对每个被 'X' 包围的连通块进行处理,时间复杂度为 $O(mn)$,空间复杂度为 $O(mn)$,其中 $m$ 和 $n$ 分别是矩阵的行数和列数。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)