ACM International Collegiate Programming Contest
Japan Domestic, 2005-07-01

Problem F
Cleaning Robot

家具が複数配置された長方形の部屋の床を掃除するロボットの経路計画を行いたい．

掃除する床をロボットの大きさ（1 × 1）で分割したタイル平面を考える．そこには「きれいなタイル」と「汚れたタイル」があり，掃除ロボットが「汚れたタイル」に乗ることで，きれいなタイルにすることができる．部屋のいくつかのタイルには障害物（家具）が乗っており，ロボットはそれらのタイルに入ることはできない．ロボットは1回の移動で東西南北に1タイルのみ移動できる．ロボットは同じタイルに2回以上行ってもよい．

このとき部屋の「汚れたタイル」すべてを「きれいなタイル」にすることが可能ならば，それに必要な最少移動回数を求めよ．

Input

入力は部屋サイズと構成を表した複数のマップからなる．各マップの形式は以下のとおりである．

w h
c₁₁ c₁₂ c₁₃ ... c_1w
c₂₁ c₂₂ c₂₃ ... c_2w
...
c_h1 c_h2 c_h3 ... c_hw

wとhは正の整数で，それぞれマップの横幅タイル数，縦幅タイル数を表す． wとhは最大でも20以下である．文字c_yx は以下のように座標 (x, y) の位置の状態を表す．

'.' : きれいなタイル
'*' : 汚れたタイル
'x' : 家具（障害物）
'o' : ロボット（初期位置を表す）

マップには1つのロボットと最大10個の汚れたタイルを含む．

入力の終わりは，0 0 で表される．

Output

それぞれのマップについて，掃除ロボットの最少移動回数を出力しなさい．もしロボットが到達できない「汚れたタイル」がある場合は，-1を出力しなさい．

Sample Input

7 5
.......
.o...*.
.......
.*...*.
.......
15 13
.......x.......
...o...x....*..
.......x.......
.......x.......
.......x.......
...............
xxxxx.....xxxxx
...............
.......x.......
.......x.......
.......x.......
..*....x....*..
.......x.......
10 10
..........
..o.......
..........
..........
..........
.....xxxxx
.....x....
.....x.*..
.....x....
.....x....
0 0

Output for the Sample Input

8
49
-1

First Input Data