{"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\"\u003eKlotski game is coming again!\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/240f7add63275967c7f1d64df52bae73?v\u003d1726279683\"\u003e\u003c/center\u003e \u003cbr\u003e\u003ci\u003e\u003cbr\u003eKlotski (from Polish klocki—wooden blocks) is a sliding block puzzle. Sometimes it only refers to the block arrangement in the right-hand-side diagram, where the largest block (in red) must be moved to the bottom middle location (marked in blue). In a more global sense, Klotski refers to a whole group of similar sliding-block puzzles where the aim is to move a specific block to some predefined location. \u003cbr\u003eFrom Wikipedia.org \u003cbr\u003e\u003c/i\u003e\u003cbr\u003eBut today, I will re-define the game for you. \u003cbr\u003eThe board is a n×m grid. There are some blocks on it. A block covers one or more cells of the grid. These blocks are 4-connected. There are also some empty cells on the board. Every step you can move only one block up or down or to the left or to the right , and two blocks can never overlap. \u003cbr\u003eHere the problem comes: giving you two layouts of board, calculate the least step(s) that needed to move blocks so that the board can be transferred from one layout to another.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"There are several test cases. \u003cbr\u003eFor each test, the first line has three integers n,m and k, indicating that the board is n×m and there are k blocks on it. ( 0\u0026lt; n,m\u0026lt;\u003d20, 0\u0026lt;\u003dk\u0026lt;\u003d10). \u003cbr\u003eThe following n lines describe the starting layout. Every line has m characters representing m cells. \u0027.\u0027 represents an empty cell and ‘0’~’9’ indicates a cell covered by a block. The none-empty cells which represented by the same characters are all covered by a same block and one block can only cover cells represented by the same characters. \u003cbr\u003eThe next n lines describe the ending layout. \u003cbr\u003eInput ends with n \u003d 0 ,m\u003d 0, and k\u003d0."}},{"title":"Output","value":{"format":"HTML","content":"For each test case you should output a line with an integer indicating the least step(s) needed to transform the starting layout into the ending layout."}},{"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\u003e5 4 10\r\n48..\r\n6200\r\n6200\r\n7311\r\n7359\r\n7632\r\n7632\r\n4811\r\n.005\r\n.009\r\n0 0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e46\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eAbout seventy percent of the test cases are of n\u0026lt;\u003d10 and m\u0026lt;\u003d10. There are exactly 10 test cases.\u003cbr\u003e"}}]}