{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\nUnlike single maze, double maze requires a common sequence of commands to solve both mazes. See the figure below for a quick understanding.\n\u003c/p\u003e\n\u003cdiv style\u003d\"text-align: center;\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/9f32bad7357cc9194c82dffc8d4ec3b4?v\u003d1713862841\" alt\u003d\"Double Maze\"\u003e\u003c/div\u003e\n\u003cp\u003e\nA maze is made up of 6*6 cells. A cell can be either a hole or a square. Moreover, a cell may be surrounded by barriers. There is ONLY one start cell\n(with a ball) and ONLY one end cell (with a star)\nin a single maze. These two cells are both squares. It is possible that the start cell and the end\ncell are the same one. The goal of a single maze is to move the ball from the start cell to the end cell.\nThere are four commands in total, \u0027L\u0027, \u0027D\u0027,\n\u0027R\u0027 and \u0027U\u0027 corresponding to moving the ball left, down, right and up one cell, respectively. The barriers may make the commands take no effect,\ni.e., the ball does NOT move if there is a barrier on the way. When the ball gets to a hole or outside of the maze, it fails.\n\u003c/p\u003e\n\u003cp\u003e\nA double maze is made up of two single mazes. The commands control two balls simultaneously, and the movements of two balls are according to the\nrules described above independently. Both balls will continue to move simultaneously if at least one of the balls has not got to the end cell.\nSo, a ball may move out of the end cell since the other ball has not been to the target.\nA double maze passes when both balls get to their end cells, or fails if either of the two mazes fails.\nThe goal of double maze is to get the shortest sequence of commands to pass. If there are multiple solutions, get the lexicographically minimum\none.\n\u003c/p\u003e\n\u003cp\u003e\nTo simplify the input, a cell is encoded to an integer as follows. The lowest 4 bits signal the existence of the barriers around a cell.\nThe fifth bit indicates whether a cell is a hole or not. The sixth and seventh bits are set for the start cell and end cell.\nDetails are listed in the following table with bits counted from lowest bit. For a barrier, both of the two adjacent cells will have the corresponding barrier bit set.\nNote that the first two mazes in the sample input is the encoding of two mazes in the figure above, make sure you understand the encoding right.\n\u003c/p\u003e\n\n\u003ctable border\u003d\"1\" bgcolor\u003d\"#FFFFFF\" cellpadding\u003d\"1\" align\u003d\"center\" style\u003d\"margin-left:10px\" width\u003d\"250\"\u003e \n\u003ctbody\u003e\u003ctr\u003e\u003cth\u003eBit\u003c/th\u003e \u003cth\u003eValue\u003c/th\u003e \u003cth\u003eDescription\u003c/th\u003e\n\u003c/tr\u003e\u003ctr\u003e \u003ctd rowspan\u003d\"2\" align\u003d\"center\"\u003e1\u003c/td\u003e \u003ctd align\u003d\"center\"\u003e0\u003c/td\u003e \u003ctd\u003eNo barrier to the left\u003c/td\u003e \u003c/tr\u003e\n\u003ctr\u003e \u003ctd align\u003d\"center\"\u003e1\u003c/td\u003e \u003ctd\u003eA barrier to the left\u003c/td\u003e \u003c/tr\u003e\n\u003ctr\u003e \u003ctd rowspan\u003d\"2\" align\u003d\"center\"\u003e2\u003c/td\u003e \u003ctd align\u003d\"center\"\u003e0\u003c/td\u003e \u003ctd\u003eNo barrier to the bottom\u003c/td\u003e \u003c/tr\u003e\n\u003ctr\u003e \u003ctd align\u003d\"center\"\u003e1\u003c/td\u003e \u003ctd\u003eA barrier to the bottom\u003c/td\u003e \u003c/tr\u003e\n\u003ctr\u003e \u003ctd rowspan\u003d\"2\" align\u003d\"center\"\u003e3\u003c/td\u003e \u003ctd align\u003d\"center\"\u003e0\u003c/td\u003e \u003ctd\u003eNo barrier to the right\u003c/td\u003e \u003c/tr\u003e\n\u003ctr\u003e \u003ctd align\u003d\"center\"\u003e1\u003c/td\u003e \u003ctd\u003eA barrier to the right\u003c/td\u003e \u003c/tr\u003e\n\u003ctr\u003e \u003ctd rowspan\u003d\"2\" align\u003d\"center\"\u003e4\u003c/td\u003e \u003ctd align\u003d\"center\"\u003e0\u003c/td\u003e \u003ctd\u003eNo barrier to the up\u003c/td\u003e \u003c/tr\u003e\n\u003ctr\u003e \u003ctd align\u003d\"center\"\u003e1\u003c/td\u003e \u003ctd\u003eA barrier to the up\u003c/td\u003e \u003c/tr\u003e\n\u003ctr\u003e \u003ctd rowspan\u003d\"2\" align\u003d\"center\"\u003e5\u003c/td\u003e \u003ctd align\u003d\"center\"\u003e0\u003c/td\u003e \u003ctd\u003eA hole\u003c/td\u003e \u003c/tr\u003e\n\u003ctr\u003e \u003ctd align\u003d\"center\"\u003e1\u003c/td\u003e \u003ctd\u003eA square\u003c/td\u003e \u003c/tr\u003e\n\u003ctr\u003e \u003ctd rowspan\u003d\"2\" align\u003d\"center\"\u003e6\u003c/td\u003e \u003ctd align\u003d\"center\"\u003e0\u003c/td\u003e \u003ctd\u003eNot start cell\u003c/td\u003e \u003c/tr\u003e\n\u003ctr\u003e \u003ctd align\u003d\"center\"\u003e1\u003c/td\u003e \u003ctd\u003eA start cell\u003c/td\u003e \u003c/tr\u003e\n\u003ctr\u003e \u003ctd rowspan\u003d\"2\" align\u003d\"center\"\u003e7\u003c/td\u003e \u003ctd align\u003d\"center\"\u003e0\u003c/td\u003e \u003ctd\u003eNot end cell\u003c/td\u003e \u003c/tr\u003e\n\u003ctr\u003e \u003ctd align\u003d\"center\"\u003e1\u003c/td\u003e \u003ctd\u003eAn end cell\u003c/td\u003e \u003c/tr\u003e\n\u003c/tbody\u003e\u003c/table\u003e\n\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\n\u003cp\u003e\nThe first line of input gives the total number of mazes, \u003cem\u003eT\u003c/em\u003e (1 \u0026lt; \u003cem\u003eT\u003c/em\u003e ≤ 20). Then follow \u003cem\u003eT\u003c/em\u003e mazes.\nEach maze is a 6*6 matrix, representing the encoding of the original maze.\nThere is a blank line between mazes. \n\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\n\u003cp\u003e\nFor every two consecutive mazes, you should treat them as a double maze and output the answer. So there\nare actually \u003cem\u003eT\u003c/em\u003e-1 answers. For each double maze, output the shortest sequence of commands to pass.\nIf there are multiple solutions, output the lexicographically minimum one. If there is no way to pass, output -1 instead.\n\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\u003e3\n16 0 18 16 18 24\n20 19 24 16 28 1\n18 28 17 0 22 17\n25 20 17 18 88 20\n2 16 48 28 17 16\n24 16 16 20 23 1\n\n16 0 18 16 18 24\n20 19 24 20 29 1\n18 28 17 16 22 17\n8 20 1 18 24 20\n19 80 48 24 16 0\n24 16 16 16 22 19\n\n18 16 18 16 18 80\n24 18 24 16 24 18\n18 24 0 0 18 24\n24 18 0 0 24 18\n18 24 18 16 18 24\n56 18 24 18 24 18\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eRRLULLLRRDLU\nRURDRLLLURDULURRRRRDDU\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003cem\u003eReference:\u003c/em\u003e\n\u003ca href\u003d\"http://www.onemorelevel.com/game/double_maze\" target\u003d\"_blank\"\u003ehttp://www.onemorelevel.com/game/double_maze\u003c/a\u003e"}}]}