Problem 3487: Tura

Trasee de drumeție

Un teren este modelat sub forma unei matrice $N \times M$ , care conține valori întregi. Valorile elementelor reprezintă altitudinea sau adâncimea fiecărui punct față de nivelul mării.

Se intră pe teren din partea de nord (prima linie a matricei) și la fiecare pas se coboară o linie, deplasându-se fie spre sud, fie spre sud-vest, fie spre sud-est. Terenul este părăsit pe partea de sud (ultima linie a matricei).

Cerință

Trebuie să determinăm câte trasee posibile există dacă nu dorim să coborâm sub nivelul mării (adică nu vrem să traversăm elemente cu valori negative), și dorim să traversăm un număr maxim de puncte de șa. Un punct de șa este definit ca un element nenegativ care este strict mai mare decât vecinii săi de nord și sud și strict mai mic decât vecinii săi de vest și est.

Date de intrare

Prima linie a fișierului de intrare tura.in conține un număr întreg $t$ - numărul de teste.
Pentru fiecare test, prima linie conține două numere întregi: $N$ și $M$
Următoarele $N$ linii conțin fiecare câte $M$ valori întregi separate prin spații, reprezentând elementele matricei.

Date de ieșire

Pentru fiecare test, scrieți pe o linie separată în tura.out numărul de trasee posibile.

Restricții și precizări

$0 < t < 9$
$1 < N, M < 19$ ;
Valorile elementelor sunt din intervalul $[−10,10]$ .

Exemplu

tura.in

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

tura.out

Explicație

Punctele de șa în exemplu sunt $(2,2), (4,4), (6,2)$ și $(6,4)$ .

Tura