417. Pacific Atlantic Water Flow
Имеется прямоугольный остров размером m x n, который граничит с Тихим и Атлантическим океанами. Тихий океан касается левого и верхнего краев острова, а Атлантический океан - правого и нижнего краев. Остров разбит на сетку квадратных ячеек. Вам дана целочисленная матрица heights размером m x n, где heights[r][c] - высота над уровнем моря клетки с координатами (r, c). На острове выпадает много осадков, и дождевая вода может стекать в соседние клетки прямо на север, юг, восток и запад, если высота соседней клетки меньше или равна высоте текущей клетки. Вода может течь из любой клетки, прилегающей к океану, в океан. Верните двумерный список координат сетки result, где result[i] = [ri, ci] означает, что дождевая вода может течь из клетки (ri, ci) как в Тихий, так и в Атлантический океаны.
Пример:
Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
C# решение
сопоставлено/оригиналpublic class Solution {
public IList<IList<int>> PacificAtlantic(int[][] heights) {
int m = heights.Length;
int n = heights[0].Length;
bool[][] pacific = new bool[m][];
bool[][] atlantic = new bool[m][];
for (int i = 0; i < m; i++) {
pacific[i] = new bool[n];
atlantic[i] = new bool[n];
}
int[][] directions = new int[][] { new int[] {-1, 0}, new int[] {1, 0}, new int[] {0, -1}, new int[] {0, 1} };
for (int i = 0; i < m; i++) {
Dfs(i, 0, pacific, heights, directions);
Dfs(i, n - 1, atlantic, heights, directions);
}
for (int j = 0; j < n; j++) {
Dfs(0, j, pacific, heights, directions);
Dfs(m - 1, j, atlantic, heights, directions);
}
IList<IList<int>> result = new List<IList<int>>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j]) {
result.Add(new List<int> { i, j });
}
}
}
return result;
}
private void Dfs(int r, int c, bool[][] ocean, int[][] heights, int[][] directions) {
ocean[r][c] = true;
foreach (int[] dir in directions) {
int nr = r + dir[0];
int nc = c + dir[1];
if (nr >= 0 && nc >= 0 && nr < heights.Length && nc < heights[0].Length && !ocean[nr][nc] && heights[nr][nc] >= heights[r][c]) {
Dfs(nr, nc, ocean, heights, directions);
}
}
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public IList<vector<int>> PacificAtlantic(int[][] heights) {
int m = heights.size();
int n = heights[0].size();
bool[][] pacific = new bool[m][];
bool[][] atlantic = new bool[m][];
for (int i = 0; i < m; i++) {
pacific[i] = new bool[n];
atlantic[i] = new bool[n];
}
int[][] directions = new int[][] { new int[] {-1, 0}, new int[] {1, 0}, new int[] {0, -1}, new int[] {0, 1} };
for (int i = 0; i < m; i++) {
Dfs(i, 0, pacific, heights, directions);
Dfs(i, n - 1, atlantic, heights, directions);
}
for (int j = 0; j < n; j++) {
Dfs(0, j, pacific, heights, directions);
Dfs(m - 1, j, atlantic, heights, directions);
}
IList<vector<int>> result = new List<vector<int>>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j]) {
result.push_back(new List<int> { i, j });
}
}
}
return result;
}
private void Dfs(int r, int c, bool[][] ocean, int[][] heights, int[][] directions) {
ocean[r][c] = true;
foreach (vector<int>& dir in directions) {
int nr = r + dir[0];
int nc = c + dir[1];
if (nr >= 0 && nc >= 0 && nr < heights.size() && nc < heights[0].size() && !ocean[nr][nc] && heights[nr][nc] >= heights[r][c]) {
Dfs(nr, nc, ocean, heights, directions);
}
}
}
}Java решение
сопоставлено/оригиналimport java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<Integer>> pacificAtlantic(int[][] heights) {
int m = heights.length;
int n = heights[0].length;
boolean[][] pacific = new boolean[m][n];
boolean[][] atlantic = new boolean[m][n];
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int i = 0; i < m; i++) {
dfs(i, 0, pacific, heights, directions);
dfs(i, n - 1, atlantic, heights, directions);
}
for (int j = 0; j < n; j++) {
dfs(0, j, pacific, heights, directions);
dfs(m - 1, j, atlantic, heights, directions);
}
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j]) {
List<Integer> cell = new ArrayList<>();
cell.add(i);
cell.add(j);
result.add(cell);
}
}
}
return result;
}
private void dfs(int r, int c, boolean[][] ocean, int[][] heights, int[][] directions) {
ocean[r][c] = true;
for (int[] dir : directions) {
int nr = r + dir[0], nc = c + dir[1];
if (nr >= 0 && nc >= 0 && nr < heights.length && nc < heights[0].length && !ocean[nr][nc] && heights[nr][nc] >= heights[r][c]) {
dfs(nr, nc, ocean, heights, directions);
}
}
}
}JavaScript решение
сопоставлено/оригиналfunction pacificAtlantic(heights) {
const m = heights.length, n = heights[0].length;
const pacific = Array.from({ length: m }, () => Array(n).fill(false));
const atlantic = Array.from({ length: m }, () => Array(n).fill(false));
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
function dfs(r, c, ocean) {
ocean[r][c] = true;
for (const [dr, dc] of directions) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nc >= 0 && nr < m && nc < n && !ocean[nr][nc] && heights[nr][nc] >= heights[r][c]) {
dfs(nr, nc, ocean);
}
}
}
for (let i = 0; i < m; i++) {
dfs(i, 0, pacific);
dfs(i, n - 1, atlantic);
}
for (let j = 0; j < n; j++) {
dfs(0, j, pacific);
dfs(m - 1, j, atlantic);
}
const result = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j]) {
result.push([i, j]);
}
}
}
return result;
}Python решение
сопоставлено/оригиналdef pacificAtlantic(heights):
m, n = len(heights), len(heights[0])
pacific = [[False] * n for _ in range(m)]
atlantic = [[False] * n for _ in range(m)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def dfs(r, c, ocean):
ocean[r][c] = True
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and not ocean[nr][nc] and heights[nr][nc] >= heights[r][c]:
dfs(nr, nc, ocean)
for i in range(m):
dfs(i, 0, pacific)
dfs(i, n - 1, atlantic)
for j in range(n):
dfs(0, j, pacific)
dfs(m - 1, j, atlantic)
result = []
for i in range(m):
for j in range(n):
if pacific[i][j] and atlantic[i][j]:
result.append([i, j])
return resultGo решение
сопоставлено/оригиналpackage main
func pacificAtlantic(heights [][]int) [][]int {
m, n := len(heights), len(heights[0])
pacific := make([][]bool, m)
atlantic := make([][]bool, m)
for i := range pacific {
pacific[i] = make([]bool, n)
atlantic[i] = make([]bool, n)
}
directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
var dfs func(r, c int, ocean [][]bool)
dfs = func(r, c int, ocean [][]bool) {
ocean[r][c] = true
for _, dir := range directions {
nr, nc := r+dir[0], c+dir[1]
if nr >= 0 && nc >= 0 && nr < m && nc < n && !ocean[nr][nc] && heights[nr][nc] >= heights[r][c] {
dfs(nr, nc, ocean)
}
}
}
for i := 0; i < m; i++ {
dfs(i, 0, pacific)
dfs(i, n-1, atlantic)
}
for j := 0; j < n; j++ {
dfs(0, j, pacific)
dfs(m-1, j, atlantic)
}
result := [][]int{}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if pacific[i][j] && atlantic[i][j] {
result = append(result, []int{i, j})
}
}
}
return result
}Algorithm
Определите две матрицы для отслеживания клеток, из которых вода может течь в Тихий и Атлантический океаны, используя поиск в глубину (DFS) или поиск в ширину (BFS), начиная с границ, примыкающих к каждому океану.
Выполните поиск для каждого океана, обновляя матрицы достижимости.
Соберите координаты клеток, которые могут стекать в оба океана, проверяя пересечение двух матриц достижимости.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.