include
include
include
include
include
include
include
include
include
include
include
include
include
using namespace std;
define open freopen("input.txt","r",stdin)
define close freopen ("output.txt","w",stdout)
define db double
define ll long long
define lll unsigned long long
define loop(i,a,n) for(int i=a;i<=n;i++)
define sf scanf
define sf1(a) sf("%d",&a)
define sf2(a,b) sf("%d %d",&a,&b)
define sf3(a,b,c) sf("%d %d %d",&a,&b,&c)
define sf4(a,b,c,d) sf("%d %d %d %d",&a,&b,&c,&d)
define sfd(a) sf("%lf",&a)
define sfd2(a,b) sf("%lf %lf",&a,&b)
define sfl1(a) sf("%lld",&a)
define sfl2(a,b) sf("%lld %lld",&a,&b)
define pii pair
define pll pair
define pf printf
define pfi(x) pf("%d",x)
define pfl(x) pf("%lld",x)
define NL puts("")
define bug pf("here is bug\n")
define pft(tc) printf("Case %d:",tc++)
define PI (2.0*acos(0.0))
//#define PI acos(-1.0)
define mem(a,v) memset(a,v,sizeof a)
define endl '\n'
define pb push_back
define xx first
define yy second
define mp make_pair
define all(a) a.begin(),a.end()
template inline T bigmod(T p,T e,T M)
{
ll ret = 1;
for(; e > 0; e >>= 1)
{
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
}
return (T)ret;
}
template inline T gcd(T a,T b)
{
if(b==0)return a;
return gcd(b,a%b);
}
template inline T lcm(T a,T b)
{
return (a/gcd(a,b))*b;
}
template inline T modinverse(T a,T M)
{
return bigmod(a,M-2,M);
} // M is prime}
template inline T bpow(T p,T e)
{
ll ret = 1;
for(; e > 0; e >>= 1)
{
if(e & 1) ret = (ret * p);
p = (p * p);
}
return (T)ret;
}
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
int dx[]={0,1,0,-1};int dy[]={1,0,-1,0}; //4 Direction
define linf 3000000000000000000ll
define inf 999999999
define MX 1000000
define mod (ll) 1000000007
define eps 1e-6
define ub upper_bound // return the right most index of x<val
define lb lower_bound // return the right most index of x<=val
struct data
{
int ele1,ele2,ele3;
data() {}
data(int a,int b,int c)
{
ele1=a,ele2=b,ele3=c;
}
bool friend operator<(data a,data b)
{
return a.ele1> b.ele1;// sort decreasingly but increasingly for priority_queue
}
};
int n,m,k;
ll N,M,K;
char a[30][30];
vector ve;
int mm[30][30];
int sz;
int dis[30][30];
int vis[30][30];
int d[30][30];
int dp[15][(1<<13)+10];
void bfs(int p){
dis[p][p]=0;
int u=ve[p].xx;
int v=ve[p].yy;
d[u][v]=0;
vis[u][v]=1;
queue <int> q;
q.push(u);
q.push(v);
while(!q.empty()){
int x=q.front();
q.pop();
int y=q.front();
q.pop();
for(int i=0;i<4;i++){
int X=x+dx[i];
int Y=y+dy[i];
if(X>=0 && X<m && Y>=0 && Y<n){
if(a[X][Y]!='x' && vis[X][Y]==0){
vis[X][Y]=1;
q.push(X);
q.push(Y);
d[X][Y]=d[x][y]+1;
if(a[X][Y]=='*' || a[X][Y]=='o'){
int g=mm[X][Y];
dis[p][g]=d[X][Y];
}
}
}
}
}
}
int sol(int i,int mask){
if(mask==((1<<sz)-1)) return 0;
int &ret=dp[i][mask];
if(ret!=-1) return ret;
ret=inf;
for(int j=0;j<sz;j++){
if(!(mask & (1<<j))){
ret=min(ret,dis[i][j]+sol(j,(mask | (1<<j))));
}
}
return ret;
}
int main()
{
int t,tc=1;
while(sf2(n,m)==2){
if(n==0 && m==0) break;
mem(mm,-1);
for(int i=0;i<m;i++){
sf("%s",a[i]);
}
int sx=-1,sy=-1;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(a[i][j]=='o'){
ve.pb(mp(i,j));
sx=i;
sy=j;
break;
}
}
if(sx!=-1) break;
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(a[i][j]=='*'){
ve.pb(mp(i,j));
}
dis[i][j]=inf;
}
}
sz=ve.size();
for(int i=0;i<sz;i++){
int x=ve[i].xx;
int y=ve[i].yy;
mm[x][y]=i;
}
for(int i=0;i<sz;i++){
mem(vis,0);
bfs(i);
}
//~ for(int i=0;i<sz;i++){
//~ for(int j=0;j<sz;j++){
//~ pf("%d %d %d\n",i,j,dis[i][j]);
//~ }
//~ }
int tmp=0;
for(int i=0;i<sz;i++){
if(dis[0][i]==inf){
tmp=1;
break;
}
}
if(tmp==1 || sx==-1){
pf("-1\n");
}
else{
mem(dp,-1);
int sk=0;
sk=1;
int res=sol(0,sk);
pfi(res);
NL;
}
ve.clear();
}
return 0;
}
/*
3 2
*xx
o
*/