一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。
时间: 2024-01-11 12:48:18 浏览: 144
这道题可以使用深度优先搜索(DFS)来解决。具体步骤如下:
1. 遍历矩形阵列,找到数字为1到9的细胞,作为起点进行搜索。
2. 对于每个起点,进行深度优先搜索,将搜索到的细胞标记为已访问。
3. 在搜索过程中,对于每个细胞,判断它的上下左右是否也是细胞,如果是,则将其标记为已访问。
4. 搜索结束后,统计标记为已访问的细胞的数量,即为矩形阵列中的细胞个数。
以下是 Python 代码实现:
```python
def dfs(grid, i, j):
if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
return
grid[i][j] = '0'
dfs(grid, i+1, j)
dfs(grid, i-1, j)
dfs(grid, i, j+1)
dfs(grid, i, j-1)
def numIslands(grid):
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] != '0':
dfs(grid, i, j)
count += 1
return count
```
其中,`grid` 是一个二维数组,表示矩形阵列;`dfs` 函数是深度优先搜索函数,用于搜索当前细胞的上下左右是否也是细胞;`numIslands` 函数用于遍历矩形阵列,找到起点细胞进行搜索,并统计标记为已访问的细胞数量。
阅读全文