| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
MCLEAN - Cleaning Robot |
| English | Vietnamese |
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
|
|||||
|
2015-01-01 09:19:49 [$Zeus$]
BFS + duyệt nhánh cận |
|||||
|
2014-08-18 14:47:57 Nắng
loang mảng 12 chiều Last edit: 2015-01-04 05:19:17 |
|||||
|
2014-08-17 19:36:39 Thcs Ðặng Chánh Kỷ
thánh wolfram |
|||||
|
2014-08-17 19:10:15 Thanga2pbc
giam time éo thành công :) |
|||||
|
2012-08-14 15:31:55 Shinken Yellow
à! <=20 |
|||||
|
2012-08-14 15:30:02 Shinken Yellow
Where is giới hạn of (w,h) ? |
|||||
|
2012-08-13 08:36:37 Tumo@gmail.com
Last edit: 2012-08-13 08:36:51 |
|||||
RSS