如何使泛洪填充功能递归填充ASCII图像

Question

我需要使用floodFill函数将ASCII图像的星号轮廓内的所有点变成星号。有人可以帮忙吗？

"use strict";

let bitmap = [
  "................**********........................",
  "...............*..........*.......................",
  "..........*****............*........*.............",
  ".........*.................*.......*.*....*****...",
  "........*................***......*...*.**.....**.",
  "....****.................*.......*.....*.........*",
  "..**......................*******................*",
  ".*...............................................*",
  ".*...............................................*",
  "*...........****.............................****.",
  "*..........*....*.........................***.....",
  ".*.........*....*.......................**........",
  "..***.......****.......................*..........",
  ".....****......................******..*..........",
  ".........**********************.....****.........."
];



const bitmap2string = bitmap => bitmap.join("\n");

console.log(bitmap2string(bitmap));

const showOnPosition = (x, y) => 
  bitmap[y].charAt(x);

const changeSymbol = (x, y, symbol) => 
  bitmap[y].substr(0, x) + symbol + bitmap[y].substr(x + 1);

const floodFill = (x, y) => 
  showOnPosition(x, y) !== "*" 
    ? bitmap.map((line, i) => (i === y ? changeSymbol(x, y, "*") : line)) 
    : bitmap;

我写了代码：

• showOnPosition - 检查当前在数组的x，y坐标上的内容
• 更改符号 - 更改任何给定位置上的符号
• floodFill - 检查当前位置上的内容，如果不是星号，则将其更改为星号，并在控制台中提供更新的阵列。

现在我不知道如何使所有这些递归地通过图像（向右）并用星号填充给定的轮廓。

结果应该是：使用floodFill函数调用任何坐标，例如console.log（floodFill（8,7））it shows the following in the console

Answer 1

这是一个懒惰但简单的实现：

let bitmap = [
    "................**********........................",
    "...............*..........*.......................",
    "..........*****............*........*.............",
    ".........*.................*.......*.*....*****...",
    "........*................***......*...*.**.....**.",
    "....****.................*.......*.....*.........*",
    "..**......................*******................*",
    ".*...............................................*",
    ".*...............................................*",
    "*...........****.............................****.",
    "*..........*....*.........................***.....",
    ".*.........*....*.......................**........",
    "..***.......****.......................*..........",
    ".....****......................******..*..........",
    ".........**********************.....****.........."
];

// convert to an array of arrays
bitmap = bitmap.map(row => [...row]);
xsize = bitmap[0].length;
ysize = bitmap.length;

floodFill = (x, y) => {

    // check bounds
    if (y < 0 || y >= ysize) return;
    if (x < 0 || x >= xsize) return;

    // already painted?
    if (bitmap[y][x] === '*') return;

    // paint!
    bitmap[y][x] = '*';

    // fill neighbours
    floodFill(x - 1, y);
    floodFill(x + 1, y);
    floodFill(x, y - 1);
    floodFill(x, y + 1);
};

floodFill(7, 8);

// convert to string
bitmap = bitmap.map(row => row.join('')).join('\n');

document.write('<pre>' + bitmap);

这个解决方案的问题在于起点是任意的，可能超出界限。更好的方法是逐行扫描矩阵并进行一种“射线追踪”以确定一个点是在内部还是外部。这将在线性时间内无递归地运行。