1140.cpp

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

const int INF = 100000000;

int W, H;
string str[32];
int dp[512][512];

int getId(int i, int j) { return i * W + j; }

int main() {
  while (cin >> W >> H, W) {
    REP(i,H) cin >> str[i];
    REP(i,512) REP(j,512) dp[i][j] = INF;
    REP(i,H) REP(j,W-1) if (str[i][j] != 'x' && str[i][j+1] != 'x') {
      dp[getId(i,j)][getId(i,j+1)] = 1;
      dp[getId(i,j+1)][getId(i,j)] = 1;
    }
    REP(i,H-1) REP(j,W) if (str[i][j] != 'x' && str[i+1][j] != 'x') {
      dp[getId(i,j)][getId(i+1,j)] = 1;
      dp[getId(i+1,j)][getId(i,j)] = 1;
    }
    REP(k,H*W) REP(i,H*W) REP(j,H*W)
      dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
    vector<int> pos;
    REP(i,H) REP(j,W) if (str[i][j] == 'o') pos.push_back(getId(i,j));
    REP(i,H) REP(j,W) if (str[i][j] == '*') pos.push_back(getId(i,j));
    vector<int> v;
    REP(i,pos.size()) v.push_back(i);
    int res = INF;
    do{
      if (v[0] != 0) break;
      int cnt = 0;
      REP(i,pos.size()-1) cnt += dp[pos[v[i]]][pos[v[i+1]]];
      res = min(res, cnt);
    } while (next_permutation(ALL(v)));
    cout << (res >= INF ? -1 : res) << endl;
  }
  return 0;
}