1140 : Cleaning Robot

幅優先探索 + ビットDP
汚れたマスを都市とした巡回セールスマン問題と見なせる。（ただしスタート地点に戻る必要はない)
事前に汚れたマス同士の距離を幅優先探索で計算し、あとはビットDPで計算。

int w,h;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
//p1->p2 の最短距離
int calc(vector<string> grid, P p1, P p2){
  int used[20][20];
  memset(used, -1, sizeof(used));
  queue<P> que;
  que.push(p1);
  used[p1.first][p1.second] = 0;
  while(!que.empty()){
    P st = que.front(); que.pop();
    if(st == p2) return used[st.first][st.second];
    REP(r,4){
      int cost = used[st.first][st.second];
      int ny = st.first + dy[r];
      int nx = st.second + dx[r];;
      if(0<=ny && ny<h && 0<=nx && nx<w){
        if(used[ny][nx] == -1 && grid[ny][nx] != 'x'){
          used[ny][nx] = cost + 1;
          que.push(P(ny,nx));
        }
      }
    }
  }
  return INF;
}

int main(){
  while(cin>>w>>h,w){
    vector<string> grid(h);
    REP(i,h)cin>>grid[i];
    P start; //初期位置
    vector<P> target; //汚れたマス
    REP(y,h)REP(x,w){
      if(grid[y][x]=='o'){
        start = P(y,x);
      }else if(grid[y][x] == '*'){
        target.push_back(P(y,x));
      }
    }

    int n = target.size();
    int d[10][10] = {}; //d[i][j]: target[i]とtarget[j]の距離
    REP(i,n)REP(j,n){
      d[i][j] = (i!=j)?(calc(grid,target[i],target[j])):0;
    }

    //dp[S][i] 最短距離: iは最後に到達したマス。Sは到達済みマスをbitであらわす。
    int dp[1<<10][10];
    REP(i,1<<n)REP(j,n)dp[i][j] = INF;
    //startからtarget[i]までの移動を最初に行う
    REP(i,n)dp[1<<i][i] = calc(grid, start, target[i]);
    REP(s,1<<n)REP(from,n){
      REP(to,n){
        dp[s|1<<to][to] = min(dp[s|1<<to][to], dp[s][from] + d[from][to]);
      }
    }

    int ans = INF;
    REP(i,n)ans = min(ans, dp[(1<<n)-1][i]);
    if(ans == INF) ans = -1;
    cout<<ans<<endl;
  }
  return 0;
}