Bài 5: Robot quét vôi
Có 9 căn phòng (đánh số từ 1 đến 9) đã được quét vôi với mầu trắng, xanh hoặc vàng. Có 9 rôbôt (đánh số từ 1 đến 9) phụ trách việc quét vôi các phòng. Mỗi rôbôt chỉ quét vôi một số phòng nhất định. Việc quét vôi được thực hiện nhờ một chương trình cài sẵn theo qui tắc:
- Nếu phòng đang có mầu trắng thì quét mầu xanh
- Nếu phòng đang có mầu xanh thì quét mầu vàng
- Nếu phòng đang có mầu vàng thì quét mầu trắng.
Cần phải gọi lần lượt một số các rôbôt ra quét vôi (mỗi lần một rôbôt, một rôbôt có thể gọi nhiều lần và có thể có rôbôt không được gọi. Rôbôt được gọi sẽ quét vôi tất cả các phòng mà nó phụ trách) để cuối cùng các phòng đều có mầu trắng. Hãy tìm một phương án như vậy sao cho lượng vôi phải quét là ít nhất. Giả thiết rằng luợng vôi cho mỗi lượt quét đối với các phòng là như nhau.
Dữ liệu: đọc từ file văn bản ROBOT.INP gồm các dòng:
- 9 dòng đầu, mỗi dòng mô tả danh sách các phòng được quét vôi bởi một rôbôt theo thứ tự từ rôbôt 1 đến rôbôt 9. Mỗi dòng như vậy gồm các số hiệu phòng viết sát nhau. Chẳng hạn dòng thứ 3 có nội dung: 2356 mô tả rôbôt 3 phụ trách việc quét vôi các phòng 2, 3, 5, 6.
- Dòng cuối mô tả mầu vôi ban đầu của các phòng. Dòng gồm 9 ký tự viết sát nhau, ký tự thứ i biểu diễn mầu vôi của phòng i với quy ước: ký tự T chỉ mầu trắng, ký tự X chỉ mầu xanh, ký tự V chỉ mầu vàng.
Kết quả: đưa ra file văn bản ROBOT.OUT gồm một dòng dưới dạng:
- Nếu không có phương án thì ghi một chữ số 0,
- Trái lại ghi dãy thứ tự các rôbôt được gọi (các số hiệu rôbôt viết sát nhau).
Ví dụ
Hướngdẫn giải
Ta sẽ giải bài toán bằng cách duyệt theo cây tìm kếm. Với mỗi con robot ta có thể không gọi hoặc sẽ gọi tối đa là hai lần, do đó là sẽ có ba cách lựa chọn. Ta sẽ lần lượt duyệt các danh sách để gọi các con robot. Vì có tất cả 9 danh sách nên ta phải duyệt tối đa là 39 cách gọi. Do bài toán đòi hỏi là lượng vôi ít nhất nên ta sẽ tìm cách gọi nào là tối ưu nhất. Để giảm bớt số lần duyệt ta có thể dùng thêm cận để kiểm tra điều kiện có thực hiện tiếp hay không. Nếu ở bước thứ i ta cần gọi là S robot là số lần gọi tối ưu lúc đó là Min thì nếu S > min thì ta có thể nhánh này của cây và quay lại bước thứ i − 1, nếu S < min thì ta có thể tiếp tục duyệt.