题目翻译
伊沃有一个 N×N 的表格,表格中按行主序填入了 1 到 N² 的整数。可以对表格执行以下操作:
旋转一行 —— 将一行中的所有单元格向右旋转,最后一列的数字移到第一列
旋转一列 —— 将一列中的所有单元格向下旋转,最后一行的数字移到第一行
伊沃偶尔想把数字 X 移到单元格 (R, C),操作步骤如下:
当 X 不在第 C 列时,旋转它所在的行
当 X 不在第 R 行时,旋转它所在的列
伊沃想依次移动 K 个数字。请编写程序计算每次移动所需的旋转次数。
输入格式:
第一行包含两个整数 N (2 ≤ N ≤ 10000) 和 K (1 ≤ K ≤ 1000),表示表格大小和移动次数
接下来 K 行,每行包含三个整数 X (1 ≤ X ≤ N²)、R 和 C (1 ≤ R, C ≤ N),描述一次移动。伊沃按给出的顺序执行移动
输出格式:
输出 K 行,每行对应一次移动所需的旋转次数
解题思路
核心分析
初始位置计算:
数字 X 在初始表格中的位置可以通过行主序规则计算:
行号:(X-1) // N + 1
列号:(X-1) % N + 1
旋转次数计算:
行旋转:将数字从当前列移到目标列 C 需要 (C - 当前列 + N) % N 次旋转
列旋转:将数字从当前行移到目标行 R 需要 (R - 当前行 + N) % N 次旋转
位置更新:
当旋转一行或一列时,该行 / 列中所有数字的位置都会发生变化,需要同步更新
算法步骤
读取所有移动操作,计算每个数字的初始位置
对每个移动操作:
计算行旋转次数并更新该行所有数字的位置
计算列旋转次数并更新该列所有数字的位置
输出总旋转次数(行旋转 + 列旋转)
代码实现
python也是有的
复杂度分析
时间复杂度:O (K²),其中 K 是移动次数。对于每个移动,我们最多需要更新 K 个数字的位置
空间复杂度:O (K),用于存储 K 个数字的位置信息
如果这篇题解帮你解决了问题,别忘了点个赞👍让我知道!