当前位置： 面试刷题>> 太平洋和大西洋的水流 (经典算法题500道)
### 题目补充描述
**题目**：
太平洋和大西洋的水流问题
给定一个`m x n`的二维网格，每个单元格可以包含一个值0（表示陆地）或1（表示海洋）。海洋的单元格彼此相连（水平或垂直方向），并且最终可以流向两个大洋：太平洋和大西洋。假设网格的左上角为太平洋的出口，右下角为大西洋的出口。
编写一个函数来找出网格中所有可以通过水流路径到达太平洋和大西洋的海洋单元格。
**注意**：
- 水流只能沿着网格的水平或垂直方向流动。
- 如果一个海洋单元格可以同时到达太平洋和大西洋，它应该被计入两次结果中。
### 示例
**输入**:
```
[[1,0,1,0,0],
[1,1,0,1,0],
[1,0,0,0,0],
[1,1,1,0,0],
[0,0,0,1,1]]
```
**输出**:
```
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
```
**解释**:
- 索引(0, 0)的海洋单元格可以通过水流路径到达太平洋和大西洋。
- 索引(1, 3)和(1, 4)的海洋单元格可以通过水流路径到达两个大洋。
- 其他标记的海洋单元格只能到达一个大洋。
### PHP 示例代码
```php
function pacificAtlantic($matrix) {
if (empty($matrix) || empty($matrix[0])) {
return [];
}
$m = count($matrix);
$n = count($matrix[0]);
$result = [];
$pacific = array_fill(0, $m, array_fill(0, $n, false));
$atlantic = array_fill(0, $m, array_fill(0, $n, false));
// 初始化太平洋可达的边界
for ($i = 0; $i < $m; $i++) {
dfs($matrix, $pacific, $i, 0);
}
for ($j = 0; $j < $n; $j++) {
dfs($matrix, $pacific, 0, $j);
}
// 初始化大西洋可达的边界
for ($i = 0; $i < $m; $i++) {
dfs($matrix, $atlantic, $i, $n - 1);
}
for ($j = 0; $j < $n; $j++) {
dfs($matrix, $atlantic, $m - 1, $j);
}
// 找出同时可达的海洋单元格
for ($i = 0; $i < $m; $i++) {
for ($j = 0; $j < $n; $j++) {
if ($matrix[$i][$j] == 1 && $pacific[$i][$j] && $atlantic[$i][$j]) {
$result[] = [$i, $j];
}
}
}
return $result;
}
function dfs(&$matrix, &$visited, $row, $col) {
$m = count($matrix);
$n = count($matrix[0]);
if ($row < 0 || $row >= $m || $col < 0 || $col >= $n || $matrix[$row][$col] == 0 || $visited[$row][$col]) {
return;
}
$visited[$row][$col] = true;
dfs($matrix, $visited, $row + 1, $col);
dfs($matrix, $visited, $row - 1, $col);
dfs($matrix, $visited, $row, $col + 1);
dfs($matrix, $visited, $row, $col - 1);
}
```
### Python 示例代码
```python
def pacificAtlantic(matrix):
if not matrix or not matrix[0]:
return []
m, n = len(matrix), len(matrix[0])
pacific = [[False] * n for _ in range(m)]
atlantic = [[False] * n for _ in range(m)]
result = []
def dfs(visited, row, col):
if row < 0 or row >= m or col < 0 or col >= n or matrix[row][col] == 0 or visited[row][col]:
return
visited[row][col] = True
dfs(visited, row + 1, col)
dfs(visited, row - 1, col)
dfs(visited, row, col + 1)
dfs(visited, row, col - 1)
# 初始化太平洋可达的边界
for i in range(m):
dfs(pacific, i, 0)
for j in range(n):
dfs(pacific, 0, j)
# 初始化大西洋可达的边界
for i in range(m):
dfs(atlantic, i, n - 1)
for j in range(n):
dfs(atlantic, m - 1, j)
# 找出同时可达的海洋单元格
for i in range(m):
for j in range(n):
if matrix[i][j] == 1 and pacific[i][j] and atlantic[i][j]:
result.append([i, j])
return result
```
### JavaScript 示例代码
```javascript
function pacificAtlantic(matrix) {
if (!matrix || !matrix[0]) return [];
const m = matrix.length;
const n = matrix[0].length;
let pacific = Array.from({ length: m }, () => Array(n).fill(false));
let atlantic = Array.from({ length: m }, () => Array(n).fill(false));
let result = [];
function dfs(visited, row, col) {
if (row < 0 || row >= m || col < 0 || col >= n || matrix[row][col] === 0 || visited[row][col]) {
return;
}
visited[row][col] = true;
dfs(visited, row + 1, col);
dfs(visited, row - 1, col);
dfs(visited, row, col + 1);
dfs(visited, row, col - 1);
}
// 初始化太平洋可达的边界
for (let i = 0; i < m; i++) {
dfs(pacific, i, 0);
}
for (let j = 0; j < n; j++) {
dfs(pacific, 0, j);
}
// 初始化大西洋可达的边界
for (let i = 0; i < m; i++) {
dfs(atlantic, i, n - 1);
}
for (let j = 0; j < n; j++) {
dfs(atlantic, m - 1, j);
}
// 找出同时可达的海洋单元格
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 1 && pacific[i][j] && atlantic[i][j]) {
result.push([i, j]);
}
}
}
return result;
}
```
**码小课**网站中有更多关于算法和数据结构的内容分享给大家学习，包括但不限于动态规划、图论、搜索算法等，欢迎访问学习。