Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
坑爹啊,高度相等不行,否则re.另付代码#include<iostream> using namespace std; #define MAX 105 #define max(a, b) ((a) > (b) ? (a) : (b)) #define inf 1000000000 int map[MAX][MAX];//MAP int dp[MAX][MAX];//dp[i][j]:到(i, j)距离最大值 int vist[MAX][MAX]; int r, c;//R, C int solve(int x, int y) { if(x >= r || y >= c) return 0; if(vist[x][y] != 0) return dp[x][y]; int ans = 0; if(x - 1 >= 0 && map[x][y] < map[x - 1][y]) ans = max(ans, solve(x - 1, y) + 1); if(x + 1 < r && map[x][y] < map[x + 1][y]) ans = max(ans, solve(x + 1, y) + 1); if(y - 1 >= 0 && map[x][y] < map[x][y - 1]) ans = max(ans, solve(x, y - 1) + 1); if(y + 1 < c && map[x][y] < map[x][y + 1]) ans = max(ans, solve(x, y + 1) + 1); vist[x][y] = 1;//标记已访问 dp[x][y] = max(ans, dp[x][y]); return dp[x][y]; } int main() { int i, j; //freopen("out.txt", "w", stdout); //freopen("in.txt", "r", stdin); while(scanf("%d%d", &r, &c) != EOF) { for(i = 0; i < r; i ++)//row { for(j = 0; j < c; j ++) //col { scanf("%d", &map[i][j]); dp[i][j] = 1; } } //dp int ans = 0; memset(vist, 0, sizeof(vist)); for(i = 0; i < r; i ++) { for(j = 0; j < c; j ++) { solve(i, j); ans = max(dp[i][j], ans); } } printf("%d\n", ans); } } /* 5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 4 4 1478 9358 6962 4464 5705 8145 3281 6827 9961 491 2995 1942 4827 5436 2391 4604 25 5 */ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator