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 |
贴个源码,请大家提意见//POJ 1088 #define P {system("PAUSE");} #include<iostream> using namespace std; struct Hill{ int height; //山的高度 int max; //由此开始的最长滑道长度 bool status; }hill[100][100]; int r,c; //山坡范围 int main(){ int findmax(int,int); //寻找最长滑道 bool flag = true; int i,j,maxl = 0; scanf("%d%d",&r,&c); for(i = 0;i < r;i++){ for(j = 0;j < c;j++){ scanf("%d",&hill[i][j].height); hill[i][j].max = 0; //预设最初的状态 hill[i][j].status = false; } } while(flag == true){ //找遍所有的点后比较得出结果 loop: flag = false; for(i = 0;i < r;i++){ for(j = 0;j < c;j++){ if(hill[i][j].status == true)continue; //若此点已搜过则跳过它 flag = true; hill[i][j].max = findmax(i,j); //找出从此点开始的最长滑道长度 if(hill[i][j].max > maxl)maxl = hill[i][j].max; goto loop; //重新从头开始搜索 } } } printf("%d\n",maxl);P return 0; } int findmax(int a,int b){ //动态规划解决?(在邻近的四个格中搜索,利用函数递归) hill[a][b].status = true; int len,maxlen = 1; if(b > 0 && hill[a][b-1].height < hill[a][b].height){ if(hill[a][b-1].status == true)len = 1 + hill[a][b-1].max; //找过了直接赋值 else len = 1 + findmax(a,b-1); //否则调用函数开始寻找 if(len > maxlen)maxlen = len; } if(b < c - 1 && hill[a][b+1].height < hill[a][b].height){ if(hill[a][b+1].status == true)len = 1 + hill[a][b+1].max; else len = 1 + findmax(a,b+1); if(len > maxlen)maxlen = len; } if(a > 0 && hill[a-1][b].height < hill[a][b].height){ if(hill[a-1][b].status == true)len = 1 + hill[a-1][b].max; else len = 1 + findmax(a-1,b); if(len > maxlen)maxlen = len; } if(a < r - 1 && hill[a+1][b].height < hill[a][b].height){ if(hill[a+1][b].status == true)len = 1 + hill[a+1][b].max; else len = 1 + findmax(a+1,b); if(len > maxlen)maxlen = len; } hill[a][b].max = maxlen; return maxlen; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator