poj 2110 Mountain Walking 枚舉+bfs
題意：
給一個n*n的矩陣，要從左上角走到右下角，使經過數字的最大數與最小數的差最小。
分析：
一開始想到了二分這個差，然後判斷是否存在路徑，每次只知道差的話深搜每次搜索要記錄沿途的最大值和最小值會tle,廣搜的話如果節點只記錄x,y坐標,搜索中存在要重新訪問以前訪問過節點的情況，比如一開始（1,1）->(1,2)->(2,2)，如果（2,1）這個點的值更合適，最優訪問路徑（1,1）->(2,1)->(2,2),也就是（2,2）要被重新訪問，不滿足廣搜每個節點只訪問一次的原則，只有增加節點維度每個節點記錄x,y坐標和到達它經過的最小最大值，顯然不好。後來了解到可以加大枚舉，不僅枚舉差，還枚舉路徑上的最大值，這樣每次路徑上的最大最小值就確定了，可以廣搜。
//poj 2110
//sep9
#include
#include
using namespace std;
const int maxN=128;
struct Node
{
int x,y;
};
int g[maxN][maxN];
int vis[maxN][maxN];
int dirx[4]={0,0,-1,1};
int diry[4]={-1,1,0,0};
int n,diff,min_hight,max_hight;
queue q;
bool pass(int low,int high)
{
memset(vis,0,sizeof(vis));
Node a;
a.x=1,a.y=1;
if(g[1][1]>high||g[1][1]=1&&nx<=n&&ny>=1&&ny<=n&&vis[nx][ny]==0&&g[nx][ny]<=high&&g[nx][ny]>=low){
Node a;
a.x=nx,a.y=ny;
q.push(a);
vis[nx][ny]=1;
if(nx==n&&ny==n) return true;
}
}
}
return false;
}
bool work(int mid)
{
for(int high=min_hight;high<=max_hight;++high){
int low=high-mid;
if(pass(low,high))
return true;
}
return false;
}
int main()
{
scanf("%d",&n);
min_hight=INT_MAX;
max_hight=INT_MIN;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
scanf("%d",&g[i][j]);
min_hight=min(min_hight,g[i][j]);
max_hight=max(max_hight,g[i][j]);
}
int ans,l=0,r=max_hight+1,mid;
while(l
