題目連結如下:
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;
}