Laboratorium programowania zad 4

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.