POJ 2110 Mountain Walking 二分+bfs

传送门

昨天看到这个题还以为是个脑残的dp， 然而脑残的是我。

题目意思就是从左上角走到右下角， 设x为路径上的最大值-最小值， 求x的最小值。

二分x， 对于每一个x， 枚举下界lower， lower从0开始枚举， 每一次bfs的时候， 如果一个点的值小于lower或者大于lower+x， 那么就不走这个点， 看最后能否走到终点。

自己的整数二分写的真是不忍直视...改了好久。

ps：poj2922貌似和这个一样

     #include<bits/stdc++.h>

     using namespace std;

     #define pb(x) push_back(x)

     #define ll long long

     #define mk(x, y) make_pair(x, y)

     #define lson l, m, rt<<1

     #define mem(a) memset(a, 0, sizeof(a))

     #define rson m+1, r, rt<<1|1

     #define mem1(a) memset(a, -1, sizeof(a))

     #define mem2(a) memset(a, 0x3f, sizeof(a))

     #define rep(i, a, n) for(int i = a; i<n; i++)

     #define ull unsigned long long

     typedef pair<int, int> pll;

     const double PI = acos(-1.0);

     const double eps = 1e-;

     const int mod = 1e9+;

     const int inf = ;

     const int dir[][] = { {-, }, {, }, {, -}, {, } };

     int a[][], vis[][], n;

     int bin(int lower, int upper) {

         queue <pll> q;

         mem(vis);

         if(a[][]<lower||a[][]>upper)

             return ;

         q.push(mk(, ));

         vis[][] = ;

         while(!q.empty()) {

             pll tmp = q.front(); q.pop();

             int x = tmp.first;

             int y = tmp.second;

             if(x == n- && y == n-)

                 return ;

             for(int i = ; i<; i++) {

                 int tmpx = x+dir[i][];

                 int tmpy = y+dir[i][];

                 if(tmpx>=&&tmpx<n&&tmpy>=&&tmpy<n&&!vis[tmpx][tmpy]) {

                     vis[tmpx][tmpy] = ;

                     if(a[tmpx][tmpy]<=upper&&a[tmpx][tmpy]>=lower)

                         q.push(mk(tmpx, tmpy));

                 }

             }

         }

         return ;

     }

     int check(int val) {

         for(int i = ; i+val<=; i++) {

             if(bin(i, i+val))

                return ;

         }

         return ;

     }

     int main()

     {

         while(cin>>n) {

             for(int i = ; i<n; i++) {

                 for(int j = ; j<n; j++) {

                     scanf("%d", &a[i][j]);

                 }

             }

             int l = , r = ;

             while(r>l) {

                 int m = l+r>>;

                 if(check(m)) {

                     r = m;

                 } else {

                     l = m+;

                 }

             }

             cout<<l<<endl;

         }

     }