Источник: https://leetcode.com/problems/pacific-atlantic-water-flow/
Остров представлен матрицейm x n граничит с Тихим и Атлантическим океанами: сверху и слева от острова Тихий океан, снизу и справа - Атдантический.
Остров поделен на ячейки, соответствующие ячейкам матрицы. Значение каждой ячейки - это высота над уровнем моря.
На остров проливается дождь. Дождь стекает по поверхности острова и вода впадает в океаны в 4 направлениях: вверх, вниз, вправо, влево. Вода может перетекать из первой ячейки во вторую, если значение первой ячейки больше или равно значения второй ячейки.
Вернуть список ячеек, заданных своими координатами, из которых вода стекает в оба океана.
На изображении выше виден пример, что остров задан матрицей: [[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]]. Желтым цветом отмечены ячейки, из которых вода стекает в оба океана: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Идея решения
Мы отдельно подсчитываем ячейки, из которых вода может стечь в один океан, потом ячейки, из которых вода может попасть во второй океан. Понятно, что пересечение этих ячеек даст искомый результат.
Как подсчитать ячейки, достигающие океана? Понятно, что ячейки, граничащие с океаном, входят в результат.
Для Тихого океана - это [[0, 0], [0,1], [0,2], [0,3], [0,4], [1,0], [2,0], [3,0], [4,0]].
Все эти ячейки мы ставим в очередь, и для каждой прверяем, чтобы соседнее справа и снизу было больше либо равно, чем рассматриваемая. Если это так, то тоже заносим в очередь. Продолжаем, пока не сможем найти новую ячейку для добавления в очередь.
Для Атлантического океана мы берем правую колонку и нижний ряд матрицы. И повторяем процедуру занесения в очередь, только проверяя соседей слева и сверху.
Пересечние ячеек и даст нам те, которые на картинке выделены желтым маркером.
Имплементация
class Solution {
private static final int[][] DIRECTIONS = new int[][]{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
private int numRows;
private int numCols;
private int[][] landHeights;
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
// Check if input is empty
if (matrix.length == 0 || matrix[0].length == 0) {
return new ArrayList<>();
}
numRows = matrix.length;
numCols = matrix[0].length;
landHeights = matrix;
// отдельно подсчитываем результат для одного океана и для другого
Queue<int[]> pacificQueue = new LinkedList<>();
Queue<int[]> atlanticQueue = new LinkedList<>();
// инициализация
for (int i = 0; i < numRows; i++) {
pacificQueue.offer(new int[]{i, 0});
atlanticQueue.offer(new int[]{i, numCols - 1});
}
for (int i = 0; i < numCols; i++) {
pacificQueue.offer(new int[]{0, i});
atlanticQueue.offer(new int[]{numRows - 1, i});
}
// Поиск в ширину
boolean[][] pacificReachable = bfs(pacificQueue);
boolean[][] atlanticReachable = bfs(atlanticQueue);
// Поиск пересечения
List<List<Integer>> commonCells = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < numCols; j++) {
if (pacificReachable[i][j] && atlanticReachable[i][j]) {
commonCells.add(List.of(i, j));
}
}
}
return commonCells;
}
// поиск в ширину
private boolean[][] bfs(Queue<int[]> queue) {
boolean[][] reachable = new boolean[numRows][numCols]; // результат поиска
while (!queue.isEmpty()) {
int[] cell = queue.poll();
// ячейке в очереди достижима, заносим ее в результат
reachable[cell[0]][cell[1]] = true;
for (int[] dir : DIRECTIONS) { //проверяем 4 направления
// считаем координаты соседней ячейки
int newRow = cell[0] + dir[0];
int newCol = cell[1] + dir[1];
// ячейка должна быть в пределах матрицы
if (newRow < 0 || newRow >= numRows || newCol < 0 || newCol >= numCols) {
continue;
}
// если мы уже занесли ячейку в очередь, то пропускаем ее
if (reachable[newRow][newCol]) {
continue;
}
// проверяем условие стекаемости. Новая чейка должна иметь значение
// больше либо равно. Если это не так, то пропускам
if (landHeights[newRow][newCol] < landHeights[cell[0]][cell[1]]) {
continue;
}
// Ячейка прошла все проверки, заносим ее в очередь
queue.offer(new int[]{newRow, newCol});
}
}
return reachable;
}
}
Комментарии
Отправить комментарий