GMSD @ 2018-05-27 20:37:31
#include<bits/stdc++.h>
using namespace std;
int maxx,length,wide,height[3002][3002],maxi,maxj,minn,mini,minj;
int q[30003][4],res[3002][3002],hd,tl,nx,ny,dx[5]={-1,-1,0,0},dy[5]={0,0,-1,-1};
void bfs(int x,int y){int maxx,maxxi,maxxj ;
hd=0;tl=1;q[1][0]=x;q[1][1]=y;res[x][y]=1;
while(hd<tl){
hd++;
for(int i=0;i<4;i++){
nx=q[hd][0]+dx[i];ny=q[hd][1]+dy[i];
if(height[nx][ny]>height[q[hd][0]][q[hd][1]]){
maxx=max(maxx,height[nx][ny]);
if(maxx==height[nx][ny])maxxi=nx,maxxj=ny;
}
}
if(maxxi==mini&&maxxj==minj)return;
tl++;q[tl][0]=maxxi;q[tl][1]=maxxj;res[maxxi][maxxj]=1;q[tl][2]++;
}
}
int main(){
cin>>length>>wide;
for(int i=1;i<=length;i++)
for(int j=1;j<=wide;i++){
cin>>height[i][j];maxx=max(maxx,height[i][j]);minn=min(minn,height[i][j]);
if(maxx==height[i][j])maxi=i,maxj=j;
if(minn==height[i][j])mini=i,minj=j;
}
bfs(maxi,maxj);
cout<<q[tl][2];
return 0;
}
by 氷スイカ233 @ 2018-05-27 20:41:51
数组小辣!
by 单曦增 @ 2018-05-27 21:07:37
@天才DXL bfs搜出来的不是最短的吗