//Compile: gcc -Wall minesweeper.c -o minesweeper

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

//unaufgedecktes Feld
#define UNKNOWN_FIELD 'x'
//eine Mine
#define MINE_FIELD '@'

//Speicher freigeben
void free_minefield( char **minefield, int rows ) {
	int i;
	//Jeden Vektor freigeben
	for (i = 0; i < rows; i++) {
    		free(minefield[i]);
   	}
   	free(minefield);
   	minefield = NULL;
}

/*
 * Speicher allozieren und matrix initialisieren
 *
 * BEACHTE:  
 * Das Minenfeld wird "in" der Funktion angelegt
 * Der Rueckgabewert ist daher ein char **
 *
 */    
char ** create_minefield( int rows, int columns, char init ) {
	int i, j;
	
	//Minenfeld anlegen
	char ** minefield = (char **) calloc(rows, sizeof(char*));
	
	//Falls wir keinen Speicher bekommen beenden wir das Programm
	if ( !minefield ) {
		printf( "Can't allocate memory for minefield.\n");
		exit(1);
	}
	
	//jedes Element von minefield[i] ist wiederum ein Vektor
	// => Damit kann man wie gewohnt auf Elemente der Matrix zugreifen
	// => minefield[i][j]
	for (i = 0; i < rows; i++) {
		minefield[i] = (char *) calloc( columns, sizeof(char) );
	}

	for(i=0; i < rows; i++) {
		for(j=0; j < columns; j++) {
			minefield[i][j] = init;
		}
	}	
	
	//Einen Zeiger auf das Minenfeld zurueckgeben
	return minefield;
}

//Zufaellig die Minen verteilen
void init_mines( char ** mines, int rows, int columns, int mines_count ) {
	int i, rand_row, rand_columns;
	
	srand(time(NULL));

	i = mines_count;

	while( i > 0 ) {
		//Zufaellige Position innerhalb der Matrix erzeugen
		rand_row = (rand()%rows);
		rand_columns = (rand()%columns);
		//Ist dort noch keine Mine?
		if( mines[rand_row][rand_columns] == 0 ) {
			//For cheaters ;-)
			//printf( "mine at %d, %d\n", rand_row, rand_columns );
			mines[rand_row][rand_columns] = 1;
			i--;
		}
	}
}

//Sind alle Minen gefunden
int check_finish( char ** minefield, char ** mines, int rows, int columns ) {
	int i, j;

	for(i=0; i < rows; i++) {
		for(j=0; j < columns; j++) {
			//Ist ein Feld noch nicht aufgedeckt welches KEINE Mine enthaelt
			//ist das Spiel noch nicht vorbei
			if( (mines[i][j] == 0) && (minefield[i][j] == UNKNOWN_FIELD) ) {
				return 0;
			}
		}
	}
	
	return 1;

}


/*
 * Anzeige
 *  
 * durch %3... wird erreicht, dass die Ausgabe immer 3 Zeichen lang ist 
 * => Sieht sonst einfach nicht schoen aus...
 *
 */    
void show_minefield( char ** minefield, int rows, int columns ) {
	int i, j;
	
	printf("\n\n");
	//Spaltenbeschriftung
	printf("    ");
	for(i=0; i < columns; i++) {
		printf("%3d", i+1);
	}
	printf("\n");
	
	//Trennzeile
	printf("    ");
	for(i=0; i < columns; i++) {
		printf("---");
	}
	printf("\n");
	
	
	for(i=0; i < rows; i++) {
		//Zeilenbeschriftung
		printf("%3d|", i+1);
		for(j=0; j < columns; j++) {
			//Ausgabe des Spielfelds
			printf("%3c", minefield[i][j]);
		}
		//Zeilenbeschriftung
		printf(" |%-3d\n", i+1);
	}
	//Trennzeile
	printf("    ");
	for(i=0; i < columns; i++) {
		printf("---");
	}
	printf("\n");
	//Spaltenbeschriftung	
	printf("    ");
	for(i=0; i < columns; i++) {
		printf("%3d", i+1);
	}
	printf("\n\n");
	
}

//Minen anzeigen
void show_mines( char ** mines, int rows, int columns ) {
	int i, j;
	
	printf("\n\n");
	//Spaltenbeschriftung
	printf("    ");
	for(i=0; i < columns; i++) {
		printf("%3d", i+1);
	}
	printf("\n");
	
	//Trennzeile
	printf("    ");
	for(i=0; i < columns; i++) {
		printf("---");
	}
	printf("\n");
	
	for(i=0; i < rows; i++) {
		//Zeilenbeschriftung
		printf("%3d|", i+1);
		for(j=0; j < columns; j++) {
			//Minen ausgeben
			if( mines[i][j] == 1) {
				printf("  %c", MINE_FIELD);
			}
			else {
				printf("  %c", UNKNOWN_FIELD);
			}
		}
		//Zeilenbeschriftung
		printf(" |%-3d\n", i+1);
	}
	
	//Trennzeile
	printf("    ");
	for(i=0; i < columns; i++) {
		printf("---");
	}
	printf("\n");
	
	//Spaltenbeschriftung
	printf("    ");
	for(i=0; i < columns; i++) {
		printf("%3d", i+1);
	}
	printf("\n\n");	
}

/*
 * Das Spielfeld an der gegebenen Position ueberpruefen.
 * Es wird die Umgebung analysiert und die entsprechende Anzahl der umliegenden Minen eingetragen.
 * Diese Funktion ist Rekurisv und deckt auch alle Felder mit '0' Minen auf.
 * 
 */   
int check_field( char ** minefield, char ** mines, int rows, int columns, int row, int column ) {
	char counter = 0;

	if( (row < 0) || (row >= rows) || (column < 0) || (column >= columns)) {
		printf("Out of minefield execption!\n");
		return -1;
	}
	//An dieser Postion ist eine Mine 
	if( mines[row][column] == 1 ) {
		return 0;
	}
	
	//An der Position ist keine Mine aber wie viele gibts um mich herum?
	if( (row+1 < rows) && (mines[row+1][column] == 1) ) {
		counter++;
	}	
	if( (row-1 >= 0) && (mines[row-1][column] == 1) ) { 
		counter++;
	}
	if( (column+1 < columns) && (mines[row][column+1] == 1) ) { 
		counter++;
	}
	if( (column-1 >= 0) && (mines[row][column-1] == 1) ) {
		counter++;
	}
	if( (row+1 < rows) && (column-1 >= 0) && (mines[row+1][column-1] == 1) ) { 
		counter++;	
	}
	if( (row-1 >= 0) && (column+1 < columns) && (mines[row-1][column+1] == 1) ) { 
		counter++;
	}
	if( (row+1 < rows) && (column+1 < columns) && (mines[row+1][column+1] == 1) ) { 
		counter++;	
	}		
	if( (row-1 >= 0) && (column-1 >= 0) && (mines[row-1][column-1] == 1) ) { 
		counter++;	
	}	
	
	//Anzahl der Minen um die Position herum. 0...8
	//Ab der Position 48 in der ASCII-Tabelle beginnen die Zahlen => 48+counter
	minefield[row][column] = 48+counter;
	
	//Ist eine Mine in der Umgebung braucht nicht weiter aufgedeckt werden
	if( counter > 0 ) {		
		return 1;
	}

	/* 
	 * An dieser Stelle ist keine Mine.
	 * Das Feld kann also aufgedeckt werden => '0'-Feld
	 * Ist eines meiner Nachbarfelder auch ein '0'-Feld?
	 */	 	 	 
	if( (row+1 < rows) && (minefield[row+1][column] == UNKNOWN_FIELD) && (mines[row+1][column] == 0) ) {
		check_field( minefield, mines, rows, columns, row+1, column );
	}

	if( (row-1 >= 0) && (minefield[row-1][column] == UNKNOWN_FIELD) && (mines[row-1][column] == 0) ) { 
		check_field( minefield, mines, rows, columns, row-1, column );
	}
	
	if( (column+1 < columns) && (minefield[row][column+1] == UNKNOWN_FIELD) && (mines[row][column+1] == 0) ) { 
		check_field( minefield, mines, rows, columns, row, column+1 );
	}
	
	if( (column-1 >= 0) && (minefield[row][column-1] == UNKNOWN_FIELD) && (mines[row][column-1] == 0) ) { 
		check_field( minefield, mines, rows, columns, row, column-1 );
	}

	if( (row+1 < rows) && (column-1 >= 0) && (minefield[row+1][column-1] == UNKNOWN_FIELD) && (mines[row+1][column-1] == 0) ) { 
		check_field( minefield, mines, rows, columns, row+1, column-1 );
	}

	if( (row-1 >= 0) && (column+1 < columns) && (minefield[row-1][column+1] == UNKNOWN_FIELD) && (mines[row-1][column+1] == 0) ) { 
		check_field( minefield, mines, rows, columns, row-1, column+1 );
	}

	if( (row+1 < rows) && (column+1 < columns) && (minefield[row+1][column+1] == UNKNOWN_FIELD) && (mines[row+1][column+1] == 0) ) { 
		check_field( minefield, mines, rows, columns, row+1, column+1 );
	}	
	
	if( (row-1 >= 0) && (column-1 >= 0) && (minefield[row-1][column-1] == UNKNOWN_FIELD) && (mines[row-1][column-1] == 0) ) { 
		check_field( minefield, mines, rows, columns, row-1, column-1 );
	}
		
	return 1;
}

int main(void) {
	int rows, columns, mines_count;
	int row, column;
	
	//Eingabe einlesen
	printf("Geben Sie die Spielfeldgroesse ein (Zeilen Spalten):\n");
	if( (scanf("%d %d", &rows, &columns) != 2) || (rows <= 0) || (columns <= 0) ) {
		printf("Falsche Eingabe!\n");
		return 1;
	}

	printf("Wieviele Minen (Es muessen weniger als %d sein):\n", (rows*columns) );
	if( (scanf("%d", &mines_count) != 1)|| (mines_count <= 0) || (mines_count >= (rows*columns)) ) {
		printf("Falsche Eingabe!\n");
		return 1;
	}
	
	printf("Die Spielfeldgroesse ist %d x %d, mit %d Minen\n", rows, columns, mines_count);

	//Eine Matrix fuer das Spielfeld
	char **minefield = create_minefield( rows, columns, UNKNOWN_FIELD );
	//Eine Matrix fuer die Minen
	char **mines = create_minefield( rows, columns, 0 );
	
	//Die Minen in der Matrix verteilen
	init_mines( mines, rows, columns, mines_count );
	
	//Das Spielfeld anzeigen => Noch ist alles verdeckt
	show_minefield( minefield, rows, columns );
	
	
	while(1) {

	  	printf("'Zeile Spalte' zum aufdecken eingeben (zum Beenden '0 0'):\n");
	  	if( scanf("%d %d",&row, &column) != 2 ) {	
	  		printf("Falsche Eingabe!\n");
			return 1;
		}	
		
		row--;
		column--;
		
		//Beenden 
		if( (row == -1) && (column == -1) ) {
			break;		
		}
		
		//Feldgrenzen abfragen
		if( row >= rows || row < 0 ) {
			printf("Zeile muss zwischen 1 und %d sein!\n", rows);
			continue;
		}
		if( column >= columns || column < 0 ) {
			printf("Spalte muss zwischen 1 und %d sein!\n", columns);
			continue;
		}
		
		//Ist man auf einer Mine gelandet?
		if( check_field( minefield, mines, rows, columns, row, column ) == 0 ) {
			//Zeige die Minen an
			show_mines( mines, rows, columns );
			printf("Zeile: %d Spalte: %d war leider eine Mine!\n", row+1, column+1 );
			break;
		}
		//Ist man fertig?
		else if( check_finish(minefield, mines, rows, columns) ) {
			//Zeige die Minen an
			show_minefield( minefield, rows, columns );
			printf("Super! Korrekt geloest!\n");
			break;
		}
		//Aktuelles Feld zum weiterspielen anzeigen
		else {	
			show_minefield( minefield, rows, columns );
		}
	}
	
	//Speicher freigeben	
	free_minefield( minefield, rows );
	free_minefield( mines, rows );
	
	return 1;
}