如何在JS中从Flood Fill中返回新数组

Question

我想知道如何更改此算法以返回新的更新对象数组，而不是在全局映射数组中更改它。它使用JS实现Flood Fill算法。

这是我拥有的数组：

var map = [
    [0, 0, 0, 1, 1],
    [0, 0, 0, 1, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1]
];

这是我想要从调用floodFill函数中得到的结果：

result = [
    [0, 2, 2],
    [0, 2, 0],
    [2, 2, 0],
    [0, 2, 0]
];

这是整个源代码(只需将原始数组中连接的数组改为二)：

var map = [
    [0, 0, 0, 1, 1],
    [0, 0, 0, 1, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1]
];

function floodFill(data, x, y, newValue) {
    // get target value
    var target = data[x][y];

    function flow(x,y) {
        // bounds check what we were passed
        if (x >= 0 && x < data.length && y >= 0 && y < data[x].length) {
            if (data[x][y] === target) {
                data[x][y] = newValue;
                flow(x-1, y);
                flow(x+1, y);
                flow(x, y-1);
                flow(x, y+1);
            }
        }
    }

    flow(x,y);
}

var result = floodFill(map, 1, 3, 2);
/*
result = [
    [0, 2, 2],
    [0, 2, 0],
    [2, 2, 0],
    [0, 2, 0]
]
*/

Answer 1

您需要首先克隆2d数组。您可以对data执行所谓的深度克隆，将其复制到一个名为newData的新2d数组中。然后你就可以改变这个拷贝。

function floodFill(data, x0, y0, newValue) {
    var minX = x0, maxX = x0;
    var minY = y0, maxY = y0;

    // perform a deep clone, copying data to newData
    var newData = [];
    for (var i = 0; i < data.length; i++)
        newData[i] = data[i].slice();

    // from now on we make modifications to newData, not data
    var target = newData[x0][y0];
    function flow(x,y) {
        if (x >= 0 && x < newData.length && y >= 0 && y < newData[x].length) {
            if (newData[x][y] === target) {
                minX = Math.min(x, minX);
                maxX = Math.max(x, maxX);
                minY = Math.min(y, minY);
                maxY = Math.max(y, maxY);

                newData[x][y] = newValue;
                flow(x-1, y);
                flow(x+1, y);
                flow(x, y-1);
                flow(x, y+1);
            }
        }
    }
    flow(x0,y0);

    // shrink array (cut out a square)
    var result = [];
    for (var i = minX; i < maxX + 1; i++)
        result[i] = newData[i].slice(minY, maxY + 1);
    return result;
}

为了去掉结果周围的零，您需要跟踪泛洪填充设法达到的最小和最大x和y值，然后从结果中切出一个正方形的minX..maxX x minY..maxY。

Answer 2

下面是一个基于堆栈的、迭代的、错位的泛洪填充算法，该算法在使用newValue应用泛洪填充后，将复制的感兴趣区作为二维子数组返回

​

function floodFill (data, x, y, newValue) {
  const target = data[y][x]
  const stack = []
  const fill = []
  const directions = {
    0: { x: -1, y:  0 },
    1: { x:  1, y:  0 },
    2: { x:  0, y: -1 },
    3: { x:  0, y:  1 }
  }
  const { X = 0, Y = 1, DIR = 2 } = {}
  let [minX, maxX, minY, maxY] = [x, x, y, y]
  
  function isChecked (x, y) {
    const hash = `${x},${y}`
    const checked = isChecked[hash]
    
    isChecked[hash] = true
    
    return checked
  }
  
  // validates spot as target
  function isValid (x, y) {
    return (
      x >= 0 && x < data[0].length &&
      y >= 0 && y < data.length &&
      data[y][x] === target &&
      !isChecked(x, y)
    )
  }

  // start with x, y  
  stack.push([x, y, [0, 1, 2, 3]])

  // continue flood fill while stack is not empty
  while (stack.length > 0) {
    let top = stack.pop()

    // if there are directions left to traverse
    if (top[DIR].length > 0) {
      // get next direction
      let dir = top[DIR].pop()
      let delta = directions[dir]
      // remember this spot before traversing
      stack.push(top)
      // calculate next spot
      top = [top[X] + delta.x, top[Y] + delta.y, [0, 1, 2, 3]]

      // if next spot doesn't match target value, skip it
      if (!isValid(...top)) continue

      // traverse to next spot
      stack.push(top)
    } else {
      // we're done with this spot
      // expand area of interest
      minX = Math.min(minX, top[X])
      maxX = Math.max(maxX, top[X])
      minY = Math.min(minY, top[Y])
      maxY = Math.max(maxY, top[Y])

      // and remember it for filling the copied sub-array later
      fill.push([top[X], top[Y]])
    }
  }

  // now that flood fill is done, get result sub-array and fill it
  const result = []

  // generate result sub-array by copying data
  for (let i = minY; i <= maxY; i++) {
    result.push(data[i].slice(minX, maxX + 1))
  }
  // fill each remembered spot with newValue
  for (let i = 0; i < fill.length; i++) {
    let [gx, gy] = fill[i]
    let [rx, ry] = [gx - minX, gy - minY]

    result[ry][rx] = newValue
  }

  return result
}

const map = [
  [0, 1, 1, 1, 1],
  [0, 1, 0, 1, 0],
  [0, 1, 1, 1, 0],
  [0, 0, 0, 1, 0],
  [0, 0, 0, 0, 0],
  [0, 1, 1, 1, 1]
]

let result = floodFill(map, 3, 1, 2)

console.log(stringify(map))
console.log(stringify(result))

// for console.log(), ignore this
function stringify(data) {
  return data.map(row => row.join(', ')).join('\n')
}

​

必须使用isChecked()的原因是为了避免无限迭代，以确保任何单个斑点不会多次成为有效的候选对象。