Flood Fill

文思海輝 面試

by louis0420

HTML

https://jsfiddle.net/#

JavaScript

const image = [
  [1, 3, 1],
  [1, 1, 0],
  [1, 0, 1]
]
const sr = 1
const sc = 1
const newColor = 2



/**
 * @param {number[][]} image
 * @param {number} sr
 * @param {number} sc
 * @param {number} newColor
 * @return {number[][]}
 */
const floodFill = (image, sr, sc, newColor) => {
  // 取得 圖片長寬
  const x = image.length
  const y = image[0].length

  const originColor = image[sr][sc]

  // 檢查是否到了圖片邊界，
  const isValid = (screen, m, n, x, y, prevC, newC) => {
    if (x < 0 || x >= m || y < 0 || y >= n || screen[x][y] != prevC ||
      screen[x][y] == newC)
      return false;
    return true;
  }

  // 處理顏色的佇列
  let queue = []

  queue.push([sr, sc])

  // 輸入新顏色
  image[sr][sc] = newColor

  while (queue.length > 0) {
    let currPixel = queue[queue.length - 1];
    queue.pop();

    let posX = currPixel[0];
    let posY = currPixel[1];

    // 下
    if (isValid(image, x, y, posX + 1, posY, originColor, newColor)) {
      image[posX + 1][posY] = newColor;
      queue.push([posX + 1, posY]);
    }
    // 上
    if (isValid(image, x, y, posX - 1, posY, originColor, newColor)) {
      image[posX - 1][posY] = newColor;
      queue.push([posX - 1, posY]);
    }
    // 右
    if (isValid(image, x, y, posX, posY + 1, originColor, newColor)) {
      image[posX][posY + 1] = newColor;
      queue.push([posX, posY + 1]);
    }

    // 左
    if (isValid(image, x, y, posX, posY - 1, originColor, newColor)) {
      image[posX][posY - 1] = newColor
      queue.push([posX, posY - 1]);
    }
  }
  return image
};


const modifyImage = floodFill(image, sr, sc, newColor)

console.log(modifyImage)