Cleaning Robot

View as PDF
Submit solution
Points: 0.29 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
Pre Japan 05
Problem types
Allowed languages
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ể.

image

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ẩn
    • x: 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

Comments

Please read the guidelines before commenting.


  • -4
    thefrog  commented on Feb. 26, 2022, 1:58 p.m. ← edited

    QHD


  • -4
    vanglong  commented on Oct. 27, 2021, 5:17 p.m. ← edited

    cảm ơn ad đã có bài hay thực sự ^^


  • 0
    leduykhongngu  commented on Aug. 30, 2021, 4:27 p.m.

    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


  • 0
    PPAP_1264589  commented on Aug. 30, 2021, 6:56 a.m. ← edited

    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


    • 1
      leduykhongngu  commented on Aug. 30, 2021, 6:58 a.m.

      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é.


  • 6
    PPAP_1264589  commented on Aug. 30, 2021, 6:24 a.m. ← edit 2

    SPOILER ALERT !!!

    BFS kết hợp với QHĐ trạng thái


    • 1
      leduykhongngu  commented on Aug. 30, 2021, 6:59 a.m.

      Nếu spoil hướng giải thì bạn nên dùng tag spoiler nhé, tham khảo ở: nội quy comment