洛谷：P4924：魔法少女小Scarlet

Posted on 4th Dec 2025

题目

题目

分析

本题有很大部分和P1205：方块转换类似，都需要对一个矩阵进行顺时针/逆时针转90度的操作。不同之处在于，本题只要转一部分，但是代码是可以借鉴的。

回顾P1205的旋转算法

void rotate90(char src[N][N], char dst[N][N])
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            dst[j][n - i - 1] = src[i][j];
        }
    }
}

在本题中，显然受影响（需要旋转）的矩阵范围变了，从0 -> n变成-r -> +r，因此坐标计算有了变化。我们可以沿用P1205的绝对坐标转换，但可以更方便地用相对坐标转换。

对于以(x,y)为中心、半径为r的子矩阵：

子矩阵范围：[x-r, x+r] × [y-r, y+r]
子矩阵大小：(2r+1) × (2r+1)
子矩阵的"左上角"在(x-r, y-r)

将绝对坐标(i,j)转换为子矩阵内的相对坐标：

local_i = i - (x-r)
local_j = j - (y-r)

应用P01205的旋转公式（子矩阵大小是2r+1）：

new_local_i = local_j
new_local_j = (2r+1-1) - local_i = 2r - local_i

转回绝对坐标：

new_i = new_local_i + (x-r) = local_j + (x-r) = (j-(y-r)) + (x-r) = x-r+j-y+r = x+j-y
new_j = new_local_j + (y-r) = (2r-local_i) + (y-r) = 2r-(i-(x-r)) + (y-r) = 2r-i+x-r+y-r = x+y-i

最终公式：

// 顺时针 90度
matrix[x + j - y][x + y - i] = temp[i][j];

和我们的代码完全一样。

逆时针旋转的转换公式可以类似推导，不再重复。

有了这两个公式后，其他代码就简单了。

答案

Solution

思考

下面给出一些实现细节、边界情况与可选优化，供读者深入思考：

边界与坐标系：题中子矩阵以(x,y)为中心、半径r，范围是[x-r, x+r] × [y-r, y+r]。实现时要明确使用的是0基还是1基下标，且在计算目标索引前务必保证下标落在矩阵合法范围内（避免负数或越界）。
局部临时区分原/目标矩阵：在一次旋转操作内，如果直接在原矩阵上就地写入目标位置，会造成后续映射读取到已被修改过的值，导致错误。常见做法有两种：
- 把整个原矩阵或要旋转的(2r+1)×(2r+1)子矩阵先拷贝到临时数组temp，再按映射公式把temp写回到matrix；
- 或者按“层（layer）”的方式在原矩阵上就地旋转（每次沿四边移动并用一个临时变量保存被替代的值），这种方法在空间上更省（几乎\(O(1)\)额外空间），但代码更繁琐，需要小心索引与循环边界。
复杂度说明：对半径为r的子矩阵做一次完整的90°旋转，其工作量为\(O((2r+1)^2)\)，若有q次操作，总复杂度大致为\(O(\sum (2r_i+1)^2)\)。在r较大或q较多时会比较耗时，必要时考虑如下优化：
- 若题目允许批量操作合并或有结构化规律，可以尝试合并旋转或延迟执行；
- 若只需查询而不需频繁修改，可考虑维护变换历史并对查询时计算映射；不过这些策略都复杂且依赖题目具体约束。
数值与类型安全：在计算新坐标时使用诸如x + j - y、x + y - i等表达式，确保中间计算不会越界（对于本题常规约束int足够），并尽量写成x + (j - y)这样的形式以减少阅读误解。
特殊情况测试：实现后请针对如下用例测试以防漏掉边缘情况：
- r = 0（半径为 0，不发生变化）；
- 子矩阵贴边或角落（部分或全部落在边界）；
- 多次对重叠区域的连续旋转，验证是否按预期顺序生效（若采用 temp 拷贝法，应能自然得到正确顺序）；
代码风格建议：
- 将坐标映射与边界检查封装成小函数（例如 map_clockwise(i,j,x,y,r)），主逻辑只负责遍历和读写；
- 在单次旋转中推荐使用一个大小为 (2r+1)×(2r+1) 的临时缓冲区来存放被读出的原值（代码更直观、更不易出错）。

这些思路既能帮助你写出正确的实现，也有助于在遇到性能或边界问题时快速定位与改进。

Previous Next

Table of Contents

题目

分析

回顾P1205的旋转算法

答案

思考