{"problem":{"name":"小挖的核燃料填充","description":{"content":"小挖做 Web 设计的时候，剧情里插入了酷炫的核填充情节！但很可惜，受制于技术，情节对应的游戏竟然是数独…… 一开始，会给定你一个有 $n\\times n$ 个**宫**，每个宫中有 $n \\times n$ 个元素，且**早已全部正确填好**的 $n$ 阶数独。本题中数独游戏的详细表示与玩法见下方 **“补充说明”** 。 但小挖会把其中**一些宫向左或者向右转 90 度/180 度**。比","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8549"},"statements":[{"statement_type":"Markdown","content":"小挖做 Web 设计的时候，剧情里插入了酷炫的核填充情节！但很可惜，受制于技术，情节对应的游戏竟然是数独……\n\n一开始，会给定你一个有 $n\\times n$ 个**宫**，每个宫中有 $n \\times n$ 个元素，且**早已全部正确填好**的 $n$ 阶数独。本题中数独游戏的详细表示与玩法见下方 **“补充说明”** 。\n\n但小挖会把其中**一些宫向左或者向右转 90 度/180 度**。比如，若一个宫初始为\n\n```cpp\n087\n654\n321\n```\n\n那么它向左旋转 $90$ 度后会变成：\n\n```cpp\n741\n852\n063\n```\n你在恢复数独时，也**只能将一些宫向左转 $90$ 度**，一次旋转算作一步。现在小挖想考考你：如果把操作后的数独重新恢复成合法的数独，最少需要多少步呢？\n\n如果一开始小挖给出的数独局面不可以通过任意次、任意位置的左旋得到，则输出 $-1$ 。~~为什么呢？因为小挖给出的是“自认为完全正确的”数独，但实际不一定。~~\n\n## Input\n\n第 $1$ 行，输入一个正整数 $n$。\n\n第 $2\\sim n^2+1$ 行，每行输入 $n^2$ 个 $16$ 进制整数，表示一个给定的数独局面，表示小挖操作之后的游戏。\n\n## Output\n\n第 $1$ 行输出一个整数，表示最小步数 $s$。\n\n第 $2\\sim s+1$ 行，每行输出两个整数 $x_i,y_i$。表示对行号列号为 $x_i,y_i$ 的宫向左旋转了 $90$ 度。\n\n数据保证当存在解时，最优解方案唯一。输出时请按如下规则输出：\n\n设 $i<j$ 表示输出方案时的第 $i,j$ 两步。则：\n\n- $x_i\\leq x_j$。\n- 若 $x_i= x_j$ ，则 $y_i\\leq y_j$。\n\n若不存在合法方案，请输出 $-1$。\n\n[samples]\n\n## Note\n\n对于 $40\\%$ 的数据，$2 \\le n\\leq 3$。\n\n对于 $100\\%$ 的数据，$2 \\le n\\leq 4$。\n\n## Hint\n\n$n$ 阶数独合法的条件：每一行、每一列、每一个粗线宫 $(n\\times n)$ 内的数字均含 $0\\sim  n^2-1$，且不重复。\n\n需要注意的是，本题内对于 $4$ 阶数独的表示方式中 $>9$ 的数字采用了十六进制表示法。准确来说 $\\mathrm A=10$，$\\mathrm B=11$，$\\mathrm C=12$，$\\mathrm D=13$，$\\mathrm E=14$，$\\mathrm F=15$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8549","tags":["深度优先搜索 DFS"],"sample_group":[["3\n701210842\n832478367\n564653501\n386648785\n457235610\n021170423\n410702257\n327514806\n685368341","12\n1 1\n1 1\n1 2\n1 3\n2 1\n2 2\n2 3\n2 3\n3 1\n3 1\n3 3\n3 3"],["4\n36952EA1CF74857C\n18E207C9B36D0419\n4DAC56BF8209DFE2\nB07FD3485AE1BA36\n36B5B7CA6E5839FE\nA4985620FD32A8B7\n01CF94DF1B7C0564\n7DE283E14A09C21D\nB46D729D0F7246B0\n8CF560154BCA159E\n1327AB8459D8D278\nEA09FC3E6E31A3CF\n8E910623C5622B60\n320BF7EDB847CDFE\n45AF5A18310F183A\n6CD7B9C4A9ED7459\n","17\n1 1\n1 1\n1 2\n1 2\n1 3\n1 3\n1 4\n2 2\n2 3\n2 4\n3 1\n3 2\n3 2\n3 3\n4 1\n4 2\n4 4\n"]],"created_at":"2026-03-03 11:09:25"}}