PKU 2922 Honeymoon Hike

http://poj.org/problem?id=2922
n*nの地点の高さの情報が与えられる。
この時、左上から右下まで移動するのに、通過する高さの最小値と最大値の差の最小値はいくつかを答えろというような問題。

最低値を変更しながらbfs(というかダイクストラ?)
時間はそれなりにゆとりがある気がします。

ゴールに辿りつけなかったときに200を返していたせいで1WAして、テストケース毎に改行が必要だというのを見落として1PEもらいました。

なんかものすごく見覚えがありました。
http://poj.org/problem?id=2110
これが複数テストケースになっただけっぽいような気がします。

int in[100][100];
int n;
bool vis[100][100];

int bfs(int low){
  priority_queue<pair<int,PI> >q;
  q.push(mp(-in[0][0],mp(0,0)));
  memset(vis,0,sizeof(vis));
  while(!q.empty()){
    int he=-q.top().F;
    int cx=q.top().S.F;
    int cy=q.top().S.S;
    q.pop();
    if(vis[cx][cy])continue;
    vis[cx][cy]=true;
    if(cx==n-1 && cy==n-1)return he;
    rep(i,4){
      int nx=cx+dx[i],ny=cy+dy[i];
      if(0>nx || nx>=n ||
         0>ny || ny>=n ||
         vis[nx][ny] || in[nx][ny]<low)continue;
      q.push(mp(-max(in[nx][ny],he),mp(nx,ny)));
    }
  }
  return 2000;
}

void solve(){
  cin>>n;
  rep(i,n)rep(j,n)cin>>in[i][j];
  int ans=200;
  for(int low=0;low<=in[0][0];++low){
    ans=min(bfs(low)-low,ans);
  }
  cout<<ans<<endl<<endl;
}

main(){
  int t;
  cin>>t;
  rep(sc,t){
    printf("Scenario #%d:\n",sc+1);
    solve();
  }
}