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.|

MWP3_3A - Algorytmiczne pola

Algorytmiczne pola to niezwykle ciekawa gra. Plansza, na której jest ona rozgrywana składa się z n wierszy i m kolumn wypełnionych liczbami całkowitymi. W każdej komórce planszy umieszczona jest jedna liczba całkowita. Gra polega na przejściu od pola, w którym znajduje się najmniejsza liczba do pola zawierającego największą liczbę. Wartości znajdujące się w tych polach są unikalne. Wędrując po planszy dodajemy do siebie liczby umieszczone w odwiedzanych komórkach. Ruchy możliwe do wykonania z danej komórki zależą od tego jaka liczba się w niej znajduje:

  1. Z pola, w którym znajduje się liczba pierwsza możemy przejść na pola bezpośrednio sąsiadujące z nim po skosach. Np. z pola 4 4 możemy przejść na pole: 3 5, 5 5, 5 3 albo 3 3.
  2. Z pola, w którym nie znajduje się liczba pierwsza możemy przejść na pola bezpośrednio sąsiadujące z nim w pionie i w poziomie. Np. z pola 4 4 możemy przejść na pole: 4 5, 5 4, 4 3 albo 3 4.

Dodatkowym celem gry jest takie przejście od pola początkowego do końcowego (o ile w ogóle jest to możliwe), aby suma wartości odwiedzonych pól była jak najmniejsza. Twoim zadaniem jest obliczenie i wypisanie dla wczytanej planszy kosztu jej optymalnego przejścia albo wypisanie słowa "NIE" jeżeli przejście nie jest możliwe.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba naturalna Z (1 ≤ Z ≤ 100) określająca ilość zestawów danych. W kolejnych liniach znajdują się zestawy danych.

W pierwszej linii każdego zestawu danych znajdują się dwie liczby całkowite n oraz m (2 ≤ n, m ≤ 20) określające odpowiednio ilość wierszy i kolumn na planszy. W kolejnych n liniach znajduje się po m liczb całkowitych. Liczba j-ta w i-tym wierszu aij (0 ≤ aij ≤ 106) określa wartość pola w i-tym wierszu i j-tej kolumnie.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać jedną liczbę całkowitą określającą koszt optymalnego przejścia planszy zgodnie z zasadami gry albo słowo "NIE" jeżeli takie przejście nie jest możliwe.

Przykład

Wejście:

3
2 2
1 2
4 3
3 3
2 4 3
4 3 4
3 4 5
3 3
2 6 3
3 3 3
3 3 3

Wyjście:

5
10
NIE

Dodane przez:Maciej Boniecki
Data dodania:2010-12-17
Limit czasu wykonania programu:0.100s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:III Mistrzostwa WWSI w Programowaniu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.