Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴个源码,请大家提意见

Posted by 1200017623 at 2012-12-26 19:40:20 on Problem 1088
//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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator