编程解决:
时间: 2023-07-31 13:12:34 浏览: 90
编程任务:解决锻炼的编程任务
好的,下面是使用深度优先搜索解决该问题的 Python 代码:
```python
n, m = map(int, input().split())
grid = []
for i in range(n):
row = list(map(int, input().split()))
grid.append(row)
visited = [[False] * m for _ in range(n)] # 标记每个格子是否已经被访问过
def dfs(x, y):
visited[x][y] = True
dx = [-1, 0, 1, 0] # 上下左右四个方向
dy = [0, 1, 0, -1]
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and grid[nx][ny] == 1:
dfs(nx, ny)
count = 0 # 记录连通块的数量
for i in range(n):
for j in range(m):
if not visited[i][j] and grid[i][j] == 1:
dfs(i, j)
count += 1
print(count)
```
输入样例:
```
5 5
0 0 1 0 1
0 1 1 0 0
0 0 0 1 1
1 1 0 0 0
0 0 0 0 1
```
输出样例:
```
4
```
在上面的样例中,有四个连通块,分别由 (0, 2), (0, 4), (1, 1), (1, 2) 和 (2, 3), (2, 4), (3, 0), (3, 1) 组成。
阅读全文