POJ 2110 Mountain Walking(bfs+二分)

       题意是从地图的左上角走到右下角，求所走的路径中最大值和最小值的差值，输出最小的差值。先用二分去找差值，然后枚举区间，看能不能从左上角走到右下角，最后的下界即为所求。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct Node{
  int x,y;
}Now,S,Next;
int vis[105][105];
int MAP[105][105];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int n;

bool in(int x,int y,int low,int high){
  if(x>=0&&y>=0&&x<n&&y<n&&!vis[x][y]&&MAP[x][y]>=low&&MAP[x][y]<=high)return true;
  return false;
}

bool bfs(int low,int high){
  memset(vis,0,sizeof(vis));
  S.x = 0;
  S.y = 0;
  queue<Node> q;
  if(MAP[0][0]<low || MAP[0][0]>high)return false;
  vis[0][0] = 1;
  while(!q.empty())q.pop();
  q.push(S);
  while(!q.empty()){
    Now = q.front();
    q.pop();
    if(Now.x == n-1 && Now.y == n-1)return true;
    for(int i=0;i<4;i++){
      Next.x = Now.x + dir[i][0];
      Next.y = Now.y + dir[i][1];
      if(in(Next.x,Next.y,low,high)){
        vis[Next.x][Next.y] = 1;
        q.push(Next);
      }
    }
  }
  return false;
}

bool Check(int x){
  for(int i=0;i<=110;i++){
    if(bfs(i,i+x))return true;
  }
  return false;
}

int main()
{
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      scanf("%d",&MAP[i][j]);
    }
  }
  int sum = 0;
  int l=0,r=110;int mid;
  while(l <= r){
    mid = (l + r) / 2;
    if(Check(mid)){
      r = mid - 1;
    }
    else l = mid + 1;
  }
  printf("%d\n",l);
  return 0;
}