Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
FR_07_16 - Zawody |
Zawody
Jasiu i jego robot bierze udział w zawodach. Robot może poruszać się po prostokątnej mapie pól w metryce miasto. Startuje z lewego górnego pola do prawego dolnego i wraca z powrotem do punktu startu. Kiedy idzie na południowy-wschód może poruszać się tylko w prawo lub na dół, a w drodze powrotnej może poruszać się wyłącznie w lewo lub do góry. Robot powinien obrać taką drogę, aby odwiedzić jak najwięcej oznaczonych pól z gwiazdkami, przy czym robot nie może przechodzić przez pola oznaczone znakiem x. Po zbadaniu mapy, Jasiu zdaje sobie sprawę, że zadanie nie jest takie proste i trzeba robota odpowiednio zaprogramować. Dlatego uprzejmie prosi Ciebie o pomoc w napisaniu programu, który pozwoli robotowi optymalnie przejść mapę. Mając do dyspozycji mapę 2D, w której zaznaczone są pola z gwiazdkami oraz pola x, po których robot poruszać się nie może, wyznacz maksymalną liczbę pól z gwiazdkami, do których robot może dotrzeć. Pola z gwiazdkami odwiedzone dwa razy liczone są tylko raz.
Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę zestawów danych. W pierwszym wierszu każdego zestawu znajdują się dwie liczby całkowite a, b (2 ≤ a, b ≤ 100) oznaczające długość i szerokość mapy. W kolejnych wierszach opisana jest mapa złożona z b wierszy, każdy wiersz po a znaków o następujących oznaczeniach:
. - chodnik, po którym może poruszać się robot
* - pole z gwiazdką
x - pola, po których robot poruszać się nie może
Należy założyć, że lewe górne pole oraz prawe dolne to pole, w którym nie ma znaku x oraz, że istnieje co najmniej jedna droga łącząca lewe górne pole z polem prawym dolnym.
Wyjście
Na wyjściu, dla każdego przypadku testowego, należy wypisać maksymalną liczbę pól z gwiazdkami, które robot może odwiedzić.
Przykład Wejście 2 8 6 *....... ....**x. ..**..x* .*xxx*.. ...x*.x* *....... 5 5 .*... .xxx. *.*.* .xxx. .*.*. Wyjście 7 5
Dodane przez: | Mariusz Śliwiński |
Data dodania: | 2017-04-07 |
Limit czasu wykonania programu: | 1s-2s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |