/*	schachbrett.c -- Matthias Jauernig, 10.12.03					*/
/*	Programm simuliert ein Schachbrett von n*n Feldern und setzt zufällig		*/
/*	k Damen darauf; dann wird errechnet, welche Damen sich gegenseitig bedrohen	*/

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

/* -- bedrohen() -- gibt aus, von welchen Damen die auf a[i][j] bedroht wird ----------	*/
void bedrohen(short **a, const int i, const int j, const int n){
	int k, l;
	short h;
	// zur Vermeidung von doppelten Einträgen werden nur die Damen betrachtet, die
	// weiter rechts bzw. weiter unten stehen, da die Matrix a[][] zeilenweise von
	// links nach rechts abgearbeitet wird; ebenso bedrohen sich nur Damen, zwischen
	// denen sich keine andere Dame befindet, also muss nach der ersten gefundenen
	// Dame in jeder Richtung Schluss sein
	//###################### 1.) Wird Dame horizontal bedroht? #######################
	for(k=j+1, h=0; k<n && h==0; k++)
		if(a[i][k]==1){
			printf("[%d][%d]  und  [%d][%d]\n", i, j, i, k);
			h=1;
		}

	//###################### 2.) Wird Dame vertikal bedroht? #########################
	for(k=i+1, h=0; k<n && h==0; k++)
		if(a[k][j]==1){
			printf("[%d][%d]  und  [%d][%d]\n", i, j, k, j);
			h=1;
		}

	//############## 3.) Wird Dame auf der Hauptdiagonalen bedroht? ##################
	for(k=i+1, l=j+1, h=0; k<n && l<n && h==0; k++, l++)
		if(a[k][l]==1){
			printf("[%d][%d]  und  [%d][%d]\n", i, j, k, l);
			h=1;
		}

	//############### 4.) Wird Dame auf der Nebendiagonalen bedroht? #################
	for(k=i+1, l=j-1, h=0; k<n && l>=0 && h==0; k++, l--)
		if(a[k][l]==1){
			printf("[%d][%d]  und  [%d][%d]\n", i, j, k, l);
			h=1;
		}
}

/* -- printline() -- gibt eine Linie für die Ausgabe des Schachbretts aus -------------	*/
void printline(int fl, int n){
	int i, j;

	printf("   ");
	for(i=1; i<=n; i++){
		printf("+");
		for(j=1; j<=fl; j++)
			printf("-");
	}
	printf("+\n");
}

/* -- ausg_brett() -- gibt das gesamte Brett aus --------------------------------------	*/
void ausg_brett(short **a, int n){
	int i, j;

	printf("\n    ");
	for(i=0; i<n; i++)
		printf("%2d  ", i);
	printf("\n");
	for(i=0; i<n; i++){
		printline(3, n);
		printf("%2d ", i);
		for(j=0; j<n; j++)
			printf("| %s ", (a[i][j]==1) ? "x" : " ");
		printf("|\n");
	}
	printline(3, n);
}


/* -- ANSI C89/C99/C++ verbieten main() ohne Rückgabewert, also "int main(void)"!!! -----------	*/
int main(void){
	short **a;
	int i, j, k, n, x, y;
	// Zufallsgenerator initialisieren
	srand(time(NULL));

	//######################### Eingabe und Speicherallokierung ##############################
	printf(	"Bedrohliche Damen\n"
		"-----------------\n\n");
	do{
		printf("Kantenlänge des Schachbretts (Felder)?: ");
		scanf("%d", &n);
	}while(n<1 && printf("=> n muss größer als 0 sein!\n\n"));

	// zunächst Speicher für die Zeiger auf die short-Vektoren allokieren
	a=(short **)malloc(n*sizeof(short *));
	// nun Speicher für jeden short-Vektor allokieren
	for(i=0; i<n; i++){
		a[i]=(short *)malloc(n*sizeof(short));
		// Werte im aktuellen short-Vektor gleich 0 setzen
		for(j=0; j<n; j++)
			a[i][j]=0;
	}

	do{
		printf("Wieviele Damen sollen sich darauf befinden?: ");
		scanf("%d", &k);
	}while((k<1 && printf("=> k muss größer als 0 sein!\n\n"))
		|| (k>n*n && printf("=> Höchstens %d Damen!\n\n", n*n)));

	//################################## Damen aufstellen ####################################
	printf("\n=> Damen befinden sich nun auf folgenden Feldern:\n");
	for(i=1; i<=k; i++){
		do{
			// x- und y-Koordinate des Feldes zufällig wählen
			x=rand()%n;
			y=rand()%n;
		}while(a[x][y]==1); // wenn schon besetzt, dann erneut wählen
		a[x][y]=1;
		if(i%8==0) printf("\n");
		printf("[%d][%d], ", x, y);
	}
	printf("\b\b \n\n");
	if(n<19)
		ausg_brett(a, n);

	//########################### sich bedrohende Damen ausgeben #############################
	printf("\n=> Felder sich bedrohender Damen:\n");
	// das Array zeilenweise (i) von links nach rechts (j) durchgehen
	for(i=0; i<n; i++)
		for(j=0; j<n; j++)
			if(a[i][j]==1) // wenn Feld mit Dame besetzt, dann schauen, ob bedroht
				bedrohen(a, i, j, n);
	printf("\n");

	//############################ Speicherfreigabe und Ende #################################
	// Speicher wieder freigeben: erst einzelne short-Vektoren, dann die Zeiger darauf
	for(i=0; i<n; i++)
		free(a[i]);
	free(a);

	return 0;
}


/* Beispielausgaben:
####################################################################
Bedrohliche Damen
-----------------

Kantenlänge des Schachbretts (Felder)?: 16
Wieviele Damen sollen sich darauf befinden?: 5

=> Damen befinden sich nun auf folgenden Feldern:
[7][8], [7][15], [8][4], [10][0], [14][8]


     0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 0 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 1 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 2 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 3 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 4 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 5 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 6 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 7 |   |   |   |   |   |   |   |   | x |   |   |   |   |   |   | x |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 8 |   |   |   |   | x |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 9 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
10 | x |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
11 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
12 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
13 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
14 |   |   |   |   |   |   |   |   | x |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
15 |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

=> Felder sich bedrohender Damen:
[7][8]  und  [7][15]
[7][8]  und  [14][8]
[7][15]  und  [14][8]

####################################################################
Bedrohliche Damen
-----------------

Kantenlänge des Schachbretts (Felder)?: 2
Wieviele Damen sollen sich darauf befinden?: 4

=> Damen befinden sich nun auf folgenden Feldern:
[0][1], [1][1], [0][0], [1][0]


     0   1
   +---+---+
 0 | x | x |
   +---+---+
 1 | x | x |
   +---+---+

=> Felder sich bedrohender Damen:
[0][0]  und  [0][1]
[0][0]  und  [1][0]
[0][0]  und  [1][1]
[0][1]  und  [1][1]
[0][1]  und  [1][0]
[1][0]  und  [1][1]

####################################################################*/