Łączenie Obszarów

Cel

Mieszkańcy wysp postanowili utworzyć największą możliwą wyspę w okolicy poprzez zbudowanie pomiędzy nimi mostu. Niestety nie stać ich na bardzo długi most. Znajdź pole, które połączy dwie wyspy w możliwie największą na podstawie podanego planu okolicy. Most może łączyć sąsiadujące pola, ale nie po skosie. Czyli tylko na prawo, lewo, górę lub dół (dowolny zestaw co najmniej z dwóch podanych). Poprzez cyfry 0 została oznaczona woda otaczająca wyspy, a przez cyfrę 1 obszar wysp. Mapa okolicy jest prostokątna.

Na wejście dane są kolejno szerokość szer oraz wysokość wys planu okolicy, a następnie zostaje podane plan okolicy złożony z wartości 0 oraz 1. Zakładamy, że istnieją chociaż dwie wyspy.

Analiza Zadania

Przypuśćmy, że została podana następująca mapa:

Przykładowa mapa

W celu zlokalizowania wszystkich obszarów należy znaleźć jedynkę, a następnie spisać wszystkie sąsiadujące z tą jedynką jedynki itd. Najprostszy sposób polega na przypisaniu polom nowej wartości identyfikującej. Wiedząc, że 0 oraz 1 są to zarezerwowane wartości to należy zacząć numerować obszary od 2. Po nadaniu każdemu obszarowi liczby otrzymamy następującą mapę okolicy:

Przykładowa mapa z zaznaczonymi wyspami

Kolejne etap polega na policzeniu z ilu pól składa się każdy z obszarów. Przyda się to podczas wyznaczania pola do wyboru. Most może powstać jedynie tam, gdzie wokół pola z wartością 0 znajdują się chociaż dwie, różne grupy. W tym przypadku największą wyspę możnaby utworzyć łącząc grupę 2 i 4, ale niestety most może mieć maksymalną długość 1, więc nie da rady ich połączyć.

Największą wyspę można utworzyć poprzez ustawienie mostu pomiędzy grupą 3 i 4. Istnieją trzy możliwe punkty. Wszystkie znajdują się w kolumnie o indeksie 5.

Implementacja

Sąsiedzi

Funkcja PodajSasiadow() zwraca zbiór wszystkich sąsiadów wokół danego pola o współrzędnych (x, y). Podczas pisania tej funkcji należy pamiętać, że nie każde pole ma wszystkich możliwych sąsiadów.

1. set<int> PodajSasiadow(int szer, int wys, int ** tab, int x, int y) {
2.   set<int> sasiedzi;
3.   if (x > 0) sasiedzi.insert(tab[y][x - 1]);
4.   if (x + 1 < szer) sasiedzi.insert(tab[y][x + 1]);
5.   if (y > 0)    sasiedzi.insert(tab[y - 1][x]);
6.   if (y + 1 < wys ) sasiedzi.insert(tab[y + 1][x]);
7.   return sasiedzi;
8. }

Rozwiązanie

Jeśli pole ma przypisaną wartość 1 to znaczy, że jest ono obszarem wyspy. W przeciwnym razie nie należy przypisywać żadnego nowego numeru obszaru. Jeśli pole nie sąsiaduje z żadnym polem z wartością większą od 1 to przypisz nową wartość. Nadanie nowego numeru obszaru oznacza również dodanie nowego licznika. W przeciwnym razie należy przypisać sąsiadujący numer obszaru oraz zwiększyć odpowiedni licznik.

1. pair<int, int> WskazPunkt(int szer, int wys, int ** tab) {
2.   int numer = 2;
3.   vector<int> licznik;
4.   licznik.push_back(0);
5.   licznik.push_back(0);
6.   for (int y = 0; y < wys; y++) {
7.     for (int x = 0; x < szer; x++) {
8.       if (tab[y][x] == 0) {
9.         continue;
10.       }
11.       set<int> sasiedzi = PodajSasiadow(szer, wys, tab, x, y);
12.       int maksimum = *--sasiedzi.end();
13.       if (maksimum == 1) {
14.         tab[y][x] = numer++;
15.         licznik.push_back(1);
16.       } else if (maksimum > 1) {
17.         tab[y][x] = maksimum;
18.         licznik[maksimum]++;
19.       }
20.     }
21.   }

Druga część polega na pobraniu sąsiadujacych pól dla każdego pola wody (tj. o wartości 0), a następnie zsumowaniu liczników każdej z grup. Ważnym aspektem jest to, aby lista sąsiadów była zbiorem (czyli lista wartości bez powtórzeń), ponieważ inaczej jeden obszar mógłby zostać zsumowany podwójnie.

1.   int sumaMax = 0;
2.   pair<int, int> punkt = make_pair(0, 0);
3.   for (int y = 0; y < wys; y++) {
4.     for (int x = 0; x < szer; x++) {
5.       if (tab[y][x] == 0) {
6.         set<int> sasiedzi = PodajSasiadow(szer, wys, tab, x, y);
7.         int suma = 0;
8.         for each (int grupa in sasiedzi)
9.         {
10.           suma += licznik[grupa];
11.         }
12.         if (suma > sumaMax) {
13.           sumaMax = suma;
14.           punkt = make_pair(x, y);
15.         }
16.       }
17.     }
18.   }
19.   return punkt;
20. }

Znalezienie każdej kolejne, większej sumy wymaga aktualizacji aktualnego maksimum oraz znalezionego punktu.

Testowanie funkcji

W celu przetestowania napisanego kodu można skorzystać z poniższego fragmentu programu:

1. int main() {
2.   int szer, wys;
3.   cout << "Podaj rozmiar szer x wys:\n";
4.   cin >> szer >> wys;
5.   int ** tab = new int*[wys];
6.   for (int i = 0; i < wys; i++) {
7.     tab[i] = new int[szer];
8.   }
9.   cout << "Podaj tablice:\n";
10.   for (int y = 0; y < wys; y++) {
11.     for (int x = 0; x < szer; x++) {
12.       cin >> tab[y][x];
13.     }
14.   }
16.   pair<int, int> punkt = WskazPunkt(szer, wys, tab);
18.   cout << "Nalezy wybrac punkt (x, y) = (";
19.   cout << punkt.first << ", " << punkt.second << ")";
21.   system("pause");
22.   return 0;
23. }

Przykładow dane do schematu podanego wyżej to:

1. 8 4
2. 1 1 1 0 1 0 1 1
3. 1 1 1 0 1 0 1 1
4. 0 0 0 0 1 0 1 1
5. 1 1 1 0 1 0 1 1

• Kod źródłowy Implementacja