Untitled

 avatar
unknown
plain_text
a year ago
2.9 kB
7
Indexable
Robot làm sạch
Chúng ta phải lên kế hoạch cho một robot dọn dẹp để làm sạch sàn phòng hình chữ nhật có kích thước NxM. Sàn phòng được lát bằng gạch vuông có kích thước phù hợp với robot dọn dẹp (1 × 1). Có gạch sạch và gạch bẩn, và robot có thể thay đổi gạch bẩn thành gạch sạch bằng cách truy cập gạch. Ngoài ra có thể có một số chướng ngại vật (đồ nội thất) có kích thước phù hợp với một viên gạch trong phòng. Nếu có chướng ngại vật trên gạch, robot không thể ghé thăm nó. Robot di chuyển đến một ô liền kề bằng một lần di chuyển. Ô mà robot di chuyển phải là một trong bốn ô (tức là đông, tây, bắc hoặc nam) liền kề với ô nơi robot có mặt. Robot có thể ghé thăm một ô hai lần trở lên.

Nhiệm vụ của bạn là viết một chương trình tính toán số lần di chuyển tối thiểu để robot thay đổi tất cả các ô bẩn thành gạch sạch, nếu có thể.

Giới hạn thời gian: 1s (C / C ++), 2s (Java)

Giới hạn gửi: 10 lần

Ví dụ:

Sau đây là một căn phòng có kích thước 5x7, với 3 viên gạch bẩn, và 0 đồ nội thất. Câu trả lời cho trường hợp này là 8.




Nhập

Đầu vào bao gồm nhiều bản đồ, dòng đầu tiên là số trường hợp kiểm thử T (T < = 50).

Mỗi trường hợp kiểm thử bắt đầu bằng N và M đại diện cho kích thước của căn phòng. ( 5 = < N, M <= 100)

Dòng N tiếp theo đại diện cho sự sắp xếp của căn phòng với mô tả sau:

0 : một viên gạch
sạch 1 : một viên gạch
bẩn 2 : một mảnh đồ nội thất (chướng ngại vật)
3: robot (vị trí ban đầu)

Trong bản đồ, số lượng gạch bẩn không vượt quá 10 và chỉ có một robot.

Ra

In mỗi trường hợp kiểm thử trên hai dòng, dòng đầu tiên của mỗi trường hợp kiểm thử là "Case #x", trong đó x là số test case. Dòng tiếp theo là số lần di chuyển tối thiểu để robot thay đổi tất cả các ô bẩn thành gạch sạch. Nếu bản đồ bao gồm các ô bẩn mà robot không thể với tới, chương trình của bạn sẽ xuất ra -1.

Mẫu

Nhập

5

5 7

0 0 0 0 0 0 0

0 3 0 0 0 1 0

0 0 0 0 0 0 0

0 1 0 0 0 1 0

0 0 0 0 0 0 0

5 15

0 0 0 0 2 0 2 0 0 0 0 1 2 0 1

0 0 0 1 0 2 0 2 2 0 1 2 0 0 0

2 1 0 2 0 1 0 2 0 0 0 0 0 0 0

0 0 0 1 0 2 0 0 1 2 0 0 2 0 0

0 2 1 0 2 0 0 0 0 0 3 0 0 0 0

...............

Ra

Trường hợp #1

8

Trường hợp #2

38

Trường hợp #3

37

Trường hợp #4

-1

Trường hợp #5

49
Editor is loading...
Leave a Comment