AOJ 1156 Twirling Robot

問題

Twirling Robot

解法

BFSで解けます。priority_queue使ってコストの低いとこから見ていって、goalについたら答えです。

コード

int w, h;
int s[32][32], dy[] = {-1,0,1,0}, dx[] = {0,1,0,-1}, c[4], used[32][32][4];

int main(){
  while(scanf("%d%d", &w, &h) && w+h){
    rep(i, h) rep(j, w) scanf("%d", &s[i][j]);
    rep(i, 4) scanf("%d", c+i);

    memset(used, 0, sizeof(used));
    priority_queue<pipi, vector<pipi>, greater<pipi> >q; // cost, nesw, y, x
    q.push(MP(MP(0, 1), MP(0, 0)));
    while(!q.empty()){
      pipi now = q.top(); q.pop();
      if(used[now.Y][now.X][now.F.S]++) continue;
      if(now.Y == h-1 && now.X == w- 1){
    printf("%d\n", now.F.F);
    break;
      }
      rep(i, 4){
    pipi next = now;
    if(i != s[now.Y][now.X]) next.F.F += c[i];
    next.F.S = (next.F.S+i)%4;
    next.Y += dy[next.F.S]; next.X += dx[next.F.S];
    if(next.Y < 0 || next.X < 0 || next.Y >= h || next.X >= w) continue;
    q.push(next);
      }
    }
  }
  return 0;
}