图片解码系统中的坐标映射与矩阵变换技术

1. 图片解码问题概述

这道题目来自曙梦OJ的CSP202512C题，要求我们实现一个图片解码系统。题目给定一个N×N的字符矩阵（N≤400），其中包含有效像素和填充的'?'字符。我们需要对这个矩阵执行一系列操作后，输出裁剪掉'?'边界后的有效图片。

核心操作包括两种：

1. 区域翻转：对指定矩形区域进行水平或垂直翻转
2. 区域旋转：对指定正方形区域进行90°、180°或270°旋转

题目难点在于需要支持操作的回溯——所有操作以栈的形式给出，需要按从后往前的顺序执行。这就要求我们设计高效的坐标映射系统，避免直接操作数据带来的性能问题。

2. 解题思路与架构设计

2.1 核心问题分析

这道题的核心挑战在于：

1. 大规模矩阵操作（400×400）的效率
2. 旋转操作带来的坐标变换复杂性
3. 操作回溯带来的执行顺序反转
4. 最终需要正确识别并裁剪边界

2.2 解决方案选型

经过分析，我们采用"虚拟坐标系统+物理存储分离"的架构：

cpp复制int deg = 0; // 当前全局旋转角度
char jz[N][N]; // 物理存储

// 虚拟坐标到物理坐标的映射
int hash1(int i, int j) {
    if(deg == 0) return i;
    else if(deg == 90) return j;
    else if(deg == 180) return z-i+1;
    else return z-j+1;
}

这种设计的优势在于：

1. 物理存储保持不变，避免频繁数据移动
2. 通过deg变量记录当前旋转状态
3. 所有操作都通过虚拟坐标系统进行
4. 执行效率高，单次操作时间复杂度为O(k²)，k为操作区域边长

3. 关键算法实现细节

3.1 坐标映射系统

坐标映射是整个解决方案的核心，我们设计了两个哈希函数：

cpp复制int hash1(int i, int j) {
    int d = deg;
    if(d == 0) return i;
    else if(d == 90) return j;
    else if(d == 180) return z-i+1;
    else return z-j+1;
}

int hash2(int i, int j) {
    int d = deg;
    if(d == 0) return j;
    else if(d == 90) return z-i+1;
    else if(d == 180) return z-j+1;
    else return i;
}

这两个函数共同完成了虚拟坐标到物理坐标的转换。这种设计使得无论矩阵如何旋转，我们都能通过调整deg值来保持正确的坐标映射。

3.2 翻转操作实现

翻转操作分为水平翻转和垂直翻转：

cpp复制void fz(int u, int d, int l, int r, int o) {
    if(o == -1) { // 水平翻转
        for(int i=u; i<=d; i++) {
            int left = l, right = r;
            for(int j=1; j<=(r-l+1)/2; j++) {
                swap(get_val(i, left), get_val(i, right));
                left += 1, right -= 1;
            }
        }
    } else { // 垂直翻转
        for(int j=l; j<=r; j++) {