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

#define SHOW_CLOSE -1 
#define SHOW_MINE 10
#define MINES_EMPTY 0
#define MINES_MINE 1
#define PLAYER_USER 1
#define PLAYER_COMPUTER 2
#define PMINE_RANDOM 1
#define PMINE_CUSTOM 2
#define BUTTON_LEFT 1
#define BUTTON_RIGHT 2
#define COMP_UNKNOW -1

int **mines, **show;
float **comp;
int length, width, num, player, pmine;

int min(int, int);
int max(int, int);
void get_parameter();
int check_parameter();
void alloc_memory();
void put_mime();
void get_mouse(int *, int *, int *);
void show_board(char *, int **);
void user();
void computer();
int open(int, int);
int count_neighbor(int, int, int **, int);

int min(int x, int y) { return (x > y? y: x); }
int max(int x, int y) { return (x > y? x: y); }

int count_neighbor(int x, int y, int **board, int s)
{
	int count = 0;
	for(int i = max(0, x - 1); i <= min(width - 1, x + 1); i++)
		for(int j = max(0, y - 1); j <= min(length - 1, y + 1); j++)
			if(*(*(board + i) + j) == s){
				count++;
			}
	return count;
}

void get_parameter()
{
	printf("width: "); scanf("%d", &width);
	printf("length: "); scanf("%d", &length);
	printf("How many mines: "); scanf("%d", &num);
	printf("Player?\n1.User\n2.Computer\n>"); scanf("%d", &player);
	printf("How to put mines?\n1.Random\n2.Custom\n>"); scanf("%d", &pmine);
}

int check_parameter()
{
	if(num * 2 > width * length){
		printf("Too many mines!\n");
		return 0;
	}
	return 1;
}

void alloc_memory()
{
	int i, j;

	mines = (int **)malloc(sizeof(int *) * width);
	show = (int **)malloc(sizeof(int *) * width);
	for(i = 0; i < width; i++)
	{
		*(mines + i) = (int *)malloc(sizeof(int) * length);
		*(show + i) = (int *)malloc(sizeof(int) * length);
	}
	for(i = 0; i < width; i++)
	{
		for(j = 0; j < length; j++)
		{
			*(*(mines + i) + j) = MINES_EMPTY;
			*(*(show + i) + j) = SHOW_CLOSE;
		}
	}

	if(player == PLAYER_COMPUTER){
		comp = (float **)malloc(sizeof(float *) * width);
		for(i = 0; i < width; i++)
		{
			*(comp + i) = (float *)malloc(sizeof(float) * length);
		}
	}
}

void put_mine()
{
	int count = 0, x, y, button;
	while(count != num)
	{
		if(pmine == PMINE_RANDOM){
			x = random() % width; y = random() % length;
		}else{
			get_mouse(&x, &y, &button);
		}
		if(*(*(mines + x) + y) == MINES_EMPTY){
			*(*(mines + x) + y) = MINES_MINE;
			count++;
		}else{
			*(*(mines + x) + y) = MINES_EMPTY;
			count--;
		}
		if(pmine == PMINE_CUSTOM){
			show_board("mines", mines);
		}
	}
}

void get_mouse(int *x, int *y,int *button)
{
	while(1)
	{
		printf("x: "); scanf("%d", x);
		printf("y: "); scanf("%d", y);
		printf("button:(1.Left 2.Right) "); scanf("%d", button);
		if(*x < 0 || *x >= width || *y < 0 || *y >= length || (*button != BUTTON_LEFT && *button != BUTTON_RIGHT)){
			continue;
		}else{
			break;
		}
	}
}

void show_board(char *caption, int **board)
{
	int i, j;
	char ch;

	for(i = 0; i < (78 - strlen(caption)) / 2; i++) printf("=");
	printf(" %s ", caption);
	for(i = 0; i < (78 - strlen(caption)) / 2; i++) printf("=");
	printf("\n   ");
	for(i = 0; i < length; i++) printf("%3d", i);
	printf("\n");
	for(i = 0; i < width; i++)
	{
		printf("%3d", i);
		for(j = 0; j < length; j++)
		{
			switch(*(*(board + i) + j))
			{
				case SHOW_MINE: ch = 'm'; break;
				case SHOW_CLOSE: ch = '#'; break;
				default: ch = *(*(board + i) + j) + '0'; break;
			}

			printf("%3c", ch);
		}
		printf("\n");
	}
}

void user()
{
	int x, y, button, found = 0, mark = 0;
	show_board("show", show);
	while(1)
	{
		get_mouse(&x, &y, &button);
		if(button == 1){
			if(*(*(mines + x) + y) == MINES_MINE){
				printf("Game Over!\n");
				show_board("mines", mines);
				break;
			}else if(*(*(show + x) + y) == SHOW_CLOSE){
				open(x, y);
				show_board("show", show);
			}
		}else{
			if(*(*(show + x) + y) != SHOW_CLOSE && *(*(show + x) + y) != SHOW_MINE){
				continue;
			}
			if(mark == num && *(*(show + x) + y) == 0){
				continue;
			}
			if(*(*(show + x) + y) == SHOW_CLOSE){
				*(*(show + x) + y) = SHOW_MINE;
				mark++;
				if(*(*(mines + x) + y) == MINES_MINE){
					found++;
				}
			}else{
				*(*(show + x) + y) = SHOW_CLOSE;
				mark--;
				if(*(*(mines + x) + y) == MINES_MINE){
					found--;
				}
			}
			show_board("show", show);
		}

		if(found == num){
			printf("You Win!\n");
			break;
		}
	}
}

void computer()
{
	int i, j, k, l, mines_left = num, close_left, x, y, flag;
	float minmin;
	while(mines_left > 0)
	{
		printf("%d mines left\n", mines_left);
		close_left = 0;
		for(i = 0; i < width; i++)
		{
			for(j = 0; j < length; j++)
			{
				if(*(*(show + i) + j) == SHOW_CLOSE){
					close_left++;
				}
			}
		}
		for(i = 0; i < width; i++)
		{
			for(j = 0; j < length; j++)
			{
				if(*(*(show + i) + j) == SHOW_CLOSE){
					*(*(comp + i) + j) = 1.0 * mines_left / close_left;
				}
			}
		}
		for(i = 0; i < width; i++)
		{
			for(j = 0; j < length; j++)
			{
				if(*(*(show + i) + j) >= 0 && *(*(show + i) + j ) <= 8 && count_neighbor(i, j, show, SHOW_CLOSE) != 0){
					for(k = max(0, i - 1); k <= min(width - 1, i + 1); k++)
					{
						for(l = max(0, j - 1); l <= min(length - 1, j + 1); l++)
						{
							if(*(*(show + k) + l) == SHOW_CLOSE && *(*(comp + k) + l) != 1 && *(*(comp + k) + l) != 0){
								*(*(comp + k) + l) = 1.0 * (*(*(show + i) + j) - count_neighbor(i, j, show, SHOW_MINE)) / count_neighbor(i, j, show, SHOW_CLOSE);
							}
						}
					}
				}
			}
		}

		flag = 0;
		for(i = 0; i < width; i++)
		{
			for(j = 0; j < length; j++)
			{
				if(*(*(show + i) + j) == SHOW_CLOSE){
					if(*(*(comp + i) + j) == 1){
						mines_left--;
						printf("Find a mine at (%d, %d)\n", i, j);
						*(*(show + i) + j) = SHOW_MINE;
						show_board("show", show);
						flag = 1;
					}else if(*(*(comp + i) + j) == 0){
						printf("open (%d, %d)\n", i, j);
						open(i, j);
						show_board("show", show);
						flag = 1;
					}
				}
			}
		}
		if(flag == 1){
			continue;
		}

		minmin = 1;
		for(i = 0; i < width; i++)
		{
			for(j = 0; j < length; j++)
			{
				if(*(*(show + i) + j) == SHOW_CLOSE){
					if(*(*(comp + i) + j) < minmin){
						minmin = *(*(comp + i) + j);
						x = i;
						y = j;
					}
				}
			}
		}
		printf("open (%d, %d)\n", x, y);
		if(*(*(mines + x) + y) == MINES_MINE){
			printf("Computer dead!\n");
			break;
		}else{
			open(x, y);
			show_board("show", show);
		}
	}
}

int open(int x, int y)
{
	*(*(show + x) + y) = count_neighbor(x, y, mines, MINES_MINE);
	if(*(*(show + x) + y) == 0){
		for(int i = max(0, x - 1); i <= min(width - 1, x + 1); i++)
			for(int j = max(0, y - 1); j <= min(length - 1, y + 1); j++)
				if(*(*(show + i) + j) == SHOW_CLOSE){
					open(i, j);
				}
	}
}

main()
{
	get_parameter();
	if(!check_parameter()){
		exit(0);
	}
	alloc_memory();
	put_mine();
	if(player == PLAYER_USER){
		user();
	}else{
		computer();
	}
}