مراقبه های LeetCode: جریان آب اقیانوس اطلس آرام

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]]

Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0, 4]: [0, 4] -> Pacific Ocean 
        [0, 4] -> Atlantic Ocean
[1, 3]: [1, 3] -> [0, 3] -> Pacific Ocean 
        [1, 3] -> [1, 4] -> Atlantic Ocean
[1, 4]: [1, 4] -> [1, 3] -> [0, 3] -> Pacific Ocean 
        [1, 4] -> Atlantic Ocean
[2, 2]: [2, 2] -> [1, 2] -> [0, 2] -> Pacific Ocean 
        [2, 2] -> [2, 3] -> [2, 4] -> Atlantic Ocean
[3, 0]: [3, 0] -> Pacific Ocean 
        [3, 0] -> [4, 0] -> Atlantic Ocean
[3, 1]: [3, 1] -> [3, 0] -> Pacific Ocean 
        [3, 1] -> [4, 1] -> Atlantic Ocean
[4, 0]: [4 ,0] -> Pacific Ocean 
        [4, 0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.

const reachableToPacific: Set<string> = new Set();
const reachableToAtlantic: Set<string> = new Set();

for (const cell of reachableToPacific.values()) {
  if (reachableToAtlantic.has(cell)) {
    const [r, c] = cell.split(',');
    result.push([+r, +c]);
  }
}

for (let col = 0; col < colsLength; col++) {
  bfs(0, col, reachableToPacific);
  bfs(rowsLength - 1, col, reachableToAtlantic);
}

for (let row = 0; row < rowsLength; row++) {
  bfs(row, 0, reachableToPacific);
  bfs(row, colsLength - 1, reachableToAtlantic);
}

let queue = [[r, c, heights[r][c]]];

const [currentRow, currentCol, prevHeight] = queue.pop() as number[];

if (
  isOutOfBounds(currentRow, currentCol) || 
  reachableToOcean.has(`${currentRow},${currentCol}`) || 
  heights[currentRow][currentCol] < prevHeight
) {
  continue;
}

reachableToOcean.add(`${currentRow},${currentCol}`);

// up, down, left, right
const coords = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (const [rowToGo, colToGo] of coords) {
  queue.push([
    currentRow + rowToGo, 
    currentCol + colToGo, 
    heights[currentRow][currentCol]
  ]);
}

function bfs(r: number, c: number, reachableToOcean: Set<string>) {
  let queue = [[r, c, heights[r][c]]];

  while (queue.length > 0) {
    const [currentRow, currentCol, prevHeight] = queue.pop() as number[];

    if (
      isOutOfBounds(currentRow, currentCol) || 
      reachableToOcean.has(`${currentRow},${currentCol}`) || 
      heights[currentRow][currentCol] < prevHeight
    ) {
      continue;
    }

    reachableToOcean.add(`${currentRow},${currentCol}`);

    // up, down, left, right
    const coords = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    for (const [rowToGo, colToGo] of coords) {
      queue.push([
        currentRow + rowToGo, 
        currentCol + colToGo, 
        heights[currentRow][currentCol]
      ]);
    }
  }
}

function pacificAtlantic(heights: number[][]): number[][] {
  let result = [];
  const rowsLength = heights.length;
  const colsLength = heights[0].length;
  const reachableToPacific: Set<string> = new Set();
  const reachableToAtlantic: Set<string> = new Set();

  function isOutOfBounds(r: number, c: number) {
    return r < 0 || c < 0 || r >= rowsLength || c >= colsLength;
  }

  function bfs(r: number, c: number, reachableToOcean: Set<string>) {
    let queue = [[r, c, heights[r][c]]];

    while (queue.length > 0) {
      const [currentRow, currentCol, prevHeight] = queue.pop() as number[];

      if (
        isOutOfBounds(currentRow, currentCol) || 
        reachableToOcean.has(`${currentRow},${currentCol}`) || 
        heights[currentRow][currentCol] < prevHeight
      ) {
        continue;
      }

      reachableToOcean.add(`${currentRow},${currentCol}`);

      // up, down, left, right
      const coords = [[-1, 0], [1, 0], [0, -1], [0, 1]];
      for (const [rowToGo, colToGo] of coords) {
        queue.push([
            currentRow + rowToGo, 
            currentCol + colToGo, 
            heights[currentRow][currentCol]
        ]);
      }
    }
  }

  for (let col = 0; col < colsLength; col++) {
    bfs(0, col, reachableToPacific);
    bfs(rowsLength - 1, col, reachableToAtlantic);
  }

  for (let row = 0; row < rowsLength; row++) {
    bfs(row, 0, reachableToPacific);
    bfs(row, colsLength - 1, reachableToAtlantic);
  }

  for (const cell of reachableToPacific.values()) {
    if (reachableToAtlantic.has(cell)) {
      const [r, c] = cell.split(',');
      result.push([+r, +c]);
    }
  }

  return result;
}