实际上是一个简单的二分答案+bfs
首先我们先用bfs得出水在不同的时间所能到达的位置,给每个位置做一个最早到达时间的记录,即step[i][j]。
然后因为高度最高为1e5,那么我们开始二分这个最大跳跃高度的最小值,每次将高度传入,并以这个高度为标准再次进行rabbit在不同时间所能到达的位置,并记录rab[i][j]作为rabbit到达这个位置的时间(每次二分时都需要初始化rab)
对于rabbit能到达的位置,我们有这个条件需要注意:
1、在**(r1!=r2 && c1!=c2)**时,对于水和rabbit都能到达的位置(i,j),必有step[i][j]>rab[i][j],并且当前位置与上一个位置的高度差一定不超过二分出来的高度。
2、对于每一个位置,rab和step都只取最早的到达时间,不重复计算。
最后上代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,m,r1,c1,r2,c2;
int a[101][101];
int ans=0x7fffffff,g=0;
int step[101][101],rab[101][101];
int sp[4][2]={1,0,0,1,-1,0,0,-1};
struct op{
int x,y;
};
void bfs(){
queue<op> Q;
Q.push((op){r2,c2});
step[r2][c2]=1;
while (!Q.empty()){
op tmp=Q.front();
Q.pop();
for(int i=0;i<4;i++){
int xx=tmp.x+sp[i][0],yy=tmp.y+sp[i][1];
if(a[xx][yy]<=a[tmp.x][tmp.y] && xx>0 && xx<=n && yy>0 && yy<=m && step[xx][yy]==0x3f3f3f3f){//判断条件是或否吻合和是否越界
step[xx][yy]=step[tmp.x][tmp.y]+1;
Q.push((op){xx,yy});
}
}
}
}
bool judge(int x,int y){
if(step[x][y]==0x3f3f3f3f)
return 1;
return 0;
}
bool bfs2(int h){
queue<op> Q;
Q.push((op){r1,c1});
rab[r1][c1]=1;
while (!Q.empty()){
op tmp=Q.front();
Q.pop();
if(judge(tmp.x,tmp.y))//如果当前这个点水不能到,则已经达到要求
return 1;
for(int i=0;i<4;i++){
int xx=tmp.x+sp[i][0],yy=tmp.y+sp[i][1];//对四周的点枚举
if(xx>0 && xx<=n && yy>0 && yy<=m && a[xx][yy]-a[tmp.x][tmp.y]<=h && step[xx][yy]>rab[tmp.x][tmp.y]+1 && rab[xx][yy]==0x3f3f3f3f){//判断条件是否吻合和是否越界
rab[xx][yy]=rab[tmp.x][tmp.y]+1;
Q.push((op){xx,yy});
}
}
}
return 0;
}
int main(){
memset(step,0x3f3f3f3f,sizeof(step));
memset(a,0,sizeof(a));
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
scanf("%d %d %d %d",&r1,&c1,&r2,&c2);
bfs();//处理step
int l=0,r=100000;//二分开始
while (l<=r){
memset(rab,0x3f3f3f3f,sizeof(rab));
int mid=(l+r)>>1;
if(bfs2(mid))
ans=mid,r=mid-1;
else
l=mid+1;
}
if(ans<0x7fffffff)//ans是否改变了
printf("%d",ans);
else
printf("-1");
return 0;
}
//Code belongs to JODE