POJ 2110【Mountain Walking】

题意翻译

题意简述：现在给一个N*N的矩阵，找一条路径从左上角走到右下角，每次可以向上下左右四个方向中某个方向走。要求走过的点中，数字最大的减去最小的。要求值越小越好。现在就是要求这个值。

输入格式：第一行给出一个数字N(2 <= N <= 100),代表矩阵的大小。接下来一个N行N列的矩阵，里面每个数字的值在[0,110]之间。

输出格式：一个数字，如翻译中所述

题目描述

English VietnameseFarmer John and Bessie the cow have embarked on one of those 'active' vacations. They spend entire days walking in the mountains and then, at the end of the day, they tire and return to their vacation cabin.

Since climbing requires a lot of energy and they are already tired, they wish to return to the cabin using a path that has the least difference between its highest and lowest elevations, no matter how long that path is. Help FJ find this easy-to-traverse path.

The map of the mountains is given by an N x N (2 <= N <= 100) matrix of integer elevations (0 <= any elevation <= 110) FJ and Bessie are currently at the upper left position (row 1, column 1) and the cabin is at the lower right (row N, column N). They can travel right, left, toward the top, or toward the bottom of the grid. They can not travel on a diagonal.

输入输出格式

输入格式

Line 1: The single integer, N
Lines 2..N+1: Each line contains N integers, each of which specifies a square's height. Line 2 contains the first (top) row of the grid; line 3 contains the second row, and so on. The first number on the line corresponds to the first (left) column of the grid, and so on.

输出格式

An integer that is the minimal height difference on the optimal path.

输入输出样例

输入样例1

输出样例1

解题思路

　　刚开始我是搜路，不打标记，并记录最高和最低，还开了个DP数组，如果比它优，就更新，加入队列，否则continue。但是我发现我并不是简单的相差，它的最高点和最低点是不确定的，我总不可能每条路一直搜下去吧，所以我们就用的二分来枚举差值，并搜索判断是否有一条路径合法，然后一直下去，输出差值即可。

题解

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int mp[105][105];//图 
 4 int flag[105][105];//标记 
 5 int n;
 6 int dir[4][2]={0,1,0,-1,1,0,-1,0};//四个方向 
 7 struct node
 8 {
 9     int x,y;//坐标 
10     node(){};
11     node(int xx,int yy)
12     {
13         x=xx;
14         y=yy;
15     }
16 };
17 bool bfs(int low,int up)
18 {
19     if(mp[1][1]<low||mp[1][1]>up) return false;//先看起点合法 
20     queue<node> q;
21     q.push(node(1,1));
22     flag[1][1]=1;
23     while(!q.empty())
24     {
25         node head=q.front();
26         q.pop();
27         if(head.x==n&&head.y==n)return true;//合法路径 
28         int x=head.x;
29         int y=head.y;
30         for(int i=0;i<4;i++)
31         {
32             int X=x+dir[i][0];
33             int Y=y+dir[i][1];
34             if(X>=1&&X<=n&&Y>=1&&Y<=n&&flag[X][Y]==0)//判断越界并且没走过 
35             {
36                 flag[X][Y]=1;//标记 
37                 if(mp[X][Y]>=low&&mp[X][Y]<=up)//没超上界或者下界 
38                 {
39                     q.push(node(X,Y));//进队列 
40                 }
41             }
42         }
43     }
44     return false;
45 }
46 bool check(int d)
47 {
48     for(int low=0;low+d<=110;low++)//根据差值枚举上界和下界 
49     {
50         memset(flag,0,sizeof(flag));//初始化标记数组 
51         if(bfs(low,low+d)) return true;//有路径 
52     }
53     return false;//没找到 
54 }
55 int main()
56 {
57     cin>>n;
58     for(int i=1;i<=n;i++)
59     {
60         for(int j=1;j<=n;j++)
61         {
62             cin>>mp[i][j];
63         }
64     }
65     int l=0,r=110;//差值最大就110 
66     while(l<r)//二分枚举差值 
67     {
68         int mid=(l+r)/2;
69         if(check(mid))r=mid;
70         else
71             l=mid+1;
72     }
73     cout<<r;//输出最少差值 
74     return 0;
75 }