AOJ 1214 Walking Ant

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1214。

antが自分の巣に帰る最短距離を求める。四方向に一つ進むのに1timeかかる。初期の体力が6で1timeごとに1ずつ減っていく、食べ物のマスを通ると体力が6になる。

解法

食べ物は２回以上通っても無駄だということが分かれば、BFSで簡単に解ける。

コード

int w, h;
int d[8][8];
int dx[] = {0,-1,0,1}, dy[] = {-1,0,1,0};

int main(){
  while(scanf("%d%d", &w, &h) && w+h){
    int y, x;
    rep(i, h) rep(j, w){
      scanf("%d", &d[i][j]);
      if(d[i][j] != 2) continue;
      y = i; x = j;
    }

    queue<pii> q;
    q.push(M(HP, M(y, x)));
    map<pi, bool> m;
    int t = 1;    
    while(!q.empty()){
      int qsize = (int)q.size();
      rep(i, qsize){
    pii now = q.front(); q.pop();
    rep(j, 4){
      int nt = now.F - 1, ny = now.S.F + dy[j], nx = now.S.S + dx[j];
      if(nt == 0 || ny < 0 || nx < 0 || ny >= h || nx >= w || d[ny][nx] == 0) continue;
      if(!m.count(M(ny, nx)) && d[ny][nx] == 4){
        nt = 6;
        m[M(ny, nx)] = true;
      }else if(d[ny][nx] == 3){
        printf("%d\n", t);
        goto e;
      }

      q.push(M(nt, M(ny, nx)));
    }
      }
      t++;
    }
    puts("-1");
  e:;
  }
  return 0;
}

久々にまともな問題解いた感じ、最近簡単な問題やりすぎた。