Cleaning Robot
Xem dạng PDF
Gửi bài giải
Điểm:
0,29 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
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à.
- ~H~ dòng tiếp theo, mỗi dòng chứa ~W~ ký tự miêu tả các ô của hình chữ nhật.
- Các ô của sàn có ~4~ giá trị sau:
.: sạch*: bẩnx: vật cản.o: robot ~(1~ con)
- Kết thúc test là 2 số 0 0.
- Có không quá 150 test ở mỗi input.
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~.
Giới hạn
- ~1 \le W~, ~H \le 20~.
- Có không quá ~10~ ô bẩn trên sàn.
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
Sample Output
8
49
-1
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bộ test của bài tập đã được cập nhật, xin cám ơn bạn PPAP_1264589 đã đóng góp test
Hình như số ô bẩn trong mỗi test chỉ khoảng 7 ô thì phải
Mình làm trâu với next_permutation() cũng AC .-.
EDIT 1: Test đã được cập nhật
Bạn có thể đóng góp test bằng cách sinh test và gửi cho bọn mình qua ticket (nút Báo cáo vấn đề) nhé.
SPOILER ALERT !!!
Nếu spoil hướng giải thì bạn nên dùng tag spoiler nhé, tham khảo ở: nội quy comment