A Little Fun with FloodFills

#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;

}