| ||||||||||
| 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 | |||||||||
老是re都烦了,麻烦大家看看怎么都想不明白,应该不是数组越界吧,试过开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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator