Zadanie 4 z laboratorium programowania na Informatyce UW.
Zadanie 4 (termin wysylania rozwiazan: 8 II 2008, godz. 23:59) (Samotnik) Gra logiczna o nazwie Samotnik jest rozgrywana przez jedna osobe na planszy, ktorej czesc pol zajmuja pionki. Pojedynczy ruch polega na przeskoczeniu pionkiem pionka znajdujacego sie na jednym z czterech sasiednich pol, zdjeciu przeskoczonego pionka z planszy i umieszczeniu pionka, ktory przeskoczyl, bezposrednio za polem przeskoczonym (wczesniej musi byc ono puste). Np. ze stanu (kropka oznacza puste pole, gwiazdka to pionek): **. przejdziemy do: ..* ze stanu: .** przejdziemy do: *.. ze stanu: . * * przejdziemy do: * . . ze stanu: * * . przejdziemy do: . . * Napisz program, ktory dla zadanego stanu planszy S i wartosci n wypisze wszystkie stany, z ktorych po n ruchach dojdziemy do stanu S. Postac danych: Program jest wywolywany z jednym argumentem bedacym nieujemna liczba calkowita, a ze standardowego wejscia wczytuje stan planszy. Reprezentacja stanu sklada sie z siedmiu wierszy, kazdy po siedem znakow. Znak kropki '.' reprezentuje puste pole planszy, znak gwiazdki '*' reprezentuje pionka a znak spacji reprezentuje miejsce poza plansza - tam pionek nigdy znalezc sie nie moze. Np. ciag znakow: *** *** ******* ***.*** ******* *** *** jest zapisem stanu poczatkowego Samotnika w jego klasycznej wersji. Postac wyniku: Program wypisuje na wyjscie wszystkie stany planszy, z ktorych po n ruchach mozna osiagnac stan zadany na wejsciu. Kazdy stan wypisujemy w takim formacie, w jakim byly dane na wejsciu (siedem wierszy po siedem znakow). Dodatkowo, po kazdym stanie planszy wypisujemy jeden pusty wiersz. Np. dla danych postaci: ... ... ....... ...*... ....... ... ... program wywolany poleceniem: ./rozwiazanie 1 < dane powinien wypisac: ... ... ....... ....... ...*... .*. ... ... .*. ...*... ....... ....... ... ... ... ... ....... ....**. ....... ... ... ... ... ....... .**.... ....... ... ... Dla tych samych danych, program wywolany z argumentem 3 powinien wypisac, miedzy innymi, stan: ... ... ...*... .**.... ....... .*. ... Pelny wynik programu wywolanego z argumentem 3 jest zalacznikiem do tresci zadania. (Uwaga: Kolejnosc stanow wypisywanych na wyjscie nie musi byc taka, jak w tym przykladzie, ale gdyby udalo sie Panstwu ja zachowac, ulatwiloby mi to sprawdzanie rozwiazan.) Mozna zalozyc, ze dane na wejsciu programu, oraz argument wywolania, beda poprawne. Wskazowka 1: Zacznij od rozwiazania problemu cofniecia stanu planszy o jeden, czyli do stanu bezposrednio poprzedzajacego zadany. Nastepnie zastanow sie, jak zastosowac rekurencje do rozwiazania problemu w wersji pelnej. Wskazowka 2: Liczbe argumentow, z ktorymi wywolano program, mozemy poznac wywolujac funkcje ParamCount. Funcja ParamStr(i) zwroci nam i-ty argument wywolania programu w postaci wartosci typu string. Wartosc liczbowa reprezentowana przez wartosc typu string mozemy obliczyc samodzielnie, lub skorzystac z procedury Val. Wywolanie Val(s,x,w) umiesci na zmiennej x typu integer wartosc liczby, ktorej ciag cyfr znajduje sie na zmiennej s typu string. Gdyby postac s byla bledna, na zmiennej w typu word znajdzie sie kod bledu.
A oto rozwiązanie:
program zad3; //Program napisany na zajęcia z Laboratorium Języka Pascal i C. Zadania nr 4. type //plansza plan=array [1..7,1..7] of char; var start:plan; argumentow,iteracji,i,j,blad:integer; parametr,wiersz:string; procedure wypisz(plansza:plan); //Jak nietrudno sie domyslic, procedura wypisuje plansze var i,j:integer; begin for i:=1 to 7 do begin for j:=1 to 7 do begin write(plansza[i,j]); end; writeln(); end; writeln(); end; procedure ruch(plansza:plan;iteracja:integer); //Rekurencyjna procedura. Wykonuje ruchy az iteracja spadnie do 0 var i,j:integer; plansza2:plan; begin //Doszlismy do odpowiedniej liczby ruchow if (iteracja=0) then begin wypisz(plansza); end else begin iteracja:=iteracja-1; //Idziemy po planszy. Dla kazdego pionka zaklada ze znalazl sie tam w wyniku ruchu for i:=1 to 7 do begin for j:=1 to 7 do begin //Mamy pionek if (plansza[i,j]='*') then begin //No i teraz zakladamy ze pionek znalazl sie tam w wyniku: //skok z dolu if ((i2) AND (plansza[i-1,j]='.') AND (plansza[i-2,j]='.')) then begin plansza2:=plansza; plansza2[i,j]:='.'; plansza2[i-1,j]:='*'; plansza2[i-2,j]:='*'; ruch(plansza2,iteracja); end; //skok z prawej if ((j2) AND (plansza[i,j-1]='.') AND (plansza[i,j-2]='.')) then begin plansza2:=plansza; plansza2[i,j]:='.'; plansza2[i,j-1]:='*'; plansza2[i,j-2]:='*'; ruch(plansza2,iteracja); end; end end end end end; begin //Przechwutujemy liczbe argumentow argumentow:=ParamCount(); if (argumentow=1) then begin //Czytamy parametr parametr:=ParamStr(1); Val(parametr,iteracji,blad); //Wczytujemy wejscie for i:=1 to 7 do begin readln(wiersz); for j:=1 to 7 do begin start[i,j]:=wiersz[j]; end end; //wczytane. //Wywyolujemy ruch(start,iteracji); end end.