| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
AL_05_07 - Linia brzegowa |
W tym zadaniu otrzymasz kilka zeskanowanych map w postaci matrycy, o rozmiarze N na M, znaków '.' i 'X'. Każdy znak reprezentuje kwadrat o boku 1 km, który jest albo wodą '.' albo lądem 'X'.
Twoim zadaniem jest obliczenie całkowitej długości morskiej linii brzegowej wszystkich lądów i wysp przedstawionych na mapie. Morzem jest każda woda, przedstawiona na mapie, która łączy się z dowolnym brzegiem mapy. Brzeg lądu przylegający do krawędzi mapy jest traktowany jako morska linia brzegowa tego lądu. Brzegi jezior i brzegi wysp na jeziorach są pomijane i nie są doliczane do całkowitej sumy.
Wejście
Najpierw liczba map T ≤ 10.
Potem opisy poszczególnych map w następującym formacie:
W pierwszej linii dwie liczby całkowite N i M (1 ≤ N,M ≤ 5000) oznaczające wymiary mapy.
W kolejnych N liniach ciągi znaków 'X' lub '.', każdy o długości M.
Wyjście
Dla każdej mapy, jedna liczba będąca całkowitą sumaryczną długością (w km) morskiej linii brzegowej wszystkich lądów i wysp na mapie. Każda suma w oddzielnej linii.
Przykład
Wejście: 2 5 6 .XXXX. .X.XX. XXX... ....X. ...... 3 3 .X. X.X .X. Wyjście: 20 12
| Dodane przez: | narbej |
| Data dodania: | 2013-04-03 |
| Limit czasu wykonania programu: | 1s-3s |
| Limit długości kodu źródłowego | 50000B |
| Limit pamięci: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Języki programowania: | All except: ASM64 GOSU |
| Pochodzenie: | ALGOLIGA |
ukryj komentarze
|
||||||
|
2013-04-07 07:53:42 narbej
1 1 1 0 To czy to jest to morze to czy to jest to jezioro, to czy to ma to znaczenie? Czy na to odpowiedź jest ta jedna? Ostatnio edytowany: 2013-04-07 08:04:02 |
||||||
|
2013-04-07 07:23:55 Filip £ubniewski
jak nie ma lądu to jezioro nie może powstać (?) czy inaczej? |
||||||
|
2013-04-06 22:06:09 narbej
A co jak jest jezioro, a nie ma lądu? Nie odpowiadaj tylko pomyśl. |
||||||
|
2013-04-06 21:58:51 Filip £ubniewski
Tak, bo przy wypełnianiu powodziowym jeśli istnieje jezioro to nie biore go pod uwagę bo woda morska nawet nie dotrze do tego miejsca. |
||||||
|
2013-04-06 21:54:07 narbej
Brzegi jezior i brzegi wysp na jeziorach są pomijane i nie są doliczane do całkowitej sumy. - wziąłeś to pod uwagę? |
||||||
|
2013-04-06 21:50:25 Filip £ubniewski
dzięki za adresy, niestety moja metoda jest bardzo podobna do tego algorytmu, który podałeś. Też wypełniam "powodziowo" czyli teoretycznie powinienem dotrzeć do każdego punktu na mapie gdzie może się dostać woda. Niestety bo nie mam pojęcia gdzie jest błąd, a wszystkie testy (moje+hodowla reniferów) przechodzi. |
||||||
|
2013-04-06 20:54:22 narbej
To zadanie, jest trochę podobne do zadania: http://pl.spoj.com/problems/AL_03_04/, chociaż tam chodziło o obszar. Możesz przeczytać komentarze pod tamtym zadaniem + wszystko co znajdziesz na forum na temat tamtego zadania + za chwilę znajde jeszcze jeden czy dwa linki to dodam tu [edytując ;-)] Znalazłem, jest to opisane w bardzo żartobliwej formie, ale możesz skorzystać [musisz przebrnąć przez tamte żarty] http://devel.sphere-research.com/phpBB3-spoj-pl/viewtopic.php?f=2&t=2258&sid=3f4f2bc04d1c94147dc7be8fc192563c Ostatnio edytowany: 2013-04-06 20:59:17 |
||||||
|
2013-04-06 20:42:54 Filip £ubniewski
można prosić o jakieś wskazówki? bo wydaje mi się że mój algorytm nie ma żadnych błędów a jednak dostaje WA. |
||||||
|
2013-04-06 18:58:34 narbej
UWAGA! UWAGA! Proszę ;-) Nie róbcie edycji swoich wcześniejszych wiadomości - mogę ich nie zauważyć. Zawsze, jeżeli chcecie żebym je łatwiej zauważył, piszcie nowe. Ostatnio edytowany: 2013-04-06 19:21:04 |
||||||
RSS