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

老是re都烦了,麻烦大家看看

Posted by ivankevin at 2007-02-19 17:07:39 on Problem 2110
怎么都想不明白,应该不是数组越界吧,试过开1000×1000的二维数组和队都不行
#include<stdio.h>
#include<algorithm>
using namespace std;
//#include<string.h>
int i,j,k,l,m,n,mind,minh,ans,tmp,hc,minnum,maxh;
int h[210][210],a[210][210];
//int fx[4]={0,1,0,-1},fy[4]={1,0,-1,0},
int x,y,xe,ye,run,ava;
int fx[5],fy[5];
int qx[100100],qy[100100],qs,qt;

/*int max(int i1,int j1){
	if(i1>j1)return i1;
	else return j1;
}

int min(int i1,int j1){
	if(i1>j1)return j1;
	else return i1;
}*/

int test(int dx){
	int i,j,k;
//	j=
	k=0;
	for(minh=max(0,min(h[1][1],h[n][n])-dx);minh<=min(h[1][1],h[n][n]);minh++){
//	for(minh=0;minh<=min(h[1][1],h[n][n]);minh++){
		maxh=minh+dx;
/*		run++;
		for(i=0;i<=n+1;i++)a[0][i]=run;
		for(i=0;i<=n+1;i++)a[n+1][i]=run;
		for(i=0;i<=n+1;i++)a[i][0]=run;
		for(i=0;i<=n+1;i++)a[i][n+1]=run;*/
		for(i=1;i<=n;i++)for(j=1;j<=n;j++)a[i][j]=0;
		qx[0]=1;
		qy[0]=1;
		qs=qt=0;
		while(qs<=qt){
			x=qx[qs];
			y=qy[qs];
			a[x][y]=1;	
			//if(a[n][n]==1)return 1;
			for(i=0;i<4;i++){
				xe=x+fx[i];
				ye=y+fy[i];
				if(xe>0&&xe<=n&&ye>0&&ye<=n&&a[xe][ye]==0&&h[xe][ye]>=minh&&h[xe][ye]<=maxh){
					qt++;
					qx[qt]=xe;
					qy[qt]=ye;
				}
			}
			qs++;
		}
		if (a[n][n]) {
			k=1;
			break;
		}
	}
	return k;
}

int main(){
	scanf("%d",&n);
	fx[0]=0;fx[1]=1;fx[2]=0;fx[3]=-1;
	fy[0]=1;fy[1]=fy[3]=0;fy[2]=-1;
	maxh=0;
	for(i=1;i<=n;i++)for(j=1;j<=n;j++){
		scanf("%d",&h[i][j]);
		if(maxh<h[i][j])maxh=h[i][j];
	}
	for(i=1;i<=n;i++)for(j=1;j<=n;j++)a[i][j]=0;
	l=max(h[1][1]-h[n][n],h[n][n]-h[1][1]);
	m=maxh;
	//run=0;
 	ans=m;
	while(l<m){
		//if(l==m)break;
		ava=(l+m)/2;
		if(test(ava)==1){
			ans=ava;
			m=ava;
		}else l=ava+1;
	}    
	printf("%d\n",ans);
	scanf("%d",&ans);
	return 0;
}
		
			



			







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