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; } }