朴素bfs压线过了

AC

#include<bits/stdc++.h>
using namespace std;
int a[1010][1010],n,m,b[1010][1010],dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
queue<pair<int,int> >q;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			b[i][j]=1e9;
		}
	}
	q.push(make_pair(1,1));
	b[1][1]=0;
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;
		q.pop();
		for(int i=0;i<4;i++){
			int xn=x+dx[i],yn=y+dy[i];
			if(xn&&yn&&xn<=m&&yn<=n&&b[yn][xn]>max(a[yn][xn],b[y][x])){
				if(a[yn][xn]>b[y][x])	b[yn][xn]=a[yn][xn];
				else	b[yn][xn]=b[y][x];
				q.push(make_pair(xn,yn));
			}
		}
	}
	cout<<b[n][m];
	return 0;
}