#include<iostream>
#include<vector>
#include<queue>
#include<fstream>
#include<algorithm>

using namespace std;
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
vector<int> vec;
queue<pair<int,int> > que;
int dir[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
int h[200][200];
int N;
int limit;
bool signal;

void search(bool s[200][200]){
    if(que.empty())return ;
    pair<int,int> pos=que.front();
    que.pop();
    if(pos.first==N-1&&pos.second==N-1){
        signal=1;
        while(!que.empty()){
            que.pop();
        }    
        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-1&&y>=0&&y<=N-1&&s[x][y]==0&&abs(h[x][y]-h[pos.first][pos.second])<=limit){
            s[x][y]=1;
            que.push(make_pair(x,y));
        }
    } 
    search(s);
}

int main(){
     ifstream cin("tmp.txt");
    cin>>N;
    
    int i,j;
    for(i=0;i<N;i++){
        for(j=0;j<N;j++){
            cin>>h[i][j];
        }
    }
    int min_n=0;
    for(i=0;i<N;i++){
        for(j=0;j<N;j++){
            if(i<N-1){
                vec.push_back(abs(h[i][j]-h[i+1][j]));
            }
            if(j<N-1){
                vec.push_back(abs(h[i][j]-h[i][j+1]));
            }
        }
    }
    sort(vec.begin(),vec.end());
    unique(vec.begin(),vec.end());
    for(i=0;i<vec.size();i++){
        bool s[200][200]={0};
        signal=0;
        limit=vec[i];
        que.push(make_pair(0,0));
        search(s);
        if(signal)break;
    }
    cout<<vec[i]<<endl;
    system("pause");
    return 0;
}    
                    
            
               
    

• which problem? (1905) TN 2005-05-03 15:57:26
  • sorry,2110 (0) cpp051300448324 2005-05-03 17:14:37
    • 二分答案，枚举下界+FloodFill就行啊，不需要BFS或DFS (0) TN 2005-05-04 13:15:33
    • 当然，我自己写的是BFS (0) TN 2005-05-04 13:25:48