Łą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. static HashSet<int> PodajSasiadow(int[,] tab, int x, int y) {
2.   int wys = tab.GetLength(0);
3.   int szer = tab.GetLength(1);
5.   HashSet<int> sasiedzi = new HashSet<int>();
6.   if (x > 0) sasiedzi.Add(tab[y, x - 1]);
7.   if (x + 1 < szer) sasiedzi.Add(tab[y, x + 1]);
8.   if (y > 0) sasiedzi.Add(tab[y - 1, x]);
9.   if (y + 1 < wys) sasiedzi.Add(tab[y + 1, x]);
10.   return sasiedzi;
11. }

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. static Punkt WskazPunkt(int[,] tab) {
2.   int wys = tab.GetLength(0);
3.   int szer = tab.GetLength(1);
5.   int numer = 2;
6.   List<int> licznik = new List<int>();
7.   licznik.Add(0);
8.   licznik.Add(0);
9.   for (int y = 0; y < wys; y++) {
10.     for (int x = 0; x < szer; x++) {
11.       if (tab[y, x] == 0) {
12.         continue;
13.       }
14.       HashSet<int> sasiedzi = PodajSasiadow(tab, x, y);
15.       int maksimum = sasiedzi.Max();
16.       if (maksimum == 1) {
17.         tab[y, x] = numer++;
18.         licznik.Add(1);
19.       }
20.       else if (maksimum > 1) {
21.         tab[y, x] = maksimum;
22.         licznik[maksimum]++;
23.       }
24.     }
25.   }

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.   Punkt punkt = new Punkt(-1, -1);
3.   for (int y = 0; y < wys; y++) {
4.     for (int x = 0; x < szer; x++) {
5.       if (tab[y, x] == 0) {
6.         HashSet<int> sasiedzi = PodajSasiadow(tab, x, y);
7.         int suma = 0;
8.         foreach (int grupa in sasiedzi) {
9.           suma += licznik[grupa];
10.         }
11.         if (suma > sumaMax) {
12.           sumaMax = suma;
13.           punkt = new Punkt(x, y);
14.         }
15.       }
16.     }
17.   }
18.   return punkt;
19. }

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. static void Main(string[] args) {
2.   Console.WriteLine("Podaj rozmiar szer x wys:");
3.   string[] dane = Console.ReadLine().Split(' ');
4.   int szer = Convert.ToInt32(dane[0]);
5.   int wys = Convert.ToInt32(dane[1]);
6.   Console.WriteLine("Podaj tablice:");
7.   int[,] tab = new int[wys, szer];
8.   for (int y = 0; y < wys; y++) {
9.     dane = Console.ReadLine().Split(' ');
10.     for (int x = 0; x < szer; x++) {
11.       tab[y, x] = Convert.ToInt32(dane[x]);
12.     }
13.   }
15.   Punkt punkt = WskazPunkt(tab);
17.   Console.Write("Należy wybrać punkt (x, y) = ");
18.   Console.Write("({0}, {1})", punkt.X, punkt.Y);
20.   Console.ReadKey();
21. }

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