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

#define N 5

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

/* Spielfeld  */
int field[N][N];
/* Welcher Kreuzungspunkt gehoert zu welcher Gruppe. Ein Kreuzungspunkt
 * zeigt auf einen anderen und der wieder auf einen anderen etc. indem 
 * group[i][j] = N*i2+j2 gesetzt wird, wobei dann i/j auf i2/j2 zeigt.
 * Zeigt ein Kreuzungspunkt auf sich selbst, so ist er der Repraesentant
 * seiner Gruppe.
 */
int group[N][N];
int pts[3];

int other (int col)
{
	switch (col) {
	case BLACK:
		return WHITE;
	case WHITE:
		return BLACK;
	}
	assert (0);
	/* NOT REACHED */
	return EMPTY;
}

void groups (void);
void freedoms (void);
int root (int si, int sj);

/* Spielfeld zeichnen.  */
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]);
}

/* Den Repraesentant einer Gruppe finden indem wir solange zum naechsten
 * Kreuzungspunkt in group[][] springen, bis wir einen finden, der auf
 * sich selbst zeigt.
 */
int root (int si, int sj)
{
	int ni, nj;
	if (group[si][sj] == -1)
		return -1;
	while (1) {
		ni = group[si][sj] / N;
		nj = group[si][sj] % N;
		if ((ni == si) && (nj == sj))
			return group[si][sj];
		si = ni; sj = nj;
	}
}

/* Zwei Gruppen vereinigen. Das passiert indem der repraesentant der ersten
 * auf den Repraesentant der zweiten Gruppe zeigt.
 */

void join (int i1, int j1, int i2, int j2)
{
	int r1, r2;
	r1 = root (i1, j1);
	r2 = root (i2, j2);
	if (r1 != r2)
		group[r1/N][r1%N] = r2;
}

/* Alle Steine einer Gruppe loeschen. Dazu werden zunaechst mit
 * groups die Gruppen bestimmt (vom Aufrufer) und dann alle Kreuzungspunkte
 * die den selben Repraesentant haben wie si/sj auf EMPTY gesetzt werden.
 */
void removegroup (int si, int sj)
{
	int i, j;
	int r = root (si, sj);
	int col = field[si][sj];
	assert ((col == BLACK) || (col == WHITE));
	col = other (col);
	groups ();
	for (i=0; i<N; ++i)
		for (j=0; j<N; ++j)
			if ((field[i][j] != EMPTY) && (root (i, j) == r)) {
				field[i][j] = EMPTY;
				pts[col]++;
			}
}

/* Gruppen/Repraesentanten bestimmen. Dazu ist zunaechst jeder Stein sein
 * eigener Repraesentant. Dann werden alle Nachbarschaftsbeziehungen
 * durchlaufen und wenn zwei benachbarte Steine gleicher Farbe gefunden
 * werden, dann werden Ihre Gruppen vereinigt, d.h. der Repraesentant
 * der einen Gruppe wird auch der Repraesentant der anderen.
 */
void groups (void)
{
	int i, j;
	for (i=0; i<N; ++i)
		for (j=0; j<N; ++j)
			if (field[i][j] == EMPTY)
				group[i][j] = -1;
			else
				group[i][j] = i*N+j;
	for (i=0; i < N; ++i) {
		for (j=0; j < N-1; ++j) {
			if ((field[i][j] != EMPTY)
			    && (field[i][j] == field[i][j+1]))
				join (i, j, i, j+1);
			if ((field[j][i] != EMPTY)
			    && (field[j][i] == field[j+1][i]))
				join (j, i, j+1, i);
		}
	}
}

/* TRUE wenn eine Gruppe Freiheiten hat. Dazu werden zunaechste die
 * Gruppen bestimmt und beim ri*N+rj wobei (ri/rj) der Repraesentant
 * der Gruppe ist wird 1 bzw. 0 eingetragen, je nach dem ob die
 * zugehoerige Gruppe eine Freiheit hat oder nicht.
 */
int freedom[N*N];

/* Eine Freiheit fuer die Gruppe an i/j eintragen. */
void set_freedom (int i, int j)
{
	if (i < 0)
		return;
	if (j < 0)
		return;
	if (i >= N)
		return;
	if (j >= N)
		return;
	if (field[i][j] == EMPTY)
		return;
	freedom[root (i,j)] = 1;
}

/* Testen, ob die Gruppe an i/j eine Freiheit hat. */
int has_freedom (int i, int j)
{
	if (i < 0)
		return -1;
	if (j < 0)
		return -1;
	if (i >= N)
		return -1;
	if (j >= N)
		return -1;
	if (field[i][j] == EMPTY)
		return -1;
	return freedom[root (i, j)];
}

/* Gruppen mit und ohne Freiheiten bestimmen. Dazu gehen wir alle
 * leeren Kreuzungspunkte durch und rufen fuer die benachbarten Gruppen
 * set_freedom auf.
 */
void freedoms (void)
{
	int i, j;
	groups ();
	for (i=0; i<N*N; ++i)
		freedom[i] = 0;
	for (i=0; i<N; ++i) {
		for (j=0; j<N; ++j) {
			if (field[i][j] != EMPTY)
				continue;
			set_freedom (i-1, j);
			set_freedom (i+1, j);
			set_freedom (i, j-1);
			set_freedom (i, j+1);
		}
	}
}

int domove (int i, int j, int col)
{
	if ((i < 0) || (j < 0))
		return 0;
	if ((i >= N) || (j >= N))
		return 0;
	if (field[i][j] != EMPTY)
		return 0;
	if ((col != BLACK) && (col != WHITE))
		return 0;
	field[i][j] = col;
	freedoms ();
	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);
	/* Freiheiten neu berechnen falls Gruppen geloescht wurden. */
	freedoms ();
	if (has_freedom (i,j) != 1) {
		field[i][j] = EMPTY;
		return 0;
	}
	return 1;
}

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 (scanf ("%s", buf) != 1) {
			printf ("Illegal move\n");
			continue;
		}
		if (strcasecmp (buf, "pass") == 0) {
			if (pts[col] > 0) {
				pts[col]--;
			} else {
				break;
			}
			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;
}