首页 > 代码库 > POJ_1088_dfs
POJ_1088_dfs
http://poj.org/problem?id=1088
dfs过程中,保存经历过的点的最大滑雪距离,依次遍历每一个点的最大距离即可。
#include<iostream>#include<cstdio>using namespace std;int r,c,a[105][105],maxlen[105][105] = {0};int dir[4][2] = {-1,0,0,-1,1,0,0,1};int dfs(int x,int y){ int maxx = 1,len; for(int i = 0;i < 4;i++) { int xx = x+dir[i][0],yy = y+dir[i][1]; if(xx < 1 || xx > r || yy < 1 || yy > c) continue; if(a[x][y] > a[xx][yy]) { if(maxlen[xx][yy]) len = maxlen[xx][yy]+1; else len = dfs(xx,yy)+1; maxx = max(maxx,len); } } maxlen[x][y] = maxx; return maxx;}int main(){ cin >> r >> c; for(int i = 1;i <= r;i++) { for(int j = 1;j <= c;j++) cin >> a[i][j]; } int ans = 1,len; for(int i = 1;i <= r;i++) { for(int j = 1;j <= c;j++) { if(maxlen[i][j] == 0) { len = dfs(i,j); ans = max(ans,len); } } } cout << ans << endl; return 0;}
POJ_1088_dfs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。