Runda 8 [Basic] - Nurek

24.01.2011 - Damian Rusak
Trudność

 

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.
PozycjaImię i nazwiskoWynikCzasNurek
1Kamil Dębowski1000:15:4210
2Maciej Kisiel1004:45:4410
3Jakub Kołodziej1007:18:5410
4Wojciech Janczewski1009:18:2410
5Łukasz Hryniuk1010:19:3410
6Bartek Dudek1062:50:4810
7Mateusz Wasylkiewicz1084:51:0610
8Przemysław Derengowski10108:56:3010
9Arek Wróbel10160:31:2510
10Jakub Sutowicz10180:00:1910
11Piotr Bejda10460:43:1810
12Damian Straszak10610:50:3810
13Witold Długosz101278:56:1010
14Maciej Jonasz905:47:119
15Krzysztof Pszeniczny906:06:379
16Paweł Michalak908:16:309
17Michał Zezyk5473:05:165
18Krzysztof Cirocki5634:27:245
19Tymon Czarnota51643:00:005
20Adam Czapliński1171:40:121
5
Twoja ocena: Brak Ocena: 5 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com