Polish version    English version  
  Obozy Olimpiady


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
III obóz 2002
IV obóz 2003
V obóz 2004
VI obóz 2005
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
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



Wersja do druku