题目链接如下:
https://nanti.jisuanke.com/t/43321
思路:
显然我们要采用二分的方法来寻找答案, 给定一个高度如果能确定在这个高度时是否可以安全到达终点, 那我们就可以很快二分出最大可行的高度. 在判断一个高度是否可行时, 搜索从起点开始, 在限制的高度下所有可以到达的坐标位置, 检验是否经过终点即可.
- /************************************************
- ┆ ┏┓ ┏┓ ┆
- ┆┏┛┻━━━┛┻┓ ┆
- ┆┃ ┃ ┆
- ┆┃ ━ ┃ ┆
- ┆┃ ┳┛ ┗┳ ┃ ┆
- ┆┃ ┃ ┆
- ┆┃ ┻ ┃ ┆
- ┆┗━┓ ┏━┛ ┆
- ┆ ┃ ┃ ┆
- ┆ ┃ ┗━━━┓ ┆
- ┆ ┃ AC 代马 ┣┓┆
- ┆ ┃ ┏┛┆
- ┆ ┗┓┓┏━┳┓┏┛ ┆
- ┆ ┃┫┫ ┃┫┫ ┆
- ┆ ┗┻┛ ┗┻┛ ┆
- ************************************************ */
- #include <iostream>
- #include <algorithm>
- #include <set>
- #include <vector>
- #include <queue>
- #include <string>
- #include <sstream>
- #include <cstdio>
- #include <cstring>
- #include<cctype>
- #include <math.h>
- #include <cmath>
- #include <bits/stdc++.h>
- #define INF 0x3f3f3f3f
- #define lb long double
- #define LINF 0x3f3f3f3f3f3f3f3f
- #define ull unsigned long long
- #define random(x) (rand()%x)
- #define sgn(x) (fabs(x) <eps ? 0 : ((x) < 0 ? -1 : 1))
- #define rep(i, a, b) for(int i=a;i<b;i++)
- #define req(j, a, b) for(int j=a;j<b;j++)
- #define mem(a, b) memset(a, b, sizeof(a))
- #define PI 3.141592653589793
- #define K 20
- using namespace std;
- typedef long long ll;
- const int maxn = 1e5 + 5;
- const double eps =1e-14;
- const double pi = acos(-1);
- const ll mod = 1e9 + 7;
- const int hash_mod = 19260817;
- inline int read()
- {
- int X=0,w=0; char ch=0;
- while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
- while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
- return w?-X:X;
- }
- inline double dbread()
- {
- double X=0,Y=1.0; int w=0; char ch=0;
- while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
- while(isdigit(ch)) X=X*10+(ch^48),ch=getchar();
- ch=getchar();// 读入小数点
- while(isdigit(ch)) X+=(Y/=10)*(ch^48),ch=getchar();
- return w?-X:X;
- }
- inline void write(int x)
- {
- if(x<0) putchar('-'),x=-x;
- if(x>9) write(x/10);
- putchar(x%10+'0');
- }
- ll gcd(ll a,ll b)// 辗转相除法 (欧几里德算法) 求最大公约数
- {
- return b ? gcd(b,a%b) : a;
- }
- ll lcm(ll a,ll b)
- {
- return a*b/gcd(a,b);// 最小公倍数
- }
- ll q_pow(ll base, ll p)
- {
- ll result = 1;
- while(p> 0)
- {
- if(p&1)
- {// 此处等价于 if(power%2==1)
- result = result * base % 1000;
- }
- p>>= 1;// 此处等价于 power=power/2
- base = (base * base) % 1000;
- }
- return result;
- }
- const int N = 250005;
- int fri[N];
- void init()
- {
- for(int i = 0; i <= N; i++)
- fri[i] = i;
- }
- int find(int a) // 查找根节点
- {
- int tem1 = a,tem2;
- while(a != fri[a])
- a = fri[a];
- while(tem1 != a)
- {
- tem2 = fri[tem1];
- fri[tem1] = a;
- tem1 = tem2;
- }
- return a;
- }
- void Union(int a,int b)
- {
- int fri_a = find(a);
- int fri_b = find(b);
- if(fri_a != fri_b)
- {
- fri[fri_a] = fri_b;
- }
- return ;
- }
- int eval(char c)
- {
- if(c==' ')
- return 0;
- if(c=='\'')
- return 1;
- return c - 'A' + 2;
- }
- double pointSegDist(double cx, double cy, double px1, double py1, double px2, double py2)
- {
- cx -= px1;
- px2 -= px1;
- cy -= py1;
- py2 -= py1;
- double len = sqrt(px2*px2 + py2*py2);
- double ux = px2 / (len * 1.0);
- double uy = py2/ (len * 1.0);
- uy = -uy;
- double nx = cx * ux - cy * uy;
- double ny = cx * uy + cy * ux;
- if(nx>=0 && nx <= len)
- return abs(ny);
- if(nx> len)
- nx -= len;
- return sqrt(nx*nx + ny*ny);
- }
- bool f(ll n)
- {
- for(ll i=2;i<=n;i++)
- {
- if(n % (i * i) == 0)
- return false;
- }
- return true;
- }
- bool judgeStr(string s)
- {
- int len = s.size();
- int i,j;
- for(i=0,j=len-1;i<=len/2;i++,j--)
- {
- if(s[i]!=s[j])
- return 0;
- }
- return 1;
- }
- ll f(ll n, ll d)
- {
- ll ans = 0;
- while(n> 0 && n % d == 0)
- {
- n /= d;
- ans++;
- }
- return ans;
- }
- ll power(ll a, ll b)
- {
- long long ans = 1;
- for (int i=0;i<b;i++)
- ans *= a;
- return ans;
- }
- const int maxnn = 1e5+5;
- int dx[4]={1, 0, -1, 0};
- int dy[4]={0, 1, 0, -1};
- int vis[505][505];
- int w[505][505];
- int r, c;
- int bfs(int h)
- {
- mem(vis, 0);
- vis[0][0] = 1;
- queue<int> q;
- //x,y,dis
- q.push(0);
- q.push(0);
- q.push(0);
- while(q.size()> 0)
- {
- int x = q.front();
- q.pop();
- int y = q.front();
- q.pop();
- int dis = q.front();
- q.pop();
- if(w[x][y] - dis>= h)
- {
- if(x == r-1 && y == c-1)
- {
- return true;
- }
- for(int i=0;i<4;i++)
- {
- int a = x + dx[i];
- int b = y + dy[i];
- if(a>= 0 && a <r && b>= 0 && b <c && !vis[a][b])
- {
- vis[a][b] = 1;
- q.push(a);
- q.push(b);
- q.push(dis+1);
- }
- }
- }
- }
- return false;
- }
- int main()
- {
- int t;
- cin>> t;
- while(t--)
- {
- cin>> r>> c;
- for(int i=0;i<r;i++)
- {
- for(int j=0;j<c;j++)
- {
- cin>> w[i][j];
- }
- }
- int left = 0;
- int right = INF;
- while(left <right)
- {
- int mid = (left + right + 1) / 2;
- if(bfs(mid))
- {
- left = mid;
- } else
- {
- right = mid - 1;
- }
- }
- if(left> 0)
- cout << left << endl;
- else
- cout << "impossible" << endl;
- }
- return 0;
- }
来源: https://www.cnblogs.com/alanwade/p/12593523.html