Runda 8 [Basic] - Nurek

24.01.2011 - Damian Rusak

Zadanie Tygodnia

Runda 8; kategoria Basic

Limit czasowy: 1s; Limit pamięciowy: 16MB

Nurek

Na dnie Oceanu Kratowego odnaleziono wrak okrętu zatopionego przed wiekami w czasie wojen morskich. Ekspedycja nurków wyrusza, aby wśród zdradliwych piasków szukać dawno zapomnianych skarbów.

Nurkom udało się sporządzić mapę dna morskiego za pomocą radarów i zamierzają wypuścić linę w głebiny oceanu, aby za jej pomocą sprawnie dostać się na dno. Oznaczyli na mapie kilka miejsc, w których chcą poszukiwać skarbu. Ponieważ lokalne wody są bardzo zdradliwe, postanowili, że na miejsce spuszczenia liny wybiorą pozycję, z której w sumie najszybciej uda im się odwiedzić wszystkie lokacje oznaczone na mapie.

Każda pojedyńcza wyprawa w poszukiwaniu skarbu wymaga wielu przygotowań i koncentracji - badanie dna nie jest prostą sprawą. Nurkowie ustalili więc, że za kryterium oceny pozycji opuszczenia liny wybiorą sumę jego odległości do wszystkich lokacji oznaczonych na mapie. Jeśli współrzędne lokacji to $(x_{1}, y_{1})$ a miejsce opuszczenia liny to $(x_{2}, y_{2})$ to odległość między nimi określimy przez $\left|x_{1}-x_{2}\right|+\left|y_{1}-y_{2}\right|$ (gdzie $\left|x\right|$ to wartość bezwzględna z liczby $x$ ).

Mając daną mapę dna morskiego, odpowiedz na pytanie o najlepsze miejsce na opuszczenie liny.

Wejście:

Pierwsza linia wejścia zawiera dwie liczby całkowite $n$ i $m$ ( $1 \leq n,m \leq 1000$ ) oznaczające wysokość i szerokość fragmentu dna przedstawionego na mapie. W kolejnych $n$ liniach (dla $i = 1,2,...,n$ ) znajdują się ciągi $m$ znaków $b_{i,1}$ , $b_{i,2}$ , ..., $b_{i,m}$ . Jeśli $b_{i,j}$ to znak '#' to pole o współrzędnych $(i,j)$ jest puste, jeśli zaś $b_{i,j}$ to znak 'X' to pole to jest możliwą lokacją skarbu. Możesz założyć, że na mapie pojawi się chociaż jeden znak 'X'.

Wyjście:

Wyjście powinno zawierać dwie liczby całkowite $(x,y)$ - współrzędne pola, na które najlepiej opuścić linę. Jeśli takich pól jest kilka, wypisz to o najmniejszej współrzędnej $x$ - jeśli takich wciąż jest więcej niż jedno, spośród nich wybierz pole o najmniejszej współrzędnej $y$ .

Przykład:

Wejście:

5 6

######

#X##X#

######

###X##

######

Wyjście:

2 4

Wyjaśnienie: Skarby znajdują się na pozycjach $(2,2)$ , $(2,5)$ oraz $(4,4)$ . Suma odległości tych lokacji od $(2,4)$ to 2+1+2 = 5 i jest to minimalna suma możliwa do uzyskania.

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

Pozycja	Imię i nazwisko	Wynik	Czas	Nurek
1	Kamil Dębowski	10	00:15:42	10
2	Maciej Kisiel	10	04:45:44	10
3	Jakub Kołodziej	10	07:18:54	10
4	Wojciech Janczewski	10	09:18:24	10
5	Łukasz Hryniuk	10	10:19:34	10
6	Bartek Dudek	10	62:50:48	10
7	Mateusz Wasylkiewicz	10	84:51:06	10
8	Przemysław Derengowski	10	108:56:30	10
9	Arek Wróbel	10	160:31:25	10
10	Jakub Sutowicz	10	180:00:19	10
11	Piotr Bejda	10	460:43:18	10
12	Damian Straszak	10	610:50:38	10
13	Witold Długosz	10	1278:56:10	10
14	Maciej Jonasz	9	05:47:11	9
15	Krzysztof Pszeniczny	9	06:06:37	9
16	Paweł Michalak	9	08:16:30	9
17	Michał Zezyk	5	473:05:16	5
18	Krzysztof Cirocki	5	634:27:24	5
19	Tymon Czarnota	5	1643:00:00	5
20	Adam Czapliński	1	171:40:12	1