描述

在这里，我们想解决移动机器人清洁矩形房间地板和家具的路径规划问题。

考虑用方形瓷砖铺成的房间地板，其尺寸适合清洁机器人（$1 \times 1$）。有“干净的瓷砖”和“脏的瓷砖”，机器人可以通过访问瓷砖将“脏瓷砖”变成“干净的瓷砖”。此外，可能还有一些障碍物（家具），其大小适合房间内的瓷砖。如果图块上有障碍物，则机器人无法访问它。机器人通过一次移动移动到相邻的图块。机器人移动的瓦片必须是与机器人所在的瓦片相邻的四个瓦片（即东、西、北或南）之一。机器人可能会访问一个图块两次或更多次。

你的任务是编写一个程序，如果可能的话，计算机器人将所有“脏图块”更改为“干净图块”的最小移动次数。

输入

输入由多个映射组成，每个映射表示房间的大小和排列。地图按以下格式提供。

$w$ $h$

$c11$ $c12$ $c13$ ... $c1w$

$c21$ $c22$ $c23$ ... $c2w$

...

$ch1$ $ch2$ $ch3$ ... $chw$

$4$

整数 $w$ 和 $h$ 是房间地板两侧的长度（以地砖的宽度表示）。$w$ 和 $h$ 小于或等于 $20$。字符 $c_{yx}$ 表示图块上最初的内容，坐标为 $(x, y)$，如下所示：

• .：干净的瓦片
• *：脏瓦片
• x：一件家具（障碍物）
• o：机器人（初始位置）

在地图中，“脏图块”的数量不超过 $10$ 个。只有一个“机器人”。

输入的结尾由包含两个 $0$ 的行表示。

输出

对于每张地图，您的程序应输出一行包含最小移动数。如果地图包含机器人无法到达的“脏瓦片”，则程序应输出 $-1$。

输入数据 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

输出数据 1

8
49
-1

来源

日本 2005 国内