PKU 3328 Cliff Climbing

PKU

http://poj.org/problem?id=3328
最短ののぼりかたのコストを計算する。

ダイクストラ。

int w,h;
char in[100][100];
bool vis[2][100][100];
int solve(){
  priority_queue<pair<PI,PI> > q;
  memset(vis,0,sizeof(vis));
  rep(i,h)rep(j,w){
    cin>>in[i][j];
    if(in[i][j]=='S'){
      q.push(mp(mp(0,0),mp(i,j)));
      q.push(mp(mp(0,1),mp(i,j)));
    }
  }

  while(!q.empty()){
    pair<PI,PI> cv=q.top();q.pop();
    int fo=cv.F.S;
    int cc=-cv.F.F;
    int cx=cv.S.F;
    int cy=cv.S.S;
    if(vis[fo][cx][cy])continue;
    vis[fo][cx][cy]=true;
    if(in[cx][cy]=='T')return cc;
    for(int i=-2;i<=2;++i)
      for(int j=1;j<=3-abs(i);++j){
        int nx=cx+i;
        int ny=cy+(fo*2-1)*j;
        if(min(nx,ny)<0 || nx>=h || ny>=w ||
           vis[!fo][nx][ny] || in[nx][ny]=='X')continue;
        int nc=cc;
        if(isdigit(in[nx][ny]))nc+=in[nx][ny]-'0';
        q.push(mp(mp(-nc,!fo),
                  mp(nx,ny)));
      }
  }
  return -1;  
}


main(){
  while(cin>>w>>h,h)
    cout<<solve()<<endl;
}