> #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;
> }    
>                     
>             
>                
>     

• 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