首页 > 代码库 > 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