MCLEAN - Cleaning Robot

Giới hạn

• Thời gian: 0.573s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Sàn nhà là hình chữ nhật, chia thành ô. Trên đó có các ô sạch, bẩn và robot có thể dọn các ô bẩn thành ô sạch nếu nó ở ô đó. Robot có thể di chuyển qua các ô kề cạnh. Xác định số bước di chuyển ít nhất để có thể dọn sạch sàn nếu có thể.

Input

Gồm nhiều test. Dòng đầu mỗi test là 2 số w,h là chiểu rộng và dài của sàn nhà. 

    w h
    c11 c12 c13 ... c1w
    c21 c22 c23 ... c2w
    ...
    ch1 ch2 ch3 ... chw

1<=w,h<=20.

Các ô của sàn có 4 giá trị sau:
    '.' : sạch
    '*' : bẩn
    'x' : vật cản.
    'o' : robot (1 con)

Có không quá 10 ô bẩn trên sàn. 

Kết thúc test là 2 số 0 0.

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

 
In ra số bước di chuyển ít nhất cần sử dụng. Nếu không thể làm sạch sàn, 
in ra -1. 

SAMPLE OUTPUT
8
49
-1

---

• Người up: vdmedragon
• Nguồn bài: Pre Japan 05