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

/* Konstanten fuer die verschiedenen Zustaende des Feldes. Da echte
 * Buchstaben verwendet werden, kann eine ganze Zeile spaeter als
 * ein String ausgegeben werden. Das hoechste Bit (0x80) wird
 * verwendet um anzuzeigen, ob auf dem Feld in der naechsten Runde
 * ein Bakterie sein wird, will dieses Bit ausblenden, dann kann MASK
 * verwendet werden.
 */
#define NOSET	' '     /* Space fuer ein Feld ohne Bakterie */
#define SET	'#'     /* #-character fuer ein Feld mit Bakterie */
#define MASK	0x7f    
#define NEXTSET 0x80

/* Das Feld, Speicher wird dynamisch allokiert, wenn bekannt ist, wie
 * gross das Feld sein soll.
 */
char ** board;
/* Die Groesse des Feldes in i-Richtung (Anzahl Zeilen) und  j-Richtung
 * (Anzahl Spalten). Der default ist 22 Zeilen, 70 Spalten.
 */
int imax = 22, jmax = 70;

int error = 0;  /* Wird true, wenn der Rand des Feldes erreicht wurde. */
int tick = 0;   /* Die aktuelle Runde. */

/* Liefert true zurueck, wenn sich in Zeile i, Spalte j eine Bakterie
 * befindet, sonst ist der Rueckgabewert false. Wenn die Koordinaten
 * ausserhalb des Feldes liegen, wird ebenfalls false zurueckgeliefert.
 */
int getboard (int i, int j)
{
	if ((i < 0) || (i >= imax)) {
		return 0;
	}
	if ((j < 0) || (j >= jmax)) {
		return 0;
	}
	return (board[i][j] & MASK) == SET;
}

/* Aktuelles Feld ausgeben. Wenn diese Funktion aufgerufen wird darf das
 * NEXTSET bit nirgendwo gesetzt sein.
 */
void showboard ()
{
	int i;
	for (i=0; i<imax; ++i) {
		printf ("%s", board[i]);
	}
	printf ("After Tick %d\n", tick);
	if (error)
		printf ("Field boarder reached. Next tick may not be reliable\n");
}

/* Einen "tick" durchfuehren. */
void do_tick ()
{
	int i, j, n, set;
	/* Erster Durchgang: Alle Felder anschauen und NEXTSET bei genau
	 * den Feldern setzen, die in der naechsten Runde eine Bakterie
	 * enthalten.
	 */
	for (i=0; i<imax; ++i) {
		for (j=0; j<jmax; ++j) {
			/* Feld mit einer Bakterie besetzt ? */
			set = getboard (i, j);
			/* Zaehlen der besetzten Nachbarfelder. */
			n = 0;
			n += getboard (i-1, j-1);
			n += getboard (i-1, j  );
			n += getboard (i-1, j+1);
			n += getboard (i  , j-1);
			n += getboard (i  , j+1);
			n += getboard (i+1, j-1);
			n += getboard (i+1, j  );
			n += getboard (i+1, j+1);
			switch (n) {
			case 0: case 1: case 4: case 5:
			case 6: case 7: case 8:
				/* In diesen Faellen stirbt eine ev.
				 * vorhandene Bakterie sicher, NEXTSET
				 * wird also nicht gesetzt.
				 */
				break;
			case 2:
				/* Falls auf dem Feld vorher eine Bakterie
				 * war ueberlebt sie, in diesem Fall muss
				 * also NEXTSET gesetzt werden.
				 */
				if (set)
					board[i][j] |= NEXTSET;
				break;
			case 3:
				/* Falls hier eine Bakterie war, ueberlebt
				 * sie, falls hier keine war entsteht eine
				 * neue, NEXTSET muss also gesetzt werden.
				 */
				board[i][j] |= NEXTSET;
				/* Falls der Rand des Feldes erreicht wurde,
				 * sind zukuenftige Schritte nicht mehr
				 * sicher richtig, es wird also error auf 1
				 * gesetzt.
				 */
				if ((i == 0) || (i == imax-1) ||
				    (j == 0) || (j == jmax-1))
					error = 1;
				break;
			}
		}
	}
	/* Zweiter Durchgang: Alle Felder, bei denen NEXTSET gesetzt is
	 * werden mit einer Bakterie besetzt, alle anderen werden leer.
	 * Dabei wird auch das NEXTSET flag ueerall geloescht.
	 */
	for (i=0; i<imax; ++i)
		for (j=0; j < jmax; ++j)
			board[i][j] = (board[i][j] & NEXTSET) ? SET : NOSET;
}

char * progname;

void usage ()
{
	printf ("usage: %s [-i int] [-j int] startfile\n", progname);
	exit (1);
}

/* Hauptprogramm. */
int main (int argc, char * argv[])
{
	char * line;
	FILE * input = NULL;
	int initimax, initjmax, i, j, si, sj, ch;
	/* Argumentverarbeitung. */
	progname = argv[0];
	while (1) {
		ch = getopt (argc, argv, "i:j:");
		if (ch == EOF)
			break;
		switch (ch) {
		case 'i':
			if (sscanf (optarg, "%d", &imax) != 1)
				usage ();
			break;
		case 'j':
			if (sscanf (optarg, "%d", &jmax) != 1)
				usage ();
			break;
		default:
			usage ();	
		}
	}
	if (optind + 1 != argc)
		usage ();
	/* Oeffnen und parsen der Eingabedatei. */
	input = fopen (argv[optind], "r");
	if (!input)
		usage ();
	/* Groesse der Anfangskonfiguration einlesen. */
	fscanf (input, "%d %d ", &initimax, &initjmax);
	assert ((initimax > 0) && (imax >= 2+initimax));
	assert ((initjmax > 0) && (jmax >= 2+initjmax));
	/* Speicher um eine Zeile aus der Anfangskonfiguration
	 * einlesen zu koennen.
	 */
	line = calloc (initjmax+10, sizeof (char));
	/* Speicher fuer das Spielfeld. */
	board = calloc (imax, sizeof (char *));
	for (i=0; i<imax; ++i) {
		board[i] = calloc (jmax+2, sizeof (char));
		for (j=0; j<jmax; ++j)
			board[i][j] = NOSET;
		board[i][j++] = '\n';
		board[i][j] = '\0';
	}
	/* Koordinaten, an denen die Anfangskonfiguration platziert wird. */
	si = (imax - initimax) / 2;
	sj = (jmax - initjmax) / 2;
	/* Anfangskonfiguration einlesen und in das Feld eintragen. */
	for (i=0; i<initimax; ++i) {
		fgets (line, initjmax+10, input);
		for (j=0; (j<initjmax) && (line[j] != '\n'); ++j)
			switch (line[j]) {
			case SET:
				board[si+i][sj+j] = SET;
				break;
			case NOSET:
				break;
			default:
				assert (0);
			}
	}
	free (line);
	/* Feld anzeigen und einen Tick durchfuehren, bis durch die
	 * Eingabe von q abgebrochen wird.
	 */
	while (1) {
		char line[10];
		showboard ();
		fgets (line, 10, stdin);
		if (line[0] == 'q')
			break;
		do_tick ();
		tick++;
	}
	return 0;
}