#include <bits/stdc++.h>
using namespace std;

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(a) max((a),-(a))
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repe(i,n) rep(i,(n)+1)
#define per(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define pere(i,n) rep(i,(n)+1)
#define all(x) (x).begin(),(x).end()
#define SP <<" "<<
#define RET return 0
#define MOD 1000000007
#define INF 1000000000000000000

typedef long long LL;
typedef long double LD;

int main(){
  while(1){
    int w,h;
    cin >> w >> h;
    if(w==0) return 0;
    vector<vector<int>> field(h,vector<int>(w));
    vector<vector<int>> bango(h,vector<int>(w,-1));
    int sx,sy;
    vector<pair<int,int>> gomi(10,{-1,-1});
    int now=0;
    char c;
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        cin >> c;
        if(c=='.'){
          field[i][j]=0;
        }else if(c=='x'){
          field[i][j]=1;
        }else if(c=='*'){
          field[i][j]=0;
          gomi[now]={j,i};
          bango[i][j]=now;
          now++;
        }else{
          field[i][j]=0;
          sx=j,sy=i;
        }
      }
    }
    vector<vector<int>> dist(now,vector<int>(now,1000000));
    int nx,ny;
    int vx[4]={0,1,0,-1},vy[4]={1,0,-1,0};
    queue<pair<int,pair<int,int>>> bfs;
    pair<int,pair<int,int>> nnow;
    for(int i=0;i<now;i++){
      vector<vector<bool>> mita(h,vector<bool>(w,false));
      bfs.push({0,gomi[i]});
      mita[gomi[i].second][gomi[i].first]=true;
      while(!bfs.empty()){
        nnow=bfs.front();
        bfs.pop();
        if(bango[nnow.second.second][nnow.second.first]>=0){
          dist[i][bango[nnow.second.second][nnow.second.first]]=nnow.first;
        }
        for(int i=0;i<4;i++){
          nx=nnow.second.first+vx[i];
          ny=nnow.second.second+vy[i];
          if(0<=nx&&nx<w&&0<=ny&&ny<h){
            if(!mita[ny][nx]&&field[ny][nx]==0){
              mita[ny][nx]=true;
              bfs.push({nnow.first+1,{nx,ny}});
            }
          }
        }
      }
    }
    vector<vector<int>> dp(1<<(now+1),vector<int>(now+1,1000000));
    vector<vector<bool>> mita(h,vector<bool>(w,false));
    bfs.push({0,{sx,sy}});
    mita[sy][sx]=true;
    while(!bfs.empty()){
      nnow=bfs.front();
      bfs.pop();
      if(bango[nnow.second.second][nnow.second.first]>=0){
        dp[1<<bango[nnow.second.second][nnow.second.first]][bango[nnow.second.second][nnow.second.first]]=nnow.first;
      }
      for(int i=0;i<4;i++){
        nx=nnow.second.first+vx[i];
        ny=nnow.second.second+vy[i];
        if(0<=nx&&nx<w&&0<=ny&&ny<h){
          if(!mita[ny][nx]&&field[ny][nx]==0){
            mita[ny][nx]=true;
            bfs.push({nnow.first+1,{nx,ny}});
          }
        }
      }
    }
    int count=0;
    for(int i=1;i<1<<now;i++){
      count=0;
      for(int j=0;j<now;j++) if(i&(1<<j)) count++;
      if(count>1){
        for(int j=0;j<now;j++){
          if(i&(1<<j)){
            for(int k=0;k<now;k++){
              if((i-(1<<j))&(1<<k)){
                dp[i][j]=min(dp[i][j],dp[i-(1<<j)][k]+dist[j][k]);
              }
            }
          }
        }
      }
    }
    int mi=100000000;
    for(int i=0;i<now;i++){
      mi=min(mi,dp[(1<<now)-1][i]);
    }
    if(mi>=1000000) cout << -1 << endl;
    else cout << mi << endl;
  }
  return 0;
}



Measured memory_bytes: 3140