Sắc Màu Lập Phương
View as PDFKhối Rubik 2×2×2 gồm sáu mặt, mỗi mặt có bốn ô. Sáu màu được ký hiệu bằng các chữ cái U, D, F, B, L, R, tương ứng với màu của các mặt.
Một thao tác là xoay một mặt 90° theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ, khi nhìn trực tiếp vào mặt đó từ bên ngoài khối Rubik. Mỗi lần xoay 90° tính là một bước; do đó, xoay 180° tính là hai bước. Xoay toàn bộ khối Rubik không được tính là một thao tác.
Với trạng thái ban đầu được cho, hãy tìm số bước ít nhất để giải khối Rubik. Khối được xem là đã giải nếu bốn ô trên mỗi mặt cùng màu; hướng đặt của toàn bộ khối không ảnh hưởng đến kết quả.
Dữ liệu vào
Sáu dòng lần lượt mô tả các mặt U, D, F, B, L, R. Mỗi dòng gồm bốn ký tự, biểu diễn bốn ô trên mặt tương ứng theo thứ tự trong bảng dưới đây.
| Mặt | Thứ tự bốn ô trong dòng |
|---|---|
| U | Hàng sau → trước; trong mỗi hàng, trái → phải |
| D | Hàng trước → sau; trong mỗi hàng, trái → phải |
| F | Hàng trên → dưới; trong mỗi hàng, trái → phải |
| B | Hàng trên → dưới; trong mỗi hàng, phải → trái |
| L | Hàng trên → dưới; trong mỗi hàng, sau → trước |
| R | Hàng trên → dưới; trong mỗi hàng, trước → sau |
Các ký tự màu là U, D, F, B, L, R. Mỗi màu xuất hiện đúng bốn lần. Trạng thái được cho luôn hợp lệ và có thể nhận được bằng cách xoay một khối Rubik đã giải.
Dữ liệu ra
In một số nguyên — số bước ít nhất để giải khối Rubik.
Ví dụ
Input
UUUU
DDDD
RRFF
LLBB
FFLL
BBRR
Output
1
Giải thích: Ví dụ trên thu được khi xoay mặt U của khối đã giải 90° theo chiều kim đồng hồ, nên đáp án là 1.
Subtasks
| Nhóm | Ràng buộc theo đáp án | Điểm |
|---|---|---|
| 1 | Đáp án không quá 1 bước | 25 |
| 2 | Đáp án từ 2 đến 4 bước | 25 |
| 3 | Đáp án từ 5 đến 8 bước | 25 |
| 4 | Đáp án từ 9 đến 14 bước | 25 |
Các test được chấm độc lập, mỗi test có trọng số bằng nhau; không áp dụng chấm theo batch.