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 Almighty at 2010-04-29 16:32:13 on Problem 1088
本人新手菜鸟,用的队列做的题,测试数据都能过,discuss的数据也行,就是wa,哪位高人能帮助下小弟呀?

做法:
先声明了围一圈的高度为100000000,读取所有的点高度,读取完,如果四周除了围墙有比该数据大的数该数据就能略过,直接记step为1,如果四周没有比该数据大的,就把小的一个个入队列,出队列时把该数据四周小的入队列,直到队列为盛一个,且不能再进入时为止,并把step记录在数组中
最后扫描下数组,输出最大的step

#include<stdio.h>
typedef struct mountain{int position;int step;}M;
int a[10405];
int step[10001];
M b[100000000];
int main()
{	
	int r,c,i,j,k,l,total=0;
	scanf("%d%d",&r,&c);
	for(i=1;i<=(r+2)*(c+2);i++)
	{
		if(i%(c+2)!=1&&i%(c+2)!=0&&i>c+2&&i<(r+1)*(c+2))
			scanf("%d",a+i);
		else
			*(a+i)=100000000;
	}
	for(i=c+4;i<(r+1)*(c+2);i++)
	{
		l=i;
		if(l%(c+2)!=1&&l%(c+2)!=0)
		{
			total++;
			if((a[l+1]>a[l]&&a[l+1]!=100000000)||(a[l+c+2]>a[l]&&a[l+c+2]!=100000000)||(a[l-1]>a[l]&&a[l-1]!=100000000)||(a[l-c-2]>a[l]&&a[l-c-2]!=100000000))
			{
				step[total]=1;
				continue;
			}
			j=0;
			k=0;
			b[j].step=1;
			b[j].position=l;
			k++;
			while(j!=k)
			{
				if(a[l+1]<a[l])
				{
					b[k].position=l+1;
					b[k].step=b[j].step+1;
					k=(k+1)%1000000;
				}
				if(a[l+c+2]<a[l])
				{
					b[k].position=l+c+2;
					b[k].step=b[j].step+1;
					k=(k+1)%1000000;
				}
				if(a[l-1]<a[l])
				{
					b[k].position=l-1;
					b[k].step=b[j].step+1;
					k=(k+1)%1000000;
				}
				if(a[l-c-2]<a[l])
				{
					b[k].position=l-c-2;
					b[k].step=b[j].step+1;
					k=(k+1)%1000000;
				}
				j=(j+1)%1000000;
				l=b[j].position;			
			}
			step[total]=b[(k+999999)%1000000].step;
		}
	}
	total=step[1];
	for(i=1;step[i]>0;i++)
	{
		if(step[i]>total)
			total=step[i];
	}
	printf("%d",total);
}

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