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