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

#define N 5

#define EMPTY 0
#define BLACK 1
#define WHITE 2

/* Das Spielfeld als globale Variable. Jedes Feld kann einen der drei
 * Werte EMPTY, BLACK  oder WHITE haben.
 */
int field[N][N];

/* Die Anzahl der gefangenen Steine der beiden Spieler. Index 0 ist
 * ungenutzt.
 */
int pts[3];

/* Spielfeld mit Koordinaten etc. auf dem Bildschirm ausgeben.
 */
void draw (void)
{
	int i, j;
	char ch = 0;
	printf ("   +");
	for (i=0; i<2*N+1; ++i) {
		printf ("-");
	}
	printf ("+\n");
	for (i=N-1; i>=0; --i) {
		printf ("%2d | ", i+1);
		for (j=0; j<N; ++j) {
			switch (field[i][j]) {
			case BLACK:
				ch = '#';
				break;
			case WHITE:
				ch = 'O';
				break;
			case EMPTY:
				ch = '.';
				break;
			default:
				assert (0);
			}
			printf ("%c ", ch);
		}
		printf ("|\n");
	}
	printf ("   +");
	for (i=0; i<2*N+1; ++i) {
		printf ("-");
	}
	printf ("+\n");
	printf ("     ");
	for (i=0; i<N; ++i) {
		printf ("%c ", 'A'+i);
	}
	printf ("\n");
	printf ("Punkte #: %d       Punkte O: %d\n", pts[BLACK], pts[WHITE]);
}

/* Das als Zeiger uebergebene NxN Array wird mit Nullen initialisiert. */
void init_beenthere (int beenthere[N][N])
{
	int i, j;
	for (i=0; i<N; ++i)
		for (j=0; j<N; ++j)
			beenthere[i][j] = 0;
}

/* Liefert TRUE zurueck, wenn (si, sj) gueltige Koordinaten in
 * field[][] sind, FALSE sonst.
 */
int valid (int si, int sj)
{
	if ((si < 0) || (sj < 0))
		return 0;
	if ((si >= N) || (sj >= N))
		return 0;
	return 1;
}

/* Liefert den jeweils anderen Spieler, wenn BLACK uebergeben wird ist
 * der Rueckgabewert WHITE und umgekehrt. Die Funktion darf nur mit
 * diesen beiden Werten als Argument aufgerufen werden, alles andere
 * fuehrt zu einem Programmabbruch.
 */
int other (int col)
{
	switch (col) {
	case BLACK:
		return WHITE;
	case WHITE:
		return BLACK;
	}
	assert (0);
	/* NOT REACHED */
	return EMPTY;
}

/* Die rekursiv aufgerufene Prozedur um eine zusammenhaengede Gruppe von
 * Steinen der Farbe col zu loeschen. si und sj geben die Koordinaten des
 * Steins an, der durch diesen Aufruf geloescht werden soll. Der Rest der
 * Gruppe geloescht, indem die Prozedur rekursiv fuer die 4 Nachbarsteine
 * aufgerufen wird.
 * Wenn die Koordinaten nicht gueltig sind, oder wenn die Farbe des
 * Spielsteins auf den Koordinaten si/sj nicht mit col uebereinstimmt
 * wird dieser Zweig der Rekursion abgebrochen.
 * Das Array beenthere teilen sich alle rekursiven Aufrufe (es wird immer
 * nur ein Zeiger auf das array uebergeben). Wenn tatsaechlich ein
 * Stein geloescht wurde, dann wird dessen Eintrag in beenthere auf 1
 * gesetzt. Sollten wir im Laufe der Rekursion wieder zurueck zu den
 * selben Koordinaten kommen, dann muss nicht mehr getan werden und dieser
 * Zweig der Rekursion wird ebenfalls abgebrochen.
 */
void removegroup2 (int si, int sj, int col, int beenthere[N][N])
{
	if (!valid (si, sj))
		return;
	if (field[si][sj] != col)
		return;
	if (beenthere[si][sj])
		return;
	beenthere[si][sj] = 1;
	field[si][sj] = EMPTY;
	pts[other(col)]++;
	removegroup2 (si-1, sj, col, beenthere);
	removegroup2 (si+1, sj, col, beenthere);
	removegroup2 (si, sj-1, col, beenthere);
	removegroup2 (si, sj+1, col, beenthere);
}

/* Diese Funktion loescht die Gruppe, die den Stein mit den Koordinaten
 * si und sj enthaelt. Dazu wird zuerst dessen Farbe ermittelt und ein
 * neues beenthere-Array mit lauter Nullen initialisiert. Das eigentliche
 * Loeschen erledigt dann die Prozedur removegroup2.
 * Wenn die Koordinaten ungueltig sind oder wenn auf dem angegebenen
 * Kreuzungspunkt kein Spielstein steht, dann wird das Programm abgeborchen.
 */
void removegroup (int si, int sj)
{
	int beenthere[N][N];
	int col;
	init_beenthere (beenthere);
	assert (valid (si, sj));
	col = field[si][sj];
	assert (col == BLACK || col == WHITE);
	removegroup2 (si, sj, col, beenthere);
}

/* Rekursive Prozedur um zu ermitteln, ob eine Gruppe noch mindestens eine
 * Freiheit hat. Die Parameter werden analog zu removegroup2 verwendet.
 * Um diese Frage zu entscheiden, muessen alle Steine, die
 * zu der Gruppe gehoeren durchlaufen werden. Sobald ein solcher Stein
 * gefunden wird, der noch einen unbesetzten Nachbarkreuzungspunkt hat, hat die
 * gesamte Gruppe noch mind. eine Freiheit. Wir betrachten also die 4
 * Nachbarkreuzunspunkte wieder mit Hilfe von rekursiven Aufrufen.
 * - Ist einer davon leer, so wurde eine Freiheit gefunden und wir
 *   sind fertig (Rueckgabewert 1: Freiheit gefunden).
 * - Liegt der "Nachbarkreuzungspunkt" ausserhalb des Speilbretts oder wurde
 *   er bereits in einem frueheren Stadium dieser Rekursion untersucht, so
 *   werden wir hier keine weiteren Freiheiten finden und sind ebenfalls
 *   fertig (Rueckgabewert 0: Zumindest hier keine Freiheit gefunden).
 * - Wenn der Kreuzungspunkt mit einem Stein der gegenerischen Farbe
 *   besetzt ist, so werden wir in diesem Zweig der Rekursion ebenfalls
 *   keine Freiheit der Gruppe finden, da ja nur unbesetzte
 *   Nachbarkreuzungspunkte als Freiheiten zaehlen (Rueckgabewert 0).
 * - In allen anderen Faelle ist der aktuelle Kreuzungspunkt mit einem zur
 *   zu untersuchenden Gruppe gehoerenden Spielstein besetzt (die Farbe
 *   des Steins an den Koordinaten si/sj stimmt mit col ueberein). In
 *   diesem Fall muessen wir die vier Nachbarn mit Hilfe rekursiver Aufrufe
 *   untersuchen. Findet einer der rekursiven Aufrufe eine Freiheit, so
 *   hat die Gruppe eine Freiheit (Rueckgabewert 1) ansonsten wurde in
 *   diesem Zweig der Rekursion keine Freiheit gefunden (Rueckgabewert 0).
 */
int has_freedom2 (int si, int sj, int col, int beenthere[N][N])
{
	if (!valid (si, sj))
		return 0;
	if (field[si][sj] == EMPTY)
		return 1;
	if (beenthere[si][sj])
		return 0;
	beenthere[si][sj] = 1;
	if (field[si][sj] == other (col))
		return 0;
	assert (field[si][sj] == col);
	if (has_freedom2 (si-1, sj, col, beenthere))
		return 1;
	if (has_freedom2 (si+1, sj, col, beenthere))
		return 1;
	if (has_freedom2 (si, sj-1, col, beenthere))
		return 1;
	if (has_freedom2 (si, sj+1, col, beenthere))
		return 1;
	return 0;
}

/* Diese Prozedur ermittelt analog zu removegroup ob die Gruppe bei den
 * Koordinaten si/sj eine Freiheit besitzt. Dazu wird eine Rekursion gestartet
 * indem has_freedom2 einem aufgerufen wird. Der Rueckgabewert ist 
 * -1 falls die Koordinaten ungueltig oder der Kreuzungspunkt si/sj leer war.
 *  0 falls bei si/sj eine Gruppe existiert, die aber keine Freiheit hat.
 *  1 falls bei si/sj eine Gruppe existiert, die eine Freiheit hat.
 */
int has_freedom (int si, int sj)
{
	int beenthere[N][N];
	int col;
	init_beenthere (beenthere);
	if (!(valid (si, sj)))
		return -1;
	if (field[si][sj] == EMPTY)
		return -1;
	col = field[si][sj];
	assert ((col == BLACK) || (col == WHITE));
	return has_freedom2 (si, sj, col, beenthere);
}

/* Einen Zug durchfuehren. i und j sind die Koordinaten, col ist die
 * Farbe des neu zu plazierenden Steins. Die Prozedur liefert 0 oder 1
 * zurueck, je nach dem, ob der Zug erfolgreich durchgefuehrt werden
 * konnte oder nicht. Beim Rueckgabewert 0 bleibt das Spielfeld unveraendert.
 * - Zunaechst wird ueberprueft, ob die Koordinaten si/sj gueltig sind und
 *   der zugehoerige Kreuzungspunkt noch unbesetzt ist. Falls nicht, ist
 *   der Zug ungueltig.
 * - Dann wird der neue Stein probehalber plaziert.
 * - Im naechsten Schritt wird untersucht, ob es auf einem der vier
 *   Nachbarkreuzungspunkte eine Gruppe gibt, die keine Freiheiten mehr
 *   hat (has_freedom (...) == 0) und ob diese Gruppe dem Gegenspieler
 *   gehoert (field[][] != col). Falls eine oder mehrere solcher Gruppen
 *   gefunden werden, werden sie entfernt (removegroup).
 *   Wenn wir eine gegnerische Gruppe, die zu unserem neuen Stein benachbart
 *   ist entfert haben, so hat dieser Stein natuerlich mindestens eine
 *   Freiheit. Damit ist der Zug auf jeden Fall gueltig und muessen daher
 *   nicht in der Lage sein, das Loeschen einer Gruppe rueckgaenig zu machen.
 * - Nachdem ggf. alle gegnerischen Gruppen ohne Freiheiten entfernt wurden,
 *   ueberprueft ein letzter Aufruf von has_freedom ob die Gruppe des gerade
 *   neu plazierten Steins eine Freiheit besitzt. Falls nicht, war der Zug
 *   ungueltig, was aber nur passieren kann, wenn noch keine gegnerische
 *   Gruppe entfernt wurde. In diesem Fall wird die einzige Veraenderung am
 *   Spielfeld, naemlich das plazieren eines Steins auf si/sj rueckgaenig
 *   gemacht und 0 zurueckgeliefert.
 * - Ansonsten war der Zug gueltig und der Rueckgabewert ist daher 1.
 */

int domove (int i, int j, int col)
{
	if (!valid (i, j))
		return 0;
	if (field[i][j] != EMPTY)
		return 0;
	if ((col != BLACK) && (col != WHITE))
		return 0;
	field[i][j] = col;
	if ((has_freedom (i-1, j) == 0) && (field[i-1][j] != col))
		removegroup (i-1, j);
	if ((has_freedom (i+1, j) == 0) && (field[i+1][j] != col))
		removegroup (i+1, j);
	if ((has_freedom (i, j-1) == 0) && (field[i][j-1] != col))
		removegroup (i, j-1);
	if ((has_freedom (i, j+1) == 0) && (field[i][j+1] != col))
		removegroup (i, j+1);
	if (has_freedom (i,j) != 1) {
		field[i][j] = EMPTY;
		return 0;
	}
	return 1;
}

/* Hauptprogramm. Hier wird zunaechst das Feld initialisiert.
 * Anschliessend werden Zuege eingelesen und mit Hilfe von domove
 * durchgefuehrt. Gibt ein Spieler PASS ein, so wird ein Gefangener
 * Stein abgegeben, oder das Spiel ist verloren, wenn kein Stein zum
 * abgeben vorhanden ist.
 */
int main ()
{
	int i, j, col = BLACK;
	char sign[3] = " #O";
	char buf[100];
	for (i=0; i<N; ++i)
		for (j=0; j<N; ++j) {
			field[i][j] = EMPTY;
		}
	while (1) {
		char tmp;
		draw ();
		printf ("Move of %c: ", sign[col]);
		if (fgets (buf, 100, stdin) == 0) {
			printf ("Illegal move\n");
			continue;
		}
		if (strcasecmp (buf, "pass\n") == 0) {
			if (pts[col] <= 0)
				break;
			pts[col]--;
			col = other (col);
			continue;
		}
		if (sscanf (buf, "%c%d", &tmp, &i) != 2) {
			printf ("Illegal move\n");
			continue;
		}
		i--; j = tmp - 'A';
		if (domove (i, j, col)) {
			col = other (col);
		} else {
			printf ("Illegal move\n");
		}
	}
	draw ();
	if (col == WHITE) {
		printf ("BLACK(#) WINS\n");
	} else {
		assert (col == BLACK);
		printf ("WHITE(O) WINS\n");
	}
	return 0;
}