#include <stdio.h>
#include <time.h>
#define PIC_X_SIZE 80U
#define PIC_Y_SIZE 25U
const char EMPTY = '.';
const char WALL = '#';
const char FILLED = '/';
// Size is Y by (X + 1) because data is stored in strings, so we need room for the \0 .
char pic[PIC_Y_SIZE][PIC_X_SIZE+1] = {
"################################################################################",
"#...........................................###########.............#...#...#..#",
"#.###.#.#.#.############.#..............###################......#..#.#.#.#.#..#",
"#.#.#.#.#.#.#########..#.#..............###################......#..#.#...#.#..#",
"#.....#.#.#.#..######..#.#..............###################......#..#.#...###..#",
"#.#.#...#.#.#..........#.#......................###########......#..###...###..#",
"#.#.#...#...#..######....#......................###########......#...##...##...#",
"#.#.#.#.#.#.#########.####..........................######.......#..###...###..#",
"#.###################....#...........................####........#..###...#....#",
"#.######...........##....#............................##.........#...##...#....#",
"#.#.###..#.........##....#............................#..........#..###...#....#",
"#.#...#..#.........##....#.......................................#..###..##....#",
"#.###.#..#.........##..###.########..............................#...##..##....#",
"#.....#..#.........##...##.#########.............................#.......##....#",
"#.##..#..#.........##..###......###..............................#.............#",
"#.##.....#.........##...#######.####..#######################################..#",
"#.########.##########..########.###...###############...##################..#..#",
"#.#######..##########...####....####..##....................................#..#",
"#..........##########..########...#...##..###################################..#",
"#..##################...############..##....................................#..#",
"#..#.################.................####################################..#..#",
"#..#..................................##....................................#..#",
"#..#.################.#..##..##..##...##################..###################..#",
"#..#................###..##..##..##...##################.......................#",
"################################################################################"
};
/*
char pic[PIC_Y_SIZE][PIC_X_SIZE+1] = {
"################################################################################",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"#..............................................................................#",
"################################################################################"
};
*/
int rDepth, calls;
clock_t tStart, tEnd;
// Recursive, pixel-step
// Assumes the picture array has a WALL frame, and that the outside-call x and y are inside the frame
void floodFill_R_Pixel(const int x, const int y, const int depth) {
if (depth > rDepth) {
rDepth = depth;
}
calls++;
if (EMPTY == pic[y][x]) {
pic[y][x] = FILLED;
floodFill_R_Pixel(x - 1, y , depth + 1);
floodFill_R_Pixel(x , y - 1, depth + 1);
floodFill_R_Pixel(x + 1, y , depth + 1);
floodFill_R_Pixel(x , y + 1, depth + 1);
}
}
// Recursive, horizontal line based
// Assumes the picture array has a WALL frame, and that the outside-call x and y are inside the frame
void floodFill_R_Line(const int x, const int y, const int depth) {
int x1 = x, x2 = x + 1;
if (depth > rDepth) {
rDepth = depth;
}
calls++;
if (EMPTY != pic[y][x]) return;
while (EMPTY == pic[y][x1]) {
pic[y][x1--] = FILLED;
}
while (EMPTY == pic[y][x2]) {
pic[y][x2++] = FILLED;
}
for (++x1 ; x1 < x2; x1++) {
floodFill_R_Line(x1, y - 1, depth + 1);
floodFill_R_Line(x1, y + 1, depth + 1);
}
}
// Non-recursive, pixel-step
// Assumes the picture array has a WALL frame, and that the outside-call x and y are inside the frame
void floodFill_Pixel(const int x, const int y) {
int changes, xx, yy;
pic[y][x] = FILLED;
do {
calls++;
changes = 0;
for (xx = 1; xx < PIC_X_SIZE - 1; xx++) {
for (yy = 1; yy < PIC_Y_SIZE - 1; yy++) {
if ((pic[yy][xx] == EMPTY) && (
(pic[yy][xx - 1] == FILLED) ||
(pic[yy - 1][xx] == FILLED) ||
(pic[yy][xx + 1] == FILLED) ||
(pic[yy + 1][xx] == FILLED)
)
) {
pic[yy][xx] = FILLED;
changes++;
}
}
}
} while (changes);
}
// Up and down, fill left to right
// Assumes the picture array has a WALL frame, and that the outside-call x and y are inside the frame
// Also that x, y is EMPTY!
void localFill(const int x, int y) {
int xx;
while (EMPTY == pic[y-1][x]) y--;
while (EMPTY == pic[y][x]) {
for (xx = x ; EMPTY == pic[y][xx] ; xx--) {
pic[y][xx] = FILLED;
}
for (xx = x + 1 ; EMPTY == pic[y][xx] ; xx++) {
pic[y][xx] = FILLED;
}
y++;
}
}
void floodFill_Smart(const int x, const int y) {
int changes, xx, yy;
localFill(x, y);
do {
calls++;
changes = 0;
for (xx = 1; xx < PIC_X_SIZE - 1; xx++) {
for (yy = 1; yy < PIC_Y_SIZE - 1; yy++) {
if ((pic[yy][xx] == EMPTY) && (
(pic[yy - 1][xx] == FILLED) ||
(pic[yy + 1][xx] == FILLED)
)
) {
localFill(xx, yy);
changes++;
}
}
}
} while (changes);
}
void drawPic(void) {
int y;
for (y = 0; y < PIC_Y_SIZE; y++) {
printf("%s\n", pic[y]);
}
printf("\n");
}
void clearPic(void) {
int x, y;
for (x = 1; x < PIC_X_SIZE - 1; x++) {
for (y = 1; y < PIC_Y_SIZE - 1; y++) {
pic[y][x] = EMPTY;
}
}
}
int main(void) {
drawPic();
rDepth = 0;
calls = 0;
tStart = clock();
//floodFill_R_Pixel(40, 12, 1);
//floodFill_R_Line(40, 12, 1);
//floodFill_Pixel(40, 12);
floodFill_Smart(40, 12);
tEnd = clock();
drawPic();
printf("%d function calls, maximal recursion depth was %d\n", calls, rDepth);
return 0;
}
Comments