{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eBài toán tám ô, còn được gọi là \"Chín ô\", xuất phát từ một trò chơi cổ. \u003cbr\u003e\u003cbr\u003eTrong trò chơi này, bạn được cung cấp một bảng 3 x 3 và 8 viên gạch. Các viên gạch được đánh số từ 1 đến 8 và mỗi viên che một ô. Như bạn thấy, có một ô trống có thể được biểu diễn bằng ký tự \u0027X\u0027. Các viên gạch trong các ô có cạnh chung với ô trống có thể được di chuyển vào ô trống đó. Phép toán này dẫn đến việc trao đổi \u0027X\u0027 với một viên gạch.\u003cbr\u003e\u003cbr\u003eChúng tôi sử dụng ký hiệu \u0027r\u0027 để đại diện cho việc trao đổi \u0027X\u0027 với viên gạch bên phải, \u0027l\u0027 cho bên trái, \u0027u\u0027 cho viên gạch phía trên, \u0027d\u0027 cho viên gạch phía dưới.\u003cbr\u003e\u003cbr\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/671f4d3b6e4f813711be59c11286128e?v\u003d1721500698\"\u003e\u003cbr\u003e\u003cbr\u003eTrạng thái của bảng có thể được biểu diễn bằng một chuỗi S theo quy tắc được hiển thị dưới đây.\u003cbr\u003e\u003cbr\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/23e43083209c3a766ab92e1429ae5a49?v\u003d1721500698\"\u003e\u003cbr\u003e\u003cbr\u003eVấn đề là thực hiện một danh sách phép toán \u0027r\u0027, \u0027u\u0027, \u0027l\u0027, \u0027d\u0027 để chuyển trạng thái của bảng từ trạng thái A sang trạng thái B. Bạn cần tìm kết quả đáp ứng các ràng buộc sau:\u003cbr\u003e1. Nó có độ dài tối thiểu trong số tất cả các giải pháp có thể.\u003cbr\u003e2. Nó là giải pháp nhỏ nhất theo thứ tự từ điển trong số tất cả các giải pháp có độ dài tối thiểu.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Đường đầu tiên là T (T \u0026lt;\u003d 200), có nghĩa là số lượng trường hợp kiểm tra của bài toán này.\u003cbr\u003e\u003cbr\u003eĐầu vào của mỗi trường hợp kiểm tra bao gồm hai dòng, với trạng thái A nằm ở dòng đầu tiên và trạng thái B ở dòng thứ hai.\u003cbr\u003eĐược đảm bảo rằng có một giải pháp khả dụng từ trạng thái A đến B.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"Đối với mỗi trường hợp kiểm tra, mong đợi hai dòng.\u003cbr\u003e\u003cbr\u003eDòng đầu tiên có định dạng \"Trường hợp x: d\", trong đó x là số trường hợp được đếm từ một, d là độ dài tối thiểu của danh sách phép toán bạn cần để chuyển A sang B.\u003cbr\u003eS là danh sách phép toán đáp ứng các ràng buộc và nó nên được hiển thị trên dòng thứ hai.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n12X453786\r\n12345678X\r\n564178X23\r\n7568X4123\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 2\r\ndd\r\nCase 2: 8\r\nurrulldr\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}