extern crate core;

use std::fmt;
use std::i32::{MAX};
use std::cmp::{Ordering, min, max };
use std::ops::{Add, Sub, Mul, Div, Neg, Index, IndexMut, SubAssign, Range};
use std::collections::{BTreeMap, VecDeque, BinaryHeap, BTreeSet, HashMap};
use std::fmt::{Display, Formatter, Error};
use std::str::Chars;

fn show<T: Display>(vec: &Vec<T>) {
    if vec.is_empty() {
        println!("[]");
    }else {
        print!("[{}", vec[0]);
        for i in 1 .. vec.len() {
            print!(", {}", vec[i]);
        }
        println!("]");
    }
}
fn show2<T: Display>(vec: &Vec<Vec<T>>) {
    if vec.is_empty() {
        println!("[]");
    }else {
        for l in vec {
            show(l);
        }
    }
}
macro_rules! read_lines{
    ($count: expr; $delimiter: expr; $ty: ty) => {{
        let line_count = $count;
        let mut vec: Vec<Vec<$ty>> = Vec::with_capacity(line_count);
        for _ in 0 .. line_count {
            vec.push(read_line!($delimiter; $ty));
        }
        vec
    }};
    ($count: expr; $ty: ty) => {{
        let line_count = $count;
        let mut vec: Vec<$ty> = Vec::with_capacity(line_count);
        for _ in 0 .. line_count {
            vec.push(read_value!());
        }
        vec
    }}
}
macro_rules! read_line{
    () => {{
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).ok();
        line
    }};
    (delimiter: ' ') => {
        read_line!().split_whitespace().map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (delimiter: $p:expr) => {
        read_line!().split($p).map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (' ') => {
        read_line!(delimiter: ' ')
    };
    ($delimiter:expr) => {
        read_line!(delimiter: $delimiter)
    };
    (' '; $ty:ty) => {
        read_line!().split_whitespace().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
    ($delimiter:expr; $ty:ty) => {
        read_line!($delimiter).into_iter().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
}
macro_rules! read_value{
    () => {
        read_line!().trim().parse().ok().unwrap()
    }
}
macro_rules! let_all {
    ($($n:ident:$t:ty),*) => {
        let line = read_line!(delimiter: ' ');
        let mut iter = line.iter();
        $(let $n:$t = iter.next().unwrap().parse().ok().unwrap();)*
    };
}

macro_rules! let_mut_all {
    ($($n:ident:$t:ty),*) => {
        let line = read_line!(delimiter: ' ');
        let mut iter = line.iter();
        $(let mut $n:$t = iter.next().unwrap().parse().ok().unwrap();)*
    };
}
struct ValueWithKey<V, K> {
    value: V,
    key: K
}
impl <V, K: PartialOrd> Ord for ValueWithKey<V, K> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.key.partial_cmp(&other.key).unwrap()
    }
}
impl <V, K: PartialOrd> PartialOrd for ValueWithKey<V, K> {
    fn partial_cmp(&self, other: &ValueWithKey<V, K>) -> Option<Ordering> {
        other.key.partial_cmp(&self.key)
    }
}
impl <V, K: PartialEq> PartialEq for ValueWithKey<V, K> {
    fn eq(&self, other: &Self) -> bool {
        other.key.eq(&self.key)
    }
}
impl <V, K: PartialEq> Eq for ValueWithKey<V, K>{}
#[derive(Copy, Clone)]
struct Coordinate {
    x: usize, y: usize
}
fn abs(value: i32) -> i32 {
    if value < 0 {
        -1
    }else if value == 0{
        0
    }else {
        1
    }
}
impl Coordinate {
    fn manhattan_distance(&self, that: &Self) -> i32 {
        abs(self.x as i32 - that.x as i32) + abs(self.y as i32 - that.y as i32)
    }
}
fn cal_min_distance(state: &Vec<String>, from: Coordinate) -> Vec<Vec<i32>> {
    let height = state.len() as i32;
    let width = state[0].len() as i32;
    let mut depth = vec![vec![-1; state[0].len()]; state.len()];
    let mut queue = VecDeque::new();
    depth[from.y][from.x] = 0;
    queue.push_back(from);
    while let Some(Coordinate{x: cx, y: cy}) = queue.pop_front() {
        for dx in -1i32 .. 2i32 {
            if dx == 0 || cx as i32 + dx < 0 || width <= cx as i32 + dx {
                continue
            }
            let x = (cx as i32 + dx) as usize;
            let y = cy;
            if  depth[y][x] == -1 && state[y].chars().nth(x).map_or(false, |c| c != 'x'){
                depth[y][x] = depth[cy][cx] + 1;
                queue.push_back(Coordinate{x: x, y: y});
            }
        }
        for dy in -1i32 .. 2 {
            if dy == 0 || cy as i32 + dy < 0 || height <= cy as i32 + dy {
                continue
            }
            let x = cx;
            let y = (cy as i32 + dy) as usize;
            if  depth[y][x] == -1 && state[y].chars().nth(x).map_or(false, |c| c != 'x'){
                depth[y][x] = depth[cy][cx] + 1;
                queue.push_back(Coordinate{x: x, y: y});
            }
        }
    }
    depth
}
fn main() {
    loop {
        let_all!(w: usize, h: usize); if w == 0 && h == 0 {break;}
        let state = read_lines!(h; String);
        let mut garbage = Vec::new();
        let mut start = Coordinate{x: 0, y: 0};
        for i in 0 .. h {
            for j in 0 .. w {
                match state[i].chars().nth(j) {
                    Some('*') =>
                        garbage.push(Coordinate{x: j, y: i}),
                    Some('o') =>
                        start = Coordinate{x: j, y: i},
                    _ => {}
                }
            }
        }
        let garbage = garbage; let start = start;
        let mut min_distance = vec![vec![-1; garbage.len()]; garbage.len()];
        for i in 0 .. garbage.len() {
            let distance = cal_min_distance(&state, garbage[i]);
            for (j, g) in garbage.iter().enumerate() {
                min_distance[i][j] = distance[g.y][g.x];
            }
        }
        let min_distance = min_distance;
        let mut min_time: Vec<Vec<i32>> = vec![vec![std::i32::MAX; 1 << garbage.len()]; garbage.len()];
        let mut heap = BinaryHeap::new();
        {
            let distance = cal_min_distance(&state, start);
            for (i, g) in garbage.iter().enumerate() {
                min_time[i][1 << i] = distance[g.y][g.x];
                heap.push(ValueWithKey{value: (i, 1 << i), key: min_time[i][1 << i]});
            }
        }
        while let Some(ValueWithKey{value: (current, state), key: cost}) = heap.pop() {
            if min_time[current][state] == cost {
                for (next, g) in garbage.iter().enumerate() {
                    if (state & (1 << next)) == 0 {
                        if min_distance[current][next] != -1 && min_time[next][state | (1 << next)] > cost + min_distance[current][next] {
                            min_time[next][state | (1 << next)] = cost + min_distance[current][next];
                            heap.push(ValueWithKey{value: (next, state | (1 << next)), key: cost + min_distance[current][next]})
                        }
                    }
                }
            }
        }
        if let Some(time) = min_time.iter().filter_map(|l|l.last()).filter(|&t| t != &std::i32::MAX).min() {
            println!("{}", time);
        }else {
            println!("-1");
        }
    }
}



Measured memory_bytes: 5052