{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eLet’s play a puzzle using eight cubes placed on a 3 × 3 board leaving one empty square.\u003c/p\u003e\u003cp\u003eFaces of cubes are painted with three colors. As a puzzle step, you can roll one of the cubes to a adjacent empty square. Your goal is to make the specified color pattern visible from above by a number of such steps.\u003c/p\u003e\u003cp\u003eThe rules of this puzzle are as follows.\u003c/p\u003e\u003col\u003e\u003cli\u003e\u003cp\u003e\u003cb\u003eColoring of Cubes:\u003c/b\u003e All the cubes area colored in the same way as shown in Figure 1. The opposite faces have the same color.\u003c/p\u003e\u003cdiv align\u003d\"center\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/8d6bab0cad43b8c8ebfc9759de8f80ff?v\u003d1713480756\"\u003e\u003c/div\u003e\u003cp align\u003d\"center\"\u003eFigure 1: Coloring of a cube\u003c/p\u003e\u003c/li\u003e\u003cli\u003e\u003cp\u003e\u003cb\u003eInitial Board State:\u003c/b\u003e Eight cubes are placed on the 3 × 3 board leaving one empty square. All the cubes have the same orientation as shown in Figure 2. As shown in the figure, squares on the board are given \u003ci\u003ex\u003c/i\u003e and \u003ci\u003ey\u003c/i\u003e coordinates, (1, 1), (1, 2), …, and (3, 3). The position of the initially empty square may vary.\u003c/p\u003e\u003cdiv align\u003d\"center\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/fd47a00110ee4ff4a0e7fccabf38957a?v\u003d1713480756\"\u003e\u003c/div\u003e\u003cp align\u003d\"center\"\u003eFigure 2: Initial board state\u003c/p\u003e\u003c/li\u003e\u003cli\u003e\u003cp\u003e\u003cb\u003eRolling Cubes:\u003c/b\u003e At each step, we can choose one of the cubes adjacent to the empty square and roll it into the empty square, leaving the original position empty. Figure 3 shows an example.\u003c/p\u003e\u003cdiv align\u003d\"center\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/d18427112a23e30db911ab80ea80837f?v\u003d1713480756\"\u003e\u003c/div\u003e\u003cp align\u003d\"center\"\u003eFigure 3: Rolling a cube\u003c/p\u003e\u003c/li\u003e\u003cli\u003e\u003cp\u003e\u003cb\u003eGoal:\u003c/b\u003e The goal of this puzzle is to arrange the cubes so that their top faces form the specified color pattern by a number of cube rolling steps described above.\u003c/p\u003e\u003c/li\u003e\u003c/ol\u003e\u003cp\u003eYour task is to write a program that finds the minimum number of steps required to make the specified color pattern from the given initial state.\u003c/p\u003e\u003c/span\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eThe input is a sequence of datasets. The end of the input is indicated by a line containing two zeros separated by a space. The number of datasets is less than 16. Each dataset is formatted as follows.\u003c/p\u003e\u003cblockquote\u003e\u003ctable border\u003d\"0\" width\u003d\"120\" id\u003d\"table1\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd width\u003d\"33%\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/td\u003e\u003ctd width\u003d\"33%\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/td\u003e\u003ctd width\u003d\"33%\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd width\u003d\"33%\"\u003e\u003ci\u003eF\u003c/i\u003e\u003csub\u003e11\u003c/sub\u003e\u003c/td\u003e\u003ctd width\u003d\"33%\"\u003e\u003ci\u003eF\u003c/i\u003e\u003csub\u003e21\u003c/sub\u003e\u003c/td\u003e\u003ctd width\u003d\"33%\"\u003e\u003ci\u003eF\u003c/i\u003e\u003csub\u003e31\u003c/sub\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd width\u003d\"33%\"\u003e\u003ci\u003eF\u003c/i\u003e\u003csub\u003e12\u003c/sub\u003e\u003c/td\u003e\u003ctd width\u003d\"33%\"\u003e\u003ci\u003eF\u003c/i\u003e\u003csub\u003e22\u003c/sub\u003e\u003c/td\u003e\u003ctd width\u003d\"33%\"\u003e\u003ci\u003eF\u003c/i\u003e\u003csub\u003e32\u003c/sub\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd width\u003d\"33%\"\u003e\u003ci\u003eF\u003c/i\u003e\u003csub\u003e13\u003c/sub\u003e\u003c/td\u003e\u003ctd width\u003d\"33%\"\u003e\u003ci\u003eF\u003c/i\u003e\u003csub\u003e23\u003c/sub\u003e\u003c/td\u003e\u003ctd width\u003d\"33%\"\u003e\u003ci\u003eF\u003c/i\u003e\u003csub\u003e33\u003c/sub\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/blockquote\u003e\u003cp\u003eThe first line contains two integers \u003ci\u003ex\u003c/i\u003e and \u003ci\u003ey\u003c/i\u003e separated by a space, indicating the position (\u003ci\u003ex\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e) of the initially empty square. The values of \u003ci\u003ex\u003c/i\u003e and \u003ci\u003ey\u003c/i\u003e are 1, 2, or 3.\u003c/p\u003e\u003cp\u003eThe following three lines specify the color pattern to make. Each line contains three characters \u003ci\u003eF\u003c/i\u003e\u003csub\u003e1\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003eF\u003c/i\u003e\u003csub\u003e2\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e, and \u003ci\u003eF\u003c/i\u003e\u003csub\u003e3\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e, separated by a space. Character \u003ci\u003eF\u003csub\u003eij\u003c/sub\u003e\u003c/i\u003e indicates the top color of the cube, if any, at the position (\u003ci\u003ei\u003c/i\u003e, \u003ci\u003ej\u003c/i\u003e) as follows:\u003c/p\u003e\u003cblockquote\u003e\u003cp\u003e\u003ccode\u003eB:\u003c/code\u003e Blue,\u003c/p\u003e\u003cp\u003e\u003ccode\u003eW:\u003c/code\u003e White,\u003c/p\u003e\u003cp\u003e\u003ccode\u003eR:\u003c/code\u003e Red,\u003c/p\u003e\u003cp\u003e\u003ccode\u003eE:\u003c/code\u003e the square is Empty.\u003c/p\u003e\u003c/blockquote\u003e\u003cp\u003eThere is exactly one ‘\u003ccode\u003eE\u003c/code\u003e’ character in each dataset.\u003c/p\u003e\u003c/span\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eFor each dataset, output the minimum number of steps to achieve the goal, when the goal can be reached within 30 steps. Otherwise, output “\u003ccode\u003e-1\u003c/code\u003e” for the dataset.\u003c/p\u003e\u003c/span\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\u003e1 2 \r\nW W W \r\nE W W \r\nW W W \r\n2 1 \r\nR B W \r\nR W W \r\nE W W \r\n3 3 \r\nW B W \r\nB R E \r\nR B R \r\n3 3 \r\nB W R \r\nB W R \r\nB E R \r\n2 1 \r\nB B B \r\nB R B \r\nB R E \r\n1 1 \r\nR R R \r\nW W W \r\nR R E \r\n2 1 \r\nR R R \r\nB W B \r\nR R E \r\n3 2 \r\nR R R \r\nW E W \r\nR R R\r\n0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0 \r\n3 \r\n13 \r\n23 \r\n29 \r\n30 \r\n-1 \r\n-1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}