PKU 2312 Battle City

http://poj.org/problem?id=2312
'Y'から'T'まで移動するのにかかる最短時間を求める。
ただし、'R'と'S'へは移動できない。
また、一回の操作で、上下左右に進むか、上下左右に砲撃することができて、砲撃によって'B'を破壊できる。
'B'は破壊されなければ通過できない。

'B'を通るときだけコストを2と考えればダイクストラできる。

string in[300];
bool vis[300][300];

main(){
  int n,m;
  while(cin>>n>>m,n|m){
    memset(vis,0,sizeof(vis));
    int sx,sy;
    rep(i,n){
      cin>>in[i];
      rep(j,m){
        if(in[i][j]=='Y'){
          sx=i,sy=j;
          in[i][j]='E';
        }
      }
    }
    priority_queue<pair<int,PI> >q;
    q.push(mp(0,mp(sx,sy)));

    int ans=-1;
    while(!q.empty()){
      int cc=-q.top().F,cx=q.top().S.F,cy=q.top().S.S;
      q.pop();
      if(vis[cx][cy])continue;
      vis[cx][cy]=true;
      if(in[cx][cy]=='T'){
        ans=cc;
        break;
      }

      rep(i,4){
        int nx=cx+dx[i],ny=cy+dy[i];
        if(nx<0 || n<=nx ||
           ny<0 || m<=ny ||
           vis[nx][ny] ||
           in[nx][ny]=='S' ||
           in[nx][ny]=='R')continue;
        int nc=cc+1;
        if(in[nx][ny]=='B')++nc;
        q.push(mp(-nc,mp(nx,ny)));
      }
    }
    cout<<ans<<endl;
  }
}