Grupa ID301

JASIO

	Wykonali:
	Rafał Dąbrowski Michał Donigiewicz Tomasz Chmiel

Problemem związanym z tym projektem jest zliczenie drogi jaką przeszedł `Jasio' podróżując po macierzy o dowolnym rozmiarze (niekoniecznie kwadratowej). Istnieje jednak zasada poruszania się. Można mianowicie stąpać tylko po czarnych polach idąc w kierunku odwrotnym do kierunku wskazówek zegara. Trzeba także przejść przez wszystkie te pola aż do końca i wrócić na pozycję wyjściową. Należy także pamiętać, że pola po których chodzimy mogą się powtarzać (kiedy trafimy na ślepą `uliczkę') i nie można tychże powtórzeń doliczyć do sumy przebytych pól.

Zupełnie losową trasę przedstawia poniższy rysunek:

Załóżmy, że następujące wartości odpowiadają kierunkom:

1 -> prawo

-1 -> lewo

2 -> góra

-2 -> dół

Możliwe jest także reprezentowanie kierunków literami, jednakże wtedy skomplikuje się warunek w pętli while. Pozwoliliśmy więc sobie na takie właśnie przedstawienie kierunków.

Jest bardziej `dydaktyczne', łatwiej wyjaśnić zasadę działania oraz wyniki uzyskane w programie są czytelniejsze.

Skoro kierunkami są liczby, to aż się prosi aby skorzystać tu z tablicy liczb całkowitych. Założeniem problemu było, że dostajemy `ścieżkę' po której poruszał się nasz Jasio.

Do zliczania ilości zamalowanych pół nie potrzebna jest nam droga powrotna więc ją pomijamy.

Dostajemy więc tablicę (dla rozważanego rysunku):

-2

-2

1

1

-2

-2

-1

-1

1

1

-2

-2

-2

-1

1

1

Rozwiązaniem tego problemu będzie szukanie sąsiadujących elementów, które w sumie dają wartość zero. Jeśli taką parę znajdziemy - oznacza to, że jedno pole się powtórzyło.

-2

-2

1

1

-2

-2

-1

-1

1

1

-2

-2

-2

-1

1

1

Mamy jedną parę, jednak nie można na tym poprzestać. Mając jedną parę wiemy, że przeszliśmy jedno pole i za chwilę wróciliśmy. A jeśli droga powrotu jest dłuższa niż 1? Wtedy elementy pary będą rozsunięte! Należy więc `rozchodzić' się w obie strony tablicy i porównywać sumy elementów. Jeśli suma jest równa zero - następna para....

-2

-2

1

1

-2

-2

-1

-1

1

1

-2

-2

-2

-1

1

1

...jeśli suma różna od zera - oznacza to, że pojawia się pole jeszcze nie odwiedzone przez naszego bohatera i możemy zaniechać szukania kolejnych przyległych par - dalej jeszcze Jasia nie było, więc nie może się tamtędy wracać!

-2

-2

1

1

-2

-2

-1

-1

1

1

-2

-2

-2

-1

1

1

Przeszukujemy tak tablicę aż do jej końca. Kiedy zostanie on osiągnięty wystarczy zliczone wcześniej pary odjąć od sumy wszystkich pól (rozmiar tablicy) i otrzymujemy liczę pól przez które musiał przejść Jasio.

Oto kod programu obliczającego długość drogi Jasia

#include <stdio.h>

#include <conio.h>

#include <iostream.h>

const int size=10;

int tab[size];

int zlicz();

void wczytaj();

void wypisz();

void main()

{

wczytaj();

wypisz();

};

int zlicz()

{

int p=1, l=0, pary=0, pom=0;

for(p=1;p<=size;p++)

{

pom=p;

while((tab[l]+tab[p])==0 && l>=0 && p<size)

{

pary++;

l--;

p++;

}

l=p;

}

int x=size-pary;

return x;

};

void wczytaj()

{

int kierunek=1;

cout << "Podaj kierunki: '1' -przod '-1' -tyl '2' -gora '-2' -dol " << endl;

for(int i=0;i<size;i++)

{

cin >> kierunek;

tab[i]=kierunek;

}

};

void wypisz()

{

cout << "Jasio naliczyl " << zlicz() << " zamalowanych kwadratow" << endl;

getch();

};

4

---