1031. 二哥在黄山

Description

二哥与女朋友到黄山旅行。他们在山上玩了一整天，发现天色已晚，该回家了。而突然又开始下起了雨，二哥的女朋友表示非常不爽：“都是你搞的，早知道就不和你来了。”

二哥当然不能抛下女朋友不管，并且二哥也不想露宿在山上。于是他摊开被雨淋湿的地图。

黄山地图是一个N*N的矩阵，矩阵中的每一项表示那个地方的高度。二哥与女朋友处在左上角，他们的住处在右下角。在矩阵中可以朝上下左右走，但不能沿着对角线行走。二哥的女朋友不喜欢颠簸，所以二哥需要找到一条回到住处的路径，使得路径上的最高点与最低点之差尽量小，而不需要管这条路径有多长。

Input Format

第一行：N 接下来N行 N*N的整数矩阵，(0≤每点的高度≤110 )。 (2≤N≤100)

Output Format

一个整数，表示颠簸最小的路径中最高点与最低点的高度差。

Sample Input

51 1 3 6 81 2 2 5 54 4 0 3 38 0 2 3 44 3 0 2 1

Sample Output

2 ====================== 　　开始立马想到最短路径问题，然后就想能不能用动态规划，但是发现不好找状态，因为路径是固定的。最后用类似dijstra解决了，本质就是广度优先。 　　实现的时候地图和所在路径最高值和最低值（不能直接储存差值，否则无法和当前点进行对比）都是用数组储存的，略繁琐。 结果并没有通过，经别人点拨后发现这样确实不行，因为只根据差值判断是否最优有点类似贪心了，无法保证后面路径的选择正确，因为后面路径选择还得考虑最大值和最小值。最后是用二分枚举+bfs解决的。 ========================== c++代码如下：

1 //二哥在黄山  2 #include 
       
         3 #include 
        
          4 using namespace std; 5  6 struct node{ 7     int raw; 8     int col; 9 };10 int n,map[101][101];  //地图边长及数据 11 bool bfs(int low,int);12 13 int main(){14     int i,j,high,low,max=-1,min=120;15 16     cin>>n;17     for (i=1;i<=n;++i)18         for (j=1;j<=n;++j) {19             cin>>map[i][j];20             max = map[i][j]>max ? map[i][j]:max;21             min = map[i][j]
         
          low+1) {26         int mid = (high+low)/2;27         bool flag = 0;28         for (i=min;i<=max-mid;++i) {29             if (bfs(i,i+mid)) {30                 flag = true;31                 break;32             } 33         }34         if (flag) high = mid;35         else low = mid;36     }37     cout<
          
           open;  //待扫描队列 44     if (map[1][1]
           
            high || 45         map[n][n]
            
             high) return false;46 node open_in,open_out;47 open_in.col = 1;48 open_in.raw = 1;49 open.push(open_in);50 state[1][1] = 1;51 while (open.size()>0) {52 open_out = open.front();53 open.pop();54 for (int i = 0;i < 4;++i) { //向四周扫描 55 int x = open_out.raw + to_x[i];56 int y = open_out.col + to_y[i];57 if (x<1 || x>n || y<1 || y>n) continue; 58 if (map[x][y] >= low && map[x][y] <= high && state[x][y]==0) {59 if (x==n && y==n) return true; 60 open_in.col = y;61 open_in.raw = x;62 open.push(open_in);63 }64 state[x][y] = 1;65 }66 }67 return false;68 }