家具が複数配置された長方形の部屋の床を掃除するロボットの経路計画を 行いたい．
掃除する床をロボットの大きさ（1 × 1）で分割したタイル平面を考える． そこには「きれいなタイル」と「汚れたタイル」があり，掃除ロボットが 「汚れたタイル」に乗ることで，きれいなタイルにすることができる． 部屋のいくつかのタイルには障害物（家具）が乗っており，ロボットはそれらのタイルに入ることはできない． ロボットは1回の移動で東西南北に1タイルのみ移動できる． ロボットは同じタイルに2回以上行ってもよい．
このとき部屋の「汚れたタイル」すべてを「きれいなタイル」にすることが 可能ならば，それに必要な最少移動回数を求めよ．
入力は部屋サイズと構成を表した複数のマップからなる．各マップの 形式は以下のとおりである．
w h
c11 c12 c13 ... c1w
c21 c22 c23 ... c2w
...
ch1 ch2 ch3 ... chw
wとhは正の整数で，それぞれマップの横幅タイル数，縦幅 タイル数を表す． wとhは最大でも20以下である． 文字cyx は以下のように座標 (x, y) の位置 の状態を表す．
'.' : きれいなタイル
'*' : 汚れたタイル
'x' : 家具（障害物）
'o' : ロボット（初期位置を表す）
マップには1つのロボットと最大10個の汚れたタイルを含む．
入力の終わりは，0 0 で表される．
それぞれのマップについて，掃除ロボットの最少移動回数を出力しなさい． もしロボットが到達できない「汚れたタイル」がある場合は，-1を出力し なさい．
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
8 49 -1