Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MCLEAN - Cleaning Robot


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ể.
Image and video hosting by TinyPic

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:~!(*(@*!@^&
Ngày:2009-02-23
Thời gian chạy:0.161s-0.573s
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
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

2015-01-01 09:19:49 [$Zeus$]
BFS + duyệt nhánh cận
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.