LeetCode 补充题 104. 矩阵行列循环移位的最少复原次数
题目描述
给你一个
3 × 3矩阵board，其中包含1到9，每个数字恰好出现一次。每次操作可以选择以下一种方式：
- 将某一行循环右移一格。
- 将某一列循环上移一格。
返回将矩阵恢复为
[[1,2,3],[4,5,6],[7,8,9]]所需的最少操作次数。如果无法恢复，返回-1。矩阵中没有空白格。
示例 1：
输入：
board = [[2,3,1],[4,5,6],[7,8,9]]
输出：1
解释： 将第一行循环右移一格即可复原。
示例 2：
输入：
board = [[3,1,2],[4,5,6],[7,8,9]]
输出：2
解释： 将第一行循环右移两次复原；一次操作不能达到目标。
提示：
- 每次整行或整列的三个元素同时移动。
- 没有空白格。
- 向左移一格等价于向右移两次。
- 向下移一格等价于向上移两次。
题意分析
操作会同时改变一整行或一整列，不能逐个把数字放回目标位置后就固定不动。把整个矩阵视为一个状态，每次合法操作视为一条代价为 1 的有向边，问题就成为初始状态到目标状态的最短路。
这里只有 9 个互不相同的数字，排列数至多为
9!，可以对状态做 BFS。操作方向必须按题面保留，不能把反方向移动也算作一步。
解法：九进制状态编码与 BFS
核心思路
[!blue]
按行读取九个数字，将
1～9映射到九进制数位0～8。固定解码九位可以恢复前导的 0，因此编码不会混淆两个矩阵；最大编码小于9^9，可放入 32 位整数。队列从初始编码开始。每次固定当前层的节点数，依次生成三种行右移和三种列上移；每个后继都从当前矩阵的独立副本产生，防止不同操作叠加。
seen在入队时标记状态，使每个状态只处理一次。BFS 按操作数递增访问，第一次取出目标状态时的层数就是最少步数；初始状态已是目标时返回 0，遍历完可达状态仍未命中则返回 -1。
解题步骤
- 把九个格子的 1 到 9 映射为 0 到 8，用九进制编码状态。
- 从初始状态按层搜索六种合法操作，生成副本并在入队时去重。
- 首次到达目标返回层数，队列耗尽返回 -1。
代码实现
class Solution {
private int encode(int[] a) {
int code = 0;
for (int v : a) {
code = code * 9 + v - 1;
}
return code;
}
private int[] decode(int code) {
int[] a = new int[9];
for (int i = 8; i >= 0; i--) {
a[i] = code % 9 + 1;
code /= 9;
}
return a;
}
public int restoreSteps(int[][] board) {
int[] a = new int[9];
for (int i = 0; i < 9; i++) {
a[i] = board[i / 3][i % 3];
}
int start = encode(a);
int goal = encode(new int[] {
1,
2,
3,
4,
5,
6,
7,
8,
9
});
ArrayDeque<Integer> queue = new ArrayDeque<>();
Set<Integer> seen = new HashSet<>();
queue.add(start);
seen.add(start);
for (int steps = 0; !queue.isEmpty(); steps++) {
for (int size = queue.size(); size > 0; size--) {
int state = queue.remove();
if (state == goal) {
return steps;
}
int[] current = decode(state);
for (int move = 0; move < 6; move++) {
int[] next = current.clone();
if (move < 3) {
int i = move * 3;
next[i] = current[i + 2];
next[i + 1] = current[i];
next[i + 2] = current[i + 1];
} else {
int j = move - 3;
next[j] = current[j + 3];
next[j + 3] = current[j + 6];
next[j + 6] = current[j];
}
int code = encode(next);
if (seen.add(code)) {
queue.add(code);
}
}
}
}
return -1;
}
}
func restoreSteps(board [][]int) int {
encode := func(a [9]int) int {
code := 0
for _, v := range a {
code = code*9 + v - 1
}
return code
}
decode := func(code int) [9]int {
a := [9]int{}
for i := 8; i >= 0; i-- {
a[i] = code%9 + 1
code /= 9
}
return a
}
a := [9]int{}
for i := 0; i < 9; i++ {
a[i] = board[i/3][i%3]
}
start, goal := encode(a), encode([9]int{
1,
2,
3,
4,
5,
6,
7,
8,
9,
})
queue := []int{
start,
}
seen := map[int]bool{start: true}
head := 0
for steps := 0; head < len(queue); steps++ {
end := len(queue)
for head < end {
state := queue[head]
head++
if state == goal {
return steps
}
current := decode(state)
for move := 0; move < 6; move++ {
next := current
if move < 3 {
i := move * 3
next[i], next[i+1], next[i+2] = current[i+2], current[i], current[i+1]
} else {
j := move - 3
next[j], next[j+3], next[j+6] = current[j+3], current[j+6], current[j]
}
code := encode(next)
if !seen[code] {
seen[code] = true
queue = append(queue, code)
}
}
}
}
return -1
}
复杂度分析
- 时间复杂度：$O(9! \cdot 6 \cdot 9)$，用全部排列数作为上界，每个状态生成 6 个后继，每次复制和编码 9 个位置。
- 空间复杂度：$O(9!)$，用于访问集合和搜索队列。
关键点总结
[!green]
状态边代价全为 1，BFS 层数才等于最少操作；逆向操作不是本题允许的一步，不能随意加入。
易错点总结
[!yellow]
不能把逆向操作也按一步加入正向搜索；实际只允许行右移和列上移，否则最少步数会被低估。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 773. 滑动谜题 | 困难 | 同样对整个棋盘状态做 BFS，原题移动空格，本题每一步循环移动一整行或一整列。 |
| 752. 打开转盘锁 | 中等 | 同样把有限状态编码并按合法的一步操作生成邻居，以 BFS 层数表示最短距离。 |