问题分析

我们有一个 $N \times M$ 的网格，每个格子包含一个唯一的数字 $0$ 到 $N \times M - 1$。目标是通过行循环右移和列循环下移操作，将网格变成"和谐数组"：

• 第1行：$0, 1, 2, \dots, M-1$
• 第2行：$M, M+1, M+2, \dots, 2M-1$
• $\dots$
• 第$i$行：$(i-1)M, (i-1)M+1, \dots, iM-1$

核心思路

这是一个构造题，采用分阶段修复的策略：

阶段1：修复前 $N-1$ 行

rep(i, 1, n - 1) rep(j, 1, m) if (a[i][j] != (i - 1) * m + j) {
    // 修复位置(i,j)
}

对于前 $N-1$ 行中的每个位置 $(i,j)$，如果数字不正确，就将其修正。

阶段2：修复最后一行

rep(j, 1, m) if (a[n][j] != (n - 1) * m + j) {
    // 修复最后一行第j列
}

阶段3：特殊情况处理

if (a[1][m] != m) {
    // 处理第一行最后一列的特殊情况
}

关键修复技术

情况1：目标数字在同一行

当前：数字v在(i, cy)，应该在(i, j)
操作：
1. 第i行右移(m - (cy - j))格，使v到位置j
2. 第j列下移(n-1)格，临时移走
3. 第i行左移(cy - j)格，恢复行
4. 第j列上移1格，完成修复

情况2：目标数字在同一列

当前：数字v在(cx, j)，应该在(i, j)
操作：
1. 第cx行右移1格
2. 第j列下移(cx - i)格，使v到位置(i,j)
3. 第cx行左移(m-1)格，恢复行
4. 第j列上移(n - (cx - i))格，恢复列

情况3：目标数字在其他位置

当前：数字v在(cx, cy)，应该在(i, j)
操作：
1. 第j列下移(cx - i)格，使目标行对齐
2. 第cx行移动使数字v到第j列
3. 第j列上移恢复

算法复杂度

• 时间复杂度：$O(N^2M^2)$（最坏情况）
• 空间复杂度：$O(NM)$
• 操作次数：最多 $10^5$ 步

关键技巧

1. 坐标映射：维护idx[v]和idy[v]数组，快速找到数字v的位置
2. 循环移动：利用模运算实现循环移位
3. 最小化影响：每次操作尽量不影响已修复的位置
4. 特殊情况处理：最后一行和角落位置需要特殊处理

样例验证

对于样例1：

初始：
4 2 3 0
1 5 6 7

目标：
0 1 2 3  
4 5 6 7

操作：
2 1 1  // 第1列下移1格
1 1 1  // 第1行右移1格

总结

这是一个经典的构造题，通过分阶段修复和巧妙的操作序列，将复杂问题分解为可管理的子问题。关键在于：

• 保持已修复部分不被破坏
• 利用循环移位的特性
• 处理边界情况的特殊策略