Laboratorium programowania zad 11

Zadanie z laboratorium programowania na Informatyce UW.

Zadanie 11 (termin wysylania rozwiazan: 17 kwietnia 2008, godz. 23:59)

(Gra w Zycie)

Gra w Zycie jest symulacja dzialania automatu komorkowego.
Symulacje przeprowadzimy na prostokatnej planszy, ktorej
krawedzie sa ze soba "sklejone", tzn. idac w prawo z pola
znajdujacego sie na prawej krawedzi trafimy na pole krawedzi
lewej (i na odwrot) a idac w gore z pola na gornej krawedzi
trafimy na pole krawedzi dolnej (i na odwrot).

Kazda komorka planszy moze byc w jednym z dwoch stanow:
"zywa" lub "martwa". Na podstawie stanow komorek na planszy
liczymy ich stan w "nastepnej generacji" zgodnie z regulami:

* Jesli zywa komorka ma dwoch lub trzech zywych sasiadow,
  to pozostaje zywa, wpp. umiera.

* Jesli martwa komorka ma trzech zywych sasiadow, to staje sie
  zywa, wpp. pozostaje martwa.

Sasiadami komorki jest 8 komorek stykajacych sie z nia krawedzia
lub wierzcholkiem. Ze wzgledu na "sklejenie" krawedzi planszy,
kazda komorka ma dokladnie 8 sasiadow.

Napisz program, ktory wczyta z wejscia stan planszy i wypisze
na wyjscie stan planszy w nastepnej generacji.

Postac danych:

Na wejsciu programu znajdzie sie pewna liczba wierszy. W wierszach
beda znaki ' ' (spacja) i '#' oznaczajace odpowiednio komorke
martwa i zywa. Dlugosci wszystkich wierszy beda rowne.

Postac wyniku:

Program wypisze na wyjscie stan planszy w generacji nastepnej po
tej, ktora wczytal. Format wyniku ma byc identyczny z formatem
danych. Pozwoli to na przekazanie na wejscie programu jego wlasnego
wyniku i obliczanie w ten sposob kolejnych generacji.

Uwaga:

Nie wolno nakladac ograniczen na liczbe wierszy na wejsciu i dlugosc
kazdego wiersza. Wolno zalozyc, ze caly stan planszy zmiesci sie na
raz w pamieci.

Wskazowka:

Dane trzeba wczytywac znak po znaku, np. za pomoca funkcji getchar().

A oto rozwiązanie:

#include 
#include 
#include 

//Bedziemy przechowywac liczby w liscie dwuwymiarowej
typedef struct plansza_el{     
      int zywa;           
      struct plansza_el * lewy;
	  struct plansza_el * prawy;
	  struct plansza_el * gora;
	  struct plansza_el * dol;
	  
};



char wypisz (struct plansza_el* komorka)
{
	//Generuje znak bedacy oznaczeniem stanu komorki.
	int zywych; //liczba zywych sasiadow
	char stan;
	//gora,dol
	zywych=komorka->gora->zywa;
	zywych+=komorka->dol->zywa;
	//prawa,lewa
	zywych+=komorka->prawy->zywa;
	zywych+=komorka->lewy->zywa;
	//gora skos
	zywych+=komorka->gora->prawy->zywa;
	zywych+=komorka->gora->lewy->zywa;
	//dol skos
	zywych+=komorka->dol->prawy->zywa;
	zywych+=komorka->dol->lewy->zywa;

	
	if(komorka->zywa==1)
	{
		//Jesli zywa komorka ma dwoch lub trzech zywych sasiadow,to pozostaje zywa, wpp. umiera.
		if((zywych==2)||(zywych==3))
		{
			stan='#';
		}
		else
		{
			stan=' ';
		}
		
	}
	else
	{
		//Jesli martwa komorka ma trzech zywych sasiadow, to staje sie zywa, wpp. pozostaje martwa.
		stan=' ';
		
		if(zywych==3)
		{
			stan='#';
		}
	}

	return stan;

}



int main (int argc, char *argv[])
{
	int wynik,przejscie;
	struct plansza_el *start=NULL;
	struct plansza_el *wiersz=NULL;
	struct plansza_el *kolumna=NULL;
	struct plansza_el *teraz=NULL;
	char znak;

	//pierwsza komorka
	start=malloc(sizeof(struct plansza_el));
	start->prawy=NULL;
	start->lewy=NULL;
	start->gora=NULL;
	start->dol=NULL;

	teraz=start;
	wiersz=start;
	kolumna=NULL;
	przejscie=0;
	
	wynik=scanf("%c",&znak);

	if(znak=='#')
	{
		teraz->zywa=1;
	}
	else
	{
		teraz->zywa=0;
	}
	
	wynik=scanf("%c",&znak);
	
	while(wynik!=EOF)
	{
	//no i czytamy
	
		if((znak=='#')||(znak==' '))
		{
	
			if (przejscie==1)
			{
				//pierwszy znak po przejsciu do nowego wiersza.
				//wpierw 'zapinamy' poprzedni wiersz
				teraz->prawy=wiersz;
				wiersz->lewy=teraz;
				//tworzymy nowy wiersz
				wiersz->dol=malloc(sizeof(struct plansza_el));
				wiersz->dol->gora=wiersz;
				//zeby sledzic 'gory'
				kolumna=wiersz;
				wiersz=wiersz->dol;
				teraz=wiersz;
				teraz->lewy=NULL;
				teraz->prawy=NULL;
				teraz->dol=NULL;
				przejscie=0;
				
			}
			else
			{
				if (kolumna!=NULL)
				{
					//przesuwamy w poprzednim wierszu gore
					kolumna=kolumna->prawy;
				}

				teraz->prawy=malloc(sizeof(struct plansza_el));
				//pozycja prawy-lewy:
				teraz->prawy->lewy=teraz;
				teraz=teraz->prawy;
				teraz->prawy=NULL;
				//pozycja gora-dol
				teraz->dol=NULL;
				teraz->gora=kolumna;
				if(kolumna!=NULL)
				{
					//chyba ze pierwsza kolumna
					teraz->gora->dol=teraz;
				}
			}
			
			//wartosc:
			if(znak=='#')
			{
				teraz->zywa=1;
			}
			else
			{
				teraz->zywa=0;
			}
			
		}
		else if(znak=='n')
		{
			przejscie=1;
		}
		//no i mamy zabezpieczenie przed nieprawidlowymi znakami na wejsciu.
		wynik=scanf("%c",&znak);
	}
	
	//Teraz powinno byc wszystko ladnie wczytane. Trzeba jeszcze 'zapiac' ostatni wiersz i 'pozapinac' gory z dolami planszy.
	//ostatni wiersz:
	teraz->prawy=wiersz;
	wiersz->lewy=teraz;
	//gory z dolami:
	
	
	//dla pierwszej kolumny:
	teraz=start;
	teraz->gora=wiersz;
	wiersz->dol=teraz;
	teraz=teraz->prawy;
	wiersz=wiersz->prawy;
	
	while (teraz!=start)
	{
		teraz->gora=wiersz;
		wiersz->dol=teraz;
		teraz=teraz->prawy;
		wiersz=wiersz->prawy;
	}
	
	//Teraz plansza jest zapetlona. czas na wypisywanie.
	
	wiersz=start;
	
	while(wiersz!=NULL)
	{
		teraz=wiersz;
		while(teraz!=NULL)
		{
			printf("%c",wypisz(teraz));
			teraz=teraz->prawy;
			if(teraz==wiersz)
			{
				//warunek stopu
				teraz=NULL;
			}
		}
		
		wiersz=wiersz->dol;
		printf("n");
		if(wiersz==start)
		{
			//warunek stopu
			wiersz=NULL;
		}
	}

	
//A teraz sprzatamy po sobie:
	wiersz=start;
	
	while(wiersz!=NULL)
	{
		teraz=wiersz;
		while(teraz!=NULL)
		{
			kolumna=teraz;
			teraz=teraz->prawy;
			free(kolumna);
			if(teraz==wiersz)
			{
				//warunek stopu
				teraz=NULL;
			}
		}
		kolumna=wiersz;
		wiersz=wiersz->dol;
		free(kolumna);
		if(wiersz==start)
		{
			//warunek stopu
			wiersz=NULL;
		}
	}
	

return 1;
}