III Obóz im. A. Kreczmara 2002
|
Zadanie: pod
|
Autor: Marcin Stefaniak
|
dzień pierwszy | 5 sierpnia 2002 |
Plik źródłowy: | pod.??? (np. pas, c, cpp) |
Plik wejściowy: | pod.in |
Plik wyjściowy: | pod.out |
Po prostokątnej planszy o rozmiarach n*m chodzi podróżnik. W jednym ruchu może on przejść z pola na sąsiednie, przyległe krawędzią. Na każdym polu napisana jest liczba całkowita. Gdy podróżnik przechodzi z pola z liczbą a na pole z liczbą b, płaci za to (a+b)*b rubli transferowych. Jeśli jest to liczba ujemna, oznacza to, że podróżnik zyskuje odpowiednią kwotę.
Należy policzyć minimalny koszt podróży z danego pola startu do podanego pola mety.
W pliku pod.in znajduje się opis planszy:
Plik wyjściowy pod.out powinien zawierać jedną liczbę całkowitą, oznaczającą minimalny koszt (w rublach transferowych) przejścia podróżnika od pola startu do pola mety (ewentualny zysk należy zapisać jako liczbę ujemną).
Jeśli tak liczba nie istnieje, czyli w wypadku, gdy podróżnik może dowolnie niskim kosztem odbyć taką trasę, należy wypisać liczbę 0.
Dla pliku wejściowego pod.in:
3 5 2 1 3 1 5 6 5 5 -5 -4 -3 0 2 2 5 -2 -1 0 2
poprawną odpowiedzią jest plik wyjściowy pod.out:
3