Łą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. def PodajSasiadow(tab, x, y):
2.   sasiedzi = set()
3.   if (x > 0): sasiedzi.add(tab[y][x - 1])
4.   if (x + 1 < szer): sasiedzi.add(tab[y][x + 1])
5.   if (y > 0): sasiedzi.add(tab[y - 1][x])
6.   if (y + 1 < wys): sasiedzi.add(tab[y + 1][x])
7.   return sasiedzi

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. def WskazPunkt(tab):
2.   numer = 2
3.   licznik = [0, 0]
4.   for y in range(len(tab)):
5.     for x in range(len(tab[0])):
6.       if (tab[y][x] == 0):
7.         continue
8.       sasiedzi = PodajSasiadow(tab, x, y)
9.       maksimum = max(sasiedzi)
10.       if (maksimum == 1):
11.         tab[y][x] = numer
12.         numer += 1
13.         licznik.append(1)
14.       elif (maksimum > 1):
15.         tab[y][x] = maksimum
16.         licznik[maksimum]+= 1

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.   sumaMax = 0
2.   punkt = (-1, -1)
3.   for y in range(len(tab)):
4.     for x in range(len(tab[0])):
5.       if (tab[y][x] == 0):
6.         sasiedzi = PodajSasiadow(tab, x, y)
7.         suma = 0
8.         for grupa in sasiedzi:
9.           suma += licznik[grupa]
10.         if (suma > sumaMax):
11.           sumaMax = suma;
12.           punkt = (x, y)
13.   return punkt

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. print("Podaj rozmiar szer x wys:");
2. [szer, wys] = [int(x) for x in input().split()]
3. print("Podaj tablice:");
4. tab = []
5. for y in range(wys):
6.   tabPom = [int(x) for x in input().split()]
7.   tab.append(tabPom)
9. punkt = WskazPunkt(tab)
11. print("Należy wybrać punkt (x, y) = ", end = "")
12. print("(" + str(punkt[0]) + ", " + str(punkt[1]) + ")")

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