讨论 / C++题解
asfeixue 2010-08-10 23:06:00
点我顶贴 收藏 删除
#include <iostream>

using namespace std;

const int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1}; //取用小角标来处理方向的问题

int N[201][201];

int opt[201][201];

int r,c;

int DFS(int x,int y)

{

if(opt[x][y])

return opt[x][y]; //如果搜索到已经确定完成的最优值直接返回

for(int i=0;i<4;i++) //四个方向,逐一搜索

if((N[x][y]>N[x+dx[i]][y+dy[i]])&&(x+dx[i]<=r)&&(x+dx[i]>=1)&&(y+dy[i]<=c)&&(y+dy[i]>=1))//条件合理性

{

int temp=DFS(x+dx[i],y+dy[i]); //每个方向上都有一个最优解

if(temp+1>opt[x][y])

opt[x][y]=temp+1;

}

if(opt[x][y]==0) //搜索到终点时终点位置占一位

opt[x][y]=1;

return opt[x][y];

}

int main()

{

cin>>r>>c;

memset(N,128,sizeof(N));

memset(opt,0,sizeof(opt));

for(int i=1;i<=r;i++)

for(int j=1;j<=c;j++)

cin>>N[i][j];

int max=0;

for(int i=1;i<=r;i++)

for(int j=1;j<=c;j++)

{

int temp=0;

temp=DFS(i,j);

if(temp>max)

max=temp;

}

cout<<max<<endl;

return 0;

}

查看更多回复
提交回复