MCLEAN - Cleaning Robot

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mclean


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


Được gửi lên bởi:psetter
Ngày:2009-02-23
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Pre Japan 05

hide comments
2021-02-07 15:01:26
sao e test trên codeforces ac mà ở đây bị sigsegv vậy :v
2019-07-17 19:46:40
đ m time limit :))) dùng vét cạn :D
2018-06-08 06:31:09
vv
2016-08-19 13:05:59
One shot
2015-12-25 04:42:13 Prismatic
đau nhất là quên khởi tạo lại khi qua test mới @@
2015-09-20 11:21:26 [Nghien] Le Long
BFS bừa AC =))
2015-09-09 15:36:15 nguyenngocanh
tố khiêm óc bã đậu :v
2015-09-09 15:34:13 phạm minh khiêm


Last edit: 2015-10-31 09:35:40
2015-08-10 10:41:45 Phạm Khánh Ly
công sản octom !!
2015-08-10 10:41:09 công

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.