#include<iostream>
#include<queue>
#include<fstream>

using namespace std;

#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
int diff;                 //diff 是高度差
int low,high;           //low high上界和下界
int N;
queue<pair<int,int> >que;
bool signal;          //判断完成标志
int h[200][200];

bool num[111]={0};  //记录值是否出现

int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};

void bloodfill(bool used[200][200]){     //bloodfill判定在上界和下界的范围是否可以完成
    if(que.empty())return;
    pair<int,int> pos=que.front();
    que.pop();
   
    if(pos.first==N-1&&pos.second==N-1){
        signal=1;
       
        return ;
    }
    int x,y;
    int i;
    for(i=0;i<4;i++){
        x=pos.first+dir[i][0];
        y=pos.second+dir[i][1];
        if(x>=0&&x<N&&y>=0&&y<N&&used[x][y]==0&&h[x][y]<=high&&h[x][y]>=low){
            used[x][y]=1;
            que.push(make_pair(x,y));
            
        }  
    }
    bloodfill(used);
}

int main(){
    ifstream cin("tmp.txt");
    cin>>N;
    int i,j;
    int max_n,min_n;
    for(i=0;i<N;i++){
        for(j=0;j<N;j++){
            cin>>h[i][j];
            num[h[i][j]]=1;
        }
    }
    for(i=0;i<=N;i++){
        if(num[i]==1)break;
    }
    min_n=i;
    for(i=N;i>=0;i--){
        if(num[i])break;
    }
    max_n=i;                             
    int limit_low=min(h[0][0],h[N-1][N-1]);
    int limit_high=max(h[0][0],h[N-1][N-1]);
    diff=limit_high-limit_low;
    for(;;diff++){               //枚举，min_n<=low<=low_limit且limit_high<=high<=max_n&&lwoh
        for(low=limit_low;low>=min_n&&low+diff>=limit_high&&low+diff<=max_n;low--){
            if(num[low]==0)continue;
            high=low+diff;
            if(num[high]==0)continue;
            bool used[200][200]={0};
        
            que.push(make_pair(0,0));
            used[0][0]=1;
            signal=0;
            bloodfill(used);
            if(signal){
                goto end;
            }
        }
    }
    end:    
    cout<<diff<<endl;
    system("pause");
    return 0;
}                    
     
                     
        
    
    

• 是对答案的二分，就是上下界的差，二分后再枚举就很快了 (2332) TN 2005-05-13 12:56:56