Input

The first line contains two integers: the length MM, and the width NN of the vault, satisfying 1 \leq M,N \leq 10001≤M,N≤1000.The following MM lines each contain NN integers. Each integer specifies the height of the pile of coins in the vault at the corresponding position. (The first line describes the north-most stacks from west to east; the last line describes the south-most stacks from west to east). The heights are given in meters and all heights are at least 00 and at most 10^9109 (yes, your friend’s uncle is very rich).

Output

Output a single line containing a single integer: the length in meters of the shortest ladder that allows you to get from the north west corner to the south east corner.

样例输入1

3 3
1 2 3
6 5 4
7 8 9


样例输出1

1


样例输入2

1 4
4 3 2 1


样例输出2

0


样例输入3

7 5
10 11 12 13 14
11 20 16 17 16
12 10 18 21 24
14 10 14 14 22
16 18 20 20 25
25 24 22 10 25
26 27 28 21 25


样例输出3

3


想法

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0)
using namespace std;
struct node{
int x,y,v;
bool operator<(const node & o)const{ //v代表每一个点到起点需要的梯子数量
return v>o.v;
}
};
priority_queue<node> p;
bool vis[1006][1006];
int arr[1006][1006],dir[4][2]={1,0,-1,0,0,1,0,-1},n,m;
int bfs(){
int num=0;
while(!p.empty()){
node d=p.top();
p.pop();
int x=d.x,y=d.y,v=d.v;
if(x==n&&y==m) return v; //到达了终点
if(vis[x][y]) continue;
vis[x][y]=1; //记得标记
for(int i=0;i<4;++i){
int x1=x+dir[i][0],y1=y+dir[i][1];
if(x1<=0||x1>n||y1<=0||y1>m) continue;
int tmp;
if(arr[x1][y1]-arr[x][y]<0) tmp=0; //这是刚开始如果下一个点比这个点小不能用负数，得用0
else tmp=arr[x1][y1]-arr[x][y]; 这段需要的梯子长度
int v1=max(v,tmp); //取他们较大的那个
p.push({x1,y1,v1}); //放进队列
}
}
}
int main()
{
ios;
cin>>n>>m;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cin>>arr[i][j];
}
}
p.push({1,1,0});
cout<<bfs()<<'\n';
}