Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_21_07 - Bombowa Ucieczka

Ed gra w grę pt. Bombowa Ucieczka. W grze tej znajdujesz się na prostokątnej mapie o wymiarach n×m na polu (a,b) i musisz dostać się (uciec) na pole (c,d). Wszystko byłoby fajnie gdyby nie to, że niektóre pola wybuchają! Po polu które wybuchło nie można chodzić, a wejście na pole które w tej turze wybuchnie jest samobójstwem i powoduje przegraną. W jednej turze można się przemieścić jedynie na pole znajdujące się:

  • powyżej
  • poniżej
  • z lewej strony
  • z prawej strony

Ed właśnie po wielu godzinach zmagania się z grą przeszedł ostatni jej poziom. Ed zastanawia się teraz, ilu minimalnie polom z danej mapy wystarczyłoby zmienić licznik do wybuchu na 0, aby uniemożliwić jej przejście? Żeby nie było za łatwo, licznik musi zostać niezmieniony dla pola startowego i pola końcowego.

Wejście

W pierwszej linii liczba testów t ∈ [1;5].

Każdy test wygląda następująco:

W pierwszej linii dwie liczby n i m (n×m ∈ [2;100]) określające rozmiar mapy.

W każdym z kolejnych n wierszy znajduje się m liczb. Liczba xij ∈ [-1;10001] znajdująca się w i-tym wierszu i j-tej kolumnie oznacza, że pole znajdujące się w tej samej kolumnie i wierszu wybuchnie po xij turach. Jeśli xij jest równe -1, to pole nigdy nie wybuchnie. Pole startowe i końcowe zawsze ma ustawiony licznik na -1.

W następnej linii wejścia znajdują się cztery liczby a ∈ [1;m], b ∈ [1;n], c ∈ [1;m], d ∈ [1;n] oznaczające, że pole startowe znajduje się w a-tej kolumnie i b-tym wierszy, zaś docelowe w c-tej kolumnie i d-tym wierszu.

Wyjście

Dla każdego testu należy wypisać minimalną liczbę pól jakie należy usunąć, aby uniemożliwić przejście mapy. (Mapa może być niemożliwa do przejścia od początku). Jeśli nie da się tak usunąć niektórych pól, żeby uniemożliwić przejście mapy wypisz -1.

Przykład

Wejście:

1
3 3
-1 3 3
2 4 4
-1 5 -1
1 1 3 3

Wyjście:

2

Dodane przez:Bartek
Data dodania:2015-03-06
Limit czasu wykonania programu:1s-5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
Pochodzenie:ALGOLIGA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.