# UVA 10825 - Longest Run on a Snowboard

*算法： Greedy、BruteForce、DP*

### 題目：
給你一個$R \times C$的矩陣每個點代表一個高度 $H_i$ ，找到一條高度嚴格遞減的最長路徑，路徑只能上下左右走且不能走出矩陣外。

[原題目](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1226)

### 輸入：
$T$ 筆測資
每筆測資的第一行有一個不含空格的字串，$R,C$ 代表行、列數，以空格隔開
接著R行有C個整數$Hi$

$N \leq 15$
$R,C \leq 100$
$0 \leq H_i \leq 100$

### 輸出：
一開始輸入的字串+": "+最長路徑長

### 解法：

*測資很小直接枚舉也行，~~但因為我DP很爛所以這裡用DP解。~~*

上下左右走，感覺能BFS但其實用DFS會更好，因為BFS比較適合求最短路

DP( i , j ) 代表( i , j )這個點能走的最長路徑長。

可得
$DP( i , j ) = max( DP( i , j ) , 下一個點的最長路徑長+1 )$

這樣能順便處理下一個點的最長路徑長，不用再跑一次。

處理邊界的部分，矩陣外面的高度全都INF，
還沒處理過的點設成-1，處理過一定大於等於1(最長路徑長最短為1)

#### 程式碼(Accepted,C++11,Runtime: 0.000)：

#pragma GCC optimize("Ofast")
#pragma loop_opt(on)
#include<bits/stdc++.h>
//#include<bits/extc++.h>
using namespace std;
template<class T> long long Mod(T a,T b){return ((a%b)+b)%b;}
#define endl '\n'
#define ll long long
#define IO ios_base::sync_with_stdio(0); cin.tie(0);
#define GETOUT cout.tie(0);
#define cendl cout << endl;
#define fr(bob,n,l) for(int bob=(n);bob<(l);++bob)
#define fra(ns,a) for(auto (ns):a)
#define frc(bot,ns,l) for(int bot=(ns);bot<=(l);++bot)
#define frx(i,ns,l) for(int i=(ns);i<(l);++i)
#define mem(arr,initn) memset(arr,initn,sizeof(arr))
#define ALL(va) (va).begin(),(va).end()
#define ALLa(arr) (arr),(arr)+sizeof((arr))/sizeof((arr)[0])
#define printv(va) {fr(i,0,size((va))){cout<<(va)[i]<< ' ';}cendl;}
#define printa(va) {fr(i,0,sizeof((va))/sizeof((va)[0])){cout << (va)[i] << ' ';}cendl;}
#define getpos(va,v) lower_bound((v).begin(),(v).end(),(va)) - (v).begin()
#define arrpos(i,va) distance((va),find(ALLa((va)),i))
#define pb emplace_back
typedef pair<int,int> pii;
#define fi first
#define se second
#define setu(x,y,v) set_union(x.begin(),x.end(),y.begin(),y.end(),back_inserter(v))
#define seti(x,y,v) set_intersection(x.begin(),x.end(),y.begin(),y.end(),back_inserter(v))
#define setdu(x,y,v) set_symmetric_difference(x.begin(),x.end(),y.begin(),y.end(),back_inserter(v))
#define setd(x,y,v) set_difference(x.begin(),x.end(),y.begin(),y.end(),back_inserter(v))
#define toupper(s) transform(s.begin(),s.end(),s.begin(),::toupper)
#define tolower(s) transform(s.begin(),s.end(),s.begin(),::tolower)
const int MAX=1e9+7;
const int MOD=998244353;
const int NN = 105;
int dp[NN][NN];
int mp[NN][NN];
pii MOV[4]={{1,0},{-1,0},{0,-1},{0,1}};
int dfs(pii POS){
	int &now = dp[POS.fi][POS.se];
	if(now!=-1) return now;
	now = 1;
	fr(i,0,4){
		pii nxt = {POS.fi+MOV[i].fi,POS.se+MOV[i].se};
		if(mp[POS.fi][POS.se]>mp[nxt.fi][nxt.se]){
			now = max(now,dfs(nxt)+1);
		}
	}
	return now;
}
inline void solve(){

	string name;
	cin >> name;
	int a,b;
	cin >> a >> b;
	
	frc(i,0,a+1) mp[i][0] = mp[i][b+1] = MAX;
	frc(i,0,b+1) mp[0][i] = mp[i][a+1] = MAX;
	
	frc(i,1,a){
		frc(j,1,b){
			cin >> mp[i][j];
			dp[i][j] = -1;
		}
	}
	
	int ans = INT_MIN;
	frc(i,1,a){
		frc(j,1,b) ans = max(ans,dfs({i,j}));
	}
	cout << name << ": " << ans<<endl;
}
signed main(){
	IO;
	GETOUT;
	int t;
	cin >> t;
	while(t--)solve();
	//cerr << "Time: " << (double)clock() / (double)CLOCKS_PER_SEC << '\n';
	return 0;
}