/* mines.c
 * Text-based game of Minesweeper
 * Input and output can be piped between another process that, for example, provides a graphical interface.
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define WIDTH		30
#define HEIGHT		20
#define NUM_MINES	50
#define STACK_SIZE	WIDTH*HEIGHT
#define PRINTLOCATION()	printf("%s line %d\n", __FILE__, __LINE__)

typedef enum { false, true } bool_t;

typedef struct {
	unsigned char num_surr_mines;
	bool_t is_mine		: 1;
	bool_t is_covered	: 1;
} cell_t;

typedef struct {
	int r, c;
} coord_t;

cell_t *board[HEIGHT];
coord_t cell_stack[STACK_SIZE];
int stack_index, max_stack_index;
int width, height;
int num_mines;

void fill_board(int num_mines) {
	int mine;
	int r, c;
	for (r = 0; r < height; ++r)
		for (c = 0; c < width; ++c) {
			board[r][c].is_mine = false;
			board[r][c].is_covered = true;
			board[r][c].num_surr_mines = 0;
		}
	
	for (mine = 0; mine < num_mines; ++mine) {
		int r1, c1;
		do {
			r = rand() % height;
			c = rand() % width;
		} while (board[r][c].is_mine);
		
		board[r][c].is_mine = true;
		
		for (r1 = r - 1; r1 <= r + 1; ++r1) {
			for (c1 = c - 1; c1 <= c + 1; ++c1) {
				if (r1 == r && c1 == c)
					continue;
				if (r1 < 0 || c1 < 0 || r1 >= height || c1 >= width)
					continue;
				
				++board[r1][c1].num_surr_mines;
			}
		}
	}
}

void show_board() {
	int r, c;
	for (r = 0; r < height; ++r) {
		for (c = 0; c < width; ++c) {
			if (board[r][c].is_covered) {
				putchar('#');
			} else if (board[r][c].is_mine) {
				putchar('*');
			} else if (board[r][c].num_surr_mines > 0)
				printf("%d", board[r][c].num_surr_mines);
			else
				putchar('.');
			putchar(' ');
		}
		fflush(stdout);
		putc('\t', stderr);
		for (c = 0; c < width; ++c) {
			if (board[r][c].is_mine) {
				putc('*', stderr);
			} else if (board[r][c].num_surr_mines > 0)
				putc(board[r][c].num_surr_mines + '0', stderr);
			else
				putc('.', stderr);
			putc(' ', stderr);
		}
		putchar('\n');
	}
}

int push(coord_t *cell) {
	++stack_index;
	if (stack_index == STACK_SIZE)
		return -1;
	
	if (stack_index > max_stack_index)
		max_stack_index = stack_index;
	
	/*printf("push(%d, %d)\t%d\n", cell->r, cell->c, stack_index);*/
	cell_stack[stack_index].r = cell->r;
	cell_stack[stack_index].c = cell->c;
	return 0;
}

int pop(coord_t *cell) {
	if (stack_index < 0)
		return 0;
	
	cell->r = cell_stack[stack_index].r; 
	cell->c = cell_stack[stack_index].c;
	/*printf("pop(%d, %d)\n", cell->r, cell->c);*/
	--stack_index;
	return 1;
}

/* uncover recurses through the board to uncover cells */
void uncover(int r, int c) {
	coord_t cell;
	
	if (board[r][c].is_covered)
		board[r][c].is_covered = false;
	else
		return;
	
	max_stack_index = 0;
	stack_index = -1;
	cell.r = r; cell.c = c;
	push(&cell);
	
	while (pop(&cell)) {
		int r1, c1;
		r = cell.r; c = cell.c;
		/*if (board[r][c].is_covered)
			board[r][c].is_covered = false;
		else
			continue;*/
		
		if (board[r][c].num_surr_mines > 0)
			continue;
			
		for (r1 = r - 1; r1 <= r + 1; ++r1)
			for (c1 = c - 1; c1 <= c + 1; ++c1) {
				if (r1 < 0 || c1 < 0 || r1 >= height || c1 >= width)
					continue;
				
				if (r1 == r && c1 == c)
					continue;
					
				if (board[r1][c1].is_covered)
					board[r1][c1].is_covered = false;
				else
					continue;
		
				cell.r = r1; cell.c = c1;
				if (push(&cell)) {
					fputs("Stack overflow.",stderr);
					exit(-1);
				}
			}
	}
	/*printf("max stack index = %d\n", max_stack_index);*/
	show_board();
	return;
}

int main () {
	int r, c;
	
	srand((unsigned int) time(NULL));
	
	width = WIDTH; height = HEIGHT;
	num_mines = NUM_MINES;
	
	for (r = 0; r < height; ++r)
		if ((board[r] = (cell_t *) malloc(width * sizeof(cell_t))) == NULL) {
			fprintf(stderr, "Could not allocate board\n");
			exit(-1);
		}
	
	fill_board(NUM_MINES);
	
	show_board();
	
	for (;;) {
		for (;;) {
			scanf("%d%d", &r, &c);
			if (r == -1 || c == -1)
				return 0;
			if (r < 0 || c < 0 || r >= height || c >= width)
				puts("Cell out of range.");
			else
				break;
		}
		
		if (board[r][c].is_mine) {
			int r, c;
			for (r = 0; r < height; ++r)
				for (c = 0; c < width; ++c)
					if (board[r][c].is_mine)
						board[r][c].is_covered = false;
			show_board();
			puts("You lose");
			break;
		}	
		
		uncover(r, c);
		
		{
			int r, c;
			int num_covered_cells = 0;
			for (r = 0; r < height; ++r)
				for (c = 0; c < width; ++c)
					if (board[r][c].is_covered)
						++num_covered_cells;
			if (num_covered_cells == num_mines) {
				puts("You win");
				break;
			}
		}
	}
	return 0;
}