Runda 9 - Trzy Wieże

30.11.2009 - Damian Rusak
TrudnośćTrudność

 

 

Zawody stałe, runda 9.

Limit czasowy: 15s; Limit pamięciowy: 64 MB;


Trzy Wieże


Król Pewnej Krainy posiada w swym kraju trzy wspaniałe wieże. Jedna jest koloru czerwonego, jedna zielonego, a jeszcze jedna mieni się osobliwym odcieniem błękitu. Cały kraj podzielony jest na powiaty, w modnym stylu kwadratowym - z lotu ptaka wygląda jak prostokąt, złożony z identycznych kwadratowych pól. Na trzech z nich stoją piękne wieże. Król postanowił, że musi stale kontrolować sytuację w państwie, wydał więc rozkaz zbudowania dróg w królewstwie, tak aby mógł podróżować pomiędzy swymi siedzibami. W każdym powiecie król może zbudować drogi - mówimy wtedy, że powiat jest przejezdny. Z wieży można przedostać się do dowolnego powiatu przejezdnego, który sąsiaduje z nią z południa, wschodu, północy lub zachodu. Podobnie król jest w stanie przeprawić się z jednego przejezdnego powiatu do każdego innego, zlokalizowanego tuż za jedną z czterech granic. Oczywiście król jest bardzo skąpy i zażądał, aby jego nadworny informatyk znalazł taki plan zagospodarowania powiatów, aby z każdej wieży można się było przedostać do dwóch pozostałych, i aby jak najmniej powiatów zostało uczynionych przejezdnymi. Pojawił się jednak problem - niektóre powiaty są położone na bardzo trudnym terenie i król nie chce marnować pieniędzy na prowadzenie przez nie dróg. Zatem wytyczone trasy nie mogą przebiegać przez te wyklęte tereny.


Zadanie:

Mając dany plan królewstwa, oblicz, ile co najmniej powiatów trzeba uczynić przejezdnymi, aby  możliwe było przebycie pomiędzy każdymi dwoma wieżami, tak, że wybieramy jedynie powiaty, które nie są położone na trudnym terenie.

Wejście:

Pierwsza linia wejścia zawiera liczbę $ t $ $ \left(1\leq t \leq 10\right) $ - oznaczającą ilość przypadków testowych. Kolejno następuje $ t $ zestawów danych. Każdy zestaw wygląda następująco: W pierwszej linii dwie liczby - $ n $ i $ m $ $ \left(1\leq n,m\leq 1000\right) $, oznaczające wysokość i szerokość planu królewstwa. W kolejnych $ n $ liniach znajduje się po $ m $ znaków, oznaczających kolejne powiaty na kolejnych wysokościach planu. Znak '_' oznacza powiat, po którym można podróżować. Znak 'X' oznacza powiat położony na trudnym terenie. Na wejściu pojawią się też trzy litery - 'A', 'B', 'C' - oznaczające położenie trzech wież. Możesz założyć, że żadne dwie wieże nie są położone bezpośrednio w swoim sąsiedztwie (tj. nie sąsiadują ze sobą na północ, południe, wschód ani zachód). Powiaty, w których znajdują się wieże, możesz uznać za przejezdne. Po każdym zestawie danych następuje pusta linia.

Wyjście:

Dla każdego zestawu danych należy wypisać jedną linię zawierającą słowo "NIE", jeśli nie jest możliwe połączenie wież (np. trudny teren skutecznie odgradza wieże od siebie), bądź w przeciwynym przypadku jedną liczbę - najmniejszą liczbę powiatów, które należy uczynić przejezdnymi, aby możliwa była podróż między każdą parą wież.

 

Przykład:

Wejście:

 

2
6 9
_______XX
_X___X___
_XA___X__
_XX__B___
__X______
________C

6 9
____X__B_
_C_______
____X_XX_
X_X___X__
__X_A____
_________

 

Wyjście:

7 
9


Przykład 1: Najmniej powiatów zostanie uczynionych przyjezdnymi, gdy wybierzemy powiaty zaznaczone brązowymi kołami.

Przykład 2: W tym przykładzie nie opłaca się łaczyć wież "po kolei" - można wybrać mniej powiatów (jak na rysunku).

 

Zapraszamy do dyskusji na temat zadania na forum.

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

PozycjaImię i nazwiskoWynikCzas
1Mateusz Skórski1010:36:44
2Bartek Dudek1014:15:30
3Anna Piekarska1016:35:07
4Janusz Wróbel1057:15:06
5Krzysztof Leszczyński1061:07:34
6Maciej Szeptuch10106:15:48
7Kuba Skudlarski10135:28:09
8Tomasz Wiatrowski101282:30:39
9Maciej Kisiel105102:56:38
10Łukasz Hanuszczak109343:35:45
11Michal Zgliczynski41227:38:33
12Darek Bukowski3133:10:00
4.666665
Twoja ocena: Brak Ocena: 4.7 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com