floodFillAlgorithm
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148
/*
Graphics programs commonly use the flood fill algorithm to fill an arbitrarily
shaped area of the same color with another color. For example, the flood begins
on a white pixel and spreads until it meets a non-white pixel, filling the enclosed
space.
Instead of an image, you’re given 2D grid m x n of text characters to represent
an “image”. Each string represents a “pixel,” and the specific character
represents the “color”. A "." represents a white pixel and a "@" represents
the edge of the shape. Given a start coordinate (x, y) and a replacement
character, implement a function `floodFill` that replaces all white
pixels with the replacement character.
For example, for given `image`:
..............
.....@@@@.....
....@@..@@....
...@@....@@...
....@@..@@....
.....@@@@.....
..............
Example 1:
- start coordinate (0, 0)
- replacement character "+"
Output:
++++++++++++++
+++++@@@@+++++
++++@@..@@++++
+++@@....@@+++
++++@@..@@++++
+++++@@@@+++++
++++++++++++++
Example 2:
- start coordinate (6, 3)
- replacement character "+"
Output:
..............
.....@@@@.....
....@@++@@....
...@@++++@@...
....@@++@@....
.....@@@@.....
..............
Constraint:
- image.length == m
- image[i].length == n
- image[i][j] is a "." or "@'.
*/
function floodFill(image, x, y, newChar, oldChar) {
const HEIGHT = image.length;
const WIDTH = image[0].length;
function floodFillRec(image, x, y) {
// if (oldChar == newChar) return;
if (image[y][x] != oldChar) return;
// Change the character.
image[y][x] = newChar;
// Check if neighbor right can be filled.
if ((x + 1 < WIDTH) && (image[y][x + 1] == oldChar)) {
floodFillRec(image, x + 1, y);
}
// Check if neighbor left can be filled.
if ((x - 1 >= 0) && (image[y][x - 1] == oldChar)) {
floodFillRec(image, x - 1, y);
}
// Check if neighbor down can be filled.
if ((y + 1 < HEIGHT) && (image[y + 1][x] == oldChar)) {
floodFillRec(image, x, y + 1);
}
// Check if neighbor up can be filled.
if ((y - 1 >= 0) && (image[y - 1][x] == oldChar)) {
floodFillRec(image, x, y - 1);
}
}
floodFillRec(image, x, y);
}
function printImage(image) {
const HEIGHT = image.length;
for (let y = 0; y < HEIGHT; y++) {
console.log(image[y].join(""));
}
console.log("\n");
}
const image = [
"............................................".split(""),
"............................................".split(""),
"................@@@@@@@@@@@@@...............".split(""),
"...............@@@.........@@@@.............".split(""),
".............@@@.............@@@@...........".split(""),
".............@@......@@@@@@@@@@@@@..........".split(""),
"............@@@......@@..........@@@........".split(""),
"........@@@@@@@.....@@............@@........".split(""),
".......@@@..........@@............@@........".split(""),
".......@@@...@......@@..........@@@@........".split(""),
".......@@....@........@@@@@@@@@@@@@@........".split(""),
".......@@....@..................@@@.........".split(""),
".......@@....@...................@@.........".split(""),
".......@@....@..................@@@.........".split(""),
".......@@@...@..................@@@.........".split(""),
".......@@@@..@..................@@@.........".split(""),
"........@@@@@@@......@@@@@@@... @@@.........".split(""),
"..........@@@@@......@...@@.... @@@.........".split(""),
"............@@@......@...@@.....@@@.........".split(""),
"............@@@@....@@...@@@@@@@@@.........".split(""),
"..............@@@@@@@@......................".split(""),
"............................................".split(""),
"............................................".split(""),
];
const image2 = [
"..............".split(""),
".....@@@@.....".split(""),
"....@@..@@....".split(""),
"...@@....@@...".split(""),
"....@@..@@....".split(""),
".....@@@@.....".split(""),
"..............".split(""),
];
const insideImage2 = JSON.parse(JSON.stringify(image2));
printImage(insideImage2);
floodFill(insideImage2, 6, 3, "+", ".");
printImage(insideImage2);
const outsideImage2 = JSON.parse(JSON.stringify(image2));
printImage(outsideImage2);
floodFill(outsideImage2, 0, 0, "+", ".");
printImage(outsideImage2);
JavaScript
INFO