信息学奥赛一本通T1280-滑雪

解题思路:从任何一点出发寻找最长路径

注意事项:

参考代码:

#include<iostream>
using namespace std;
const int N = 1e2 + 10;
int g[N][N], f[N][N],r,c,d[4][2]={{-1,0},{1,0},{0,1},{0,-1}},res; 
int dfs(int i, int j){
	if(f[i][j] > 0) return f[i][j];
	int ans = 0;
	for(int k = 0; k < 4; k ++){
		int pi = d[k][0] + i;
		int pj = d[k][1] + j;
		if(pi >= 1 && pi <= r && pj >=1 && pj <= c && g[pi][pj] < g[i][j]) 
			ans = max(ans, dfs(pi,pj));
	}
	return f[i][j] = ans + 1;
}
int main()
{
	cin >> r >> c;
	for(int i = 1; i <= r; i ++)
		for(int j = 1; j <= c; j ++)
			cin >> g[i][j];	
	for(int i = 1; i <= r;  i ++)
		for(int j = 1; j <= c; j ++)
			res = max(res, dfs(i,j));			
	cout << res;
	return 0;
}