| ||||||||||
| 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