floodFill.ts

floodFill.ts

function floodFill(
    image: number[][],
    x: number,
    y: number,
    newColor: number,
): void {
    const minY = 0
    const maxY = image.length - 1

    if (maxY < 0) { return }

    const minX = 0
    const maxX = image[0].length - 1

    if (maxX < 0) { return }

    function isOut(x: number, y: number) {
        return (
            x < minX ||
            x > maxX ||
            y < minY ||
            y > maxY
        )
    }

    if (isOut(x, y)) { return }

    const targetColor = image[y][x]
    const tasks: Array<[number, number]> = []
    const checked = new Set<number>()

    function key(x: number, y: number): number {
        // non-negative cantor pairing
        return (.5 * (x + y) * (x + y + 1)) + y
    }

    function fill(x: number, y: number): boolean {
        checked.add(key(x, y))

        if (image[y][x] === targetColor) {
            image[y][x] = newColor
            return true
        } else {
            return false
        }
    }

    tasks.push([x, y])

    while (tasks.length) {
        const [x, y] = tasks.pop()!

        if (fill(x, y)) {
            if (!isOut(x + 1, y) && !checked.has(key(x + 1, y))) tasks.push([x + 1, y])
            if (!isOut(x - 1, y) && !checked.has(key(x - 1, y))) tasks.push([x - 1, y])
            if (!isOut(x, y + 1) && !checked.has(key(x, y + 1))) tasks.push([x, y + 1])
            if (!isOut(x, y - 1) && !checked.has(key(x, y - 1))) tasks.push([x, y - 1])
        }
    }
}

function printImage(image: number[][]) {
    for (let y = 0; y < image.length; ++y) {
        const row = image[y]
        let line = ''

        for (let x = 0; x < row.length; ++x) {
            const c = row[x]
            line += (c === 2 ? '  ' : c + ' ')
        }

        console.log(line)
    }
}

function compare(imageA: number[][], imageB: number[][]) {
    if (imageA.length !== imageB.length) { return false }
    if (imageA.length === 0) { return true }
    if (imageA[0].length !== imageB[0].length) { return false }
    if (imageA[0].length === 0) { return true }

    for (let y = 0; y < imageA.length; ++y) {
        const rowA = imageA[y]
        const rowB = imageB[y]

        for (let x = 0; x < rowA.length; ++x) {
            if (rowA[x] !== rowB[x]) { return false }
        }
    }

    return true
}

const image = [
    [0, 2, 0, 0, 0],
    [0, 2, 0, 2, 0],
    [2, 0, 0, 2, 0],
    [2, 0, 2, 0, 0],
    [0, 0, 2, 0, 2],
]

const correct = [
    [0, 2, 1, 1, 1],
    [0, 2, 1, 2, 1],
    [2, 1, 1, 2, 1],
    [2, 1, 2, 1, 1],
    [1, 1, 2, 1, 2],
]

console.log('before:')
printImage(image)

floodFill(image, 2, 2, 1)

console.log('after:')
printImage(image)

console.log('correct:')
printImage(correct)

console.log('equal:', compare(image, correct))