Polish version    English version  
  Olympic camps


 News
 About Olympic
 History of OI
 OI books
 National team
 Olympic camps
III camp 2002
IV camp 2003
V camp 2005
VI camp 2005
 Photo gallery
 Links
 SIO
 MAIN
This document is not available in English version.

III Obóz im. A. Kreczmara 2002

Zadanie: pod
Autor: Marcin Stefaniak
Podróżnik

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.

Wejście

W pliku pod.in znajduje się opis planszy:

  • W pierwszym wierszu znajdują się liczby całkowite n, m, xs, ys, xm, ym (1 <= n,m <= 200; 1 <= xs,xm <= n; 1 <= ys,ym <= m) oznaczające odpowiednio: liczbę kolumn i wierszy planszy, numer kolumny i wiersza pola startowego, numer kolumny i wiersza pola mety.
  • W każdym z kolejnych m wierszy znajduje się ciąg n liczb całkowitych ai,j rozdzielonych pojedynczymi odstępami (-100 <= ai,j <= 100). Są to liczby przypisane polom.

Wyjście

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.

Przykład

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



Print friendly version