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; }