图片解码

GitHub跳转原题关系图 Canvas 关系图返回列表

逆序还原旋转与翻转操作，用四种逻辑方向表示整图旋转，避免重复搬运大矩阵。

OJ: shumeng

题目 ID: CSP202512C

难度:未知

标签:模拟矩阵坐标映射逆操作

日期: 2026-07-31 16:22

形式化题目

一张图片被补成 $Z \times Z$ 方阵后，依次进行 $t$ 次加密操作，每次为局部顺时针旋转（附整图逆时针旋转 $r$ 次）或局部上下/左右翻转。给定加密后的方阵和密钥序列（记录每次操作参数），还原原始图片并输出其真实尺寸。

思路

加密操作全部可逆，因此从最后一次操作开始逆序处理。

逆序撤销操作

旋转加密：先撤销整图旋转（把逻辑视图方向回退），再撤销局部正方形的旋转。
翻转加密：上下、左右翻转都是自身的逆操作，直接反向搬回。

用逻辑方向避免整图搬运

整图旋转如果直接搬动 $Z^2$ 个字符会超时。改为维护"逻辑坐标到存储坐标"的四种方向映射，整图旋转只是修改一个枚举方向，实际矩阵不动。局部操作边长最多 10，读入临时数组后按方向映射写回即可。

还原原始尺寸

全部操作逆序完成后，扫描逻辑视图中非 ? 的最大行列，即为原始图片的尺寸。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:22
 * update_at: 2026-08-17 23:06
 */
#include <bits/stdc++.h>
using namespace std;

int z;                  // 加密方阵边长
int orientation;        // 当前整图旋转方向：0/1/2/3 分别表示 0/90/180/270 度
vector<string> picture; // 存储矩阵（以逻辑视图为准）

// 逻辑坐标 (row,col) 到存储坐标 (mapped_row,mapped_col) 的映射，随整图方向变化
void map_position(int row, int col, int &mapped_row, int &mapped_col) {
    if (orientation == 0) {
        mapped_row = row;
        mapped_col = col;
    } else if (orientation == 1) {
        mapped_row = z - 1 - col;
        mapped_col = row;
    } else if (orientation == 2) {
        mapped_row = z - 1 - row;
        mapped_col = z - 1 - col;
    } else {
        mapped_row = col;
        mapped_col = z - 1 - row;
    }
}

// 读取逻辑坐标 (row,col) 处的字符
char get_cell(int row, int col) {
    int mapped_row, mapped_col;
    map_position(row, col, mapped_row, mapped_col);
    return picture[mapped_row][mapped_col];
}

// 写入逻辑坐标 (row,col) 处的字符
void set_cell(int row, int col, char value) {
    int mapped_row, mapped_col;
    map_position(row, col, mapped_row, mapped_col);
    picture[mapped_row][mapped_col] = value;
}

// 撤销一次局部旋转：把 top,left 处边长 length 的正方形逆时针转回。
// 当前整图方向已提前由调用者更新，这里以逻辑视图操作即可
void undo_rotation(int top, int left, int length, int degree) {
    char old_value[10][10];
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < length; j++) {
            old_value[i][j] = get_cell(top + i, left + j);
        }
    }

    int times = degree / 90;
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < length; j++) {
            int old_row, old_col;
            if (times == 1) {
                old_row = j;
                old_col = length - 1 - i;
            } else if (times == 2) {
                old_row = length - 1 - i;
                old_col = length - 1 - j;
            } else {
                old_row = length - 1 - j;
                old_col = i;
            }
            set_cell(top + i, left + j, old_value[old_row][old_col]);
        }
    }
}

// 撤销一次局部翻转：direction=1 上下翻转，direction=-1 左右翻转。
// 翻转是自身的逆操作，直接反向搬回即可
void undo_flip(int top, int bottom, int left, int right, int direction) {
    int height = bottom - top + 1;
    int width = right - left + 1;
    char old_value[10][10];
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            old_value[i][j] = get_cell(top + i, left + j);
        }
    }
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            int old_row = direction == 1 ? height - 1 - i : i;
            int old_col = direction == -1 ? width - 1 - j : j;
            set_cell(top + i, left + j, old_value[old_row][old_col]);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> z;
    picture.resize(z);
    for (int i = 0; i < z; i++) cin >> picture[i];
    int key_length;
    cin >> key_length;
    vector<int> key(key_length);
    for (int i = 0; i < key_length; i++) cin >> key[i];

    int operations = key[0];
    orientation = 0;
    for (int operation = operations - 1; operation >= 0; operation--) {
        int position = 1 + operation * 6;
        int type = key[position];
        if (type == 1) {
            int top = key[position + 1] - 1;
            int left = key[position + 2] - 1;
            int length = key[position + 3];
            int degree = key[position + 4];
            int whole_rotations = key[position + 5];
            orientation = (orientation + whole_rotations) % 4;
            undo_rotation(top, left, length, degree);
        } else {
            int top = key[position + 1] - 1;
            int bottom = key[position + 2] - 1;
            int left = key[position + 3] - 1;
            int right = key[position + 4] - 1;
            int direction = key[position + 5];
            undo_flip(top, bottom, left, right, direction);
        }
    }

    int last_row = -1;
    int last_col = -1;
    for (int i = 0; i < z; i++) {
        for (int j = 0; j < z; j++) {
            if (get_cell(i, j) != '?') {
                last_row = max(last_row, i);
                last_col = max(last_col, j);
            }
        }
    }
    cout << last_row + 1 << ' ' << last_col + 1 << '\n';
    for (int i = 0; i <= last_row; i++) {
        for (int j = 0; j <= last_col; j++) cout << get_cell(i, j);
        cout << '\n';
    }
    return 0;
}

复杂度

每次局部操作处理至多 $10 \times 10$ 个字符，总时间复杂度 $O(t \cdot 100 + Z^2)$ ，空间复杂度 $O(Z^2)$ 。

总结

对经常整图旋转的矩阵，把旋转记录在坐标映射中而不是真的搬运数据，能省下大量时间。局部操作规模很小，直接读临时数组再写回即可。注意逆序撤销时先处理整图方向、再处理局部旋转。

题目来自第 40 次 CSP 认证 T3，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 1.5 秒

空间限制： 512 MB

题目背景

西西艾弗岛上的居民经常使用 InkGraph 系统来对自己的图片进行加密操作。加密方在加密图片时，将图片输入该系统后可以得到一份系统文件与一个对应的密钥；如果想要获取图片的原始信息，接收方需要获取该系统文件与对应的密钥并将它们输入系统，经系统解码后便能获得原始图片。

具体来说，一张图片可以由一个 $n\times m$ 的字符表格 $P$ 来表示，其中位于从上向下数第 $i$ 行，从左向右数第 $j$ 列的字符可以用 $P_{i,j}$ （ $1\leq i\leq n,1\leq j\leq m$ ）来表示。这些字符中仅含有大小写字母、数字和下划线。新加入开发团队的小 C 学习了这个系统的加密方法。

加密步骤

加密方在加密一张图片 $P$ 前，需预先设定一个整数规模参数 $Z$ （ $1\leq Z\leq 400$ ）。在导入图片 $P$ 后，系统会自动在右下方用字符 ? 将其补齐成一张 $Z\times Z$ 的正方形图片 $A_0$ 。一个对 $2\times 3$ 图片加密，并设置 $Z=4$ 的例子如下：

系统此时会向用户请求加密次数 $t$ ，满足 $1\leq t\leq 5\times 10^4$ 。然后系统会从图片 $A_0$ 开始，进行 $t$ 次加密操作。具体来说，第 $i$ 次加密操作的输入为 $A_{i-1}$ ，输出为 $A_i$ 。 $t$ 次加密操作结束后，系统会将加密后的最终结果图 $A_t$ 与代表加密过程的密钥（一个整数序列 $K$ ）输出到加密方获取的系统文件中。在加密过程开始前，系统先向空的密钥 $K$ 中添加一个整数 $t$ ，即设置 $K_1=t$ 。

对于第 $i$ 次加密操作，系统会先自动选择一个加密类型 $op_i\in\{1,2\}$ 。

如果 $op_i=1$ ，那么第 $i$ 次加密是一次旋转加密。系统会生成一个五维整数向量 $(u_i,v_i,L_i,d_i,r_i)$ ，满足 $1\leq u_i\leq Z,1\leq v_i\leq Z,1\leq L_i\leq \min\{Z,10\},u_i+L_i-1\leq Z,v_i+L_i-1\leq Z,d_i\in\{90,180,270\},0\leq r_i\leq 3$ ，然后抽取出图片 $A_{i-1}$ 的从第 $u_i$ 到第 $u_i+L_i−1$ 行，第 $v_i$ 到第 $v_i+L_i−1$ 列的大小为 $L_i\times L_i$ 的正方形子表 $B$ ，将 $B$ 顺时针旋转 $d_i$ 度（角度制）后放在原来的位置上（字符本身不会被旋转）；旋转完成后，再对这张图整体进行 $r_i$ 次逆时针旋转 $90$ 度的操作，从而得到本次加密的结果图 $A_{i}$ 。将上例图片作为 $A_{i-1}$ 进行一次 $(2,2,3,90,1)$ 的旋转加密的过程如下，得到本次加密操作的结果图片 $A_{i}$ ：

在本次加密完成后，系统会在密钥序列 $K$ 的后方依次追加 $op_i,u_i,v_i,L_i,d_i,r_i$ 这 $6$ 个数。例如若上述加密过程为第一次加密，密钥序列 $K$ 应形如 $\{t,1,2,2,3,90,1\}$ 。

如果 $op=2$ ，那么第 $i$ 次加密是一次翻转加密：系统会生成一个五维整数向量 $(u_i,d_i,l_i,r_i,o_i)$ ，满足 $1\leq u_i\leq d_i\leq Z,1\leq l_i\leq r_i\leq Z,1\leq d_i-u_i+1\leq\min\{Z,10\},1\leq r_i-l_i+1\leq\min\{Z,10\},o_i\in\{-1,1\}$ ，然后抽取出当前图片 $A_{i-1}$ 的第 $u_i$ 到第 $d_i$ 行，第 $l_i$ 到第 $r_i$ 列的大小为 $(d_i−u_i+1)\times(r_i−l_i+1)$ 的矩形子表 $B$ ；当 $o_i=1$ 时，将 $B$ 上下翻转；当 $o_i=-1$ 时，将 $B$ 左右翻转（字符本身不会被翻转），然后放在原来的位置上，从而得到本次加密的结果图 $A_{i}$ 。将上例图片作为 $A_{i-1}$ 进行一次 $(2,3,1,4,-1)$ 的翻转加密的过程如下，得到本次加密的结果图片 $A_{i}$ ：

在本次加密完成后，系统会在密钥序列 $K$ 的后方依次追加 $op_i,u_i,d_i,l_i,r_i,o_i$ 这 $6$ 个数。例如若上述加密过程为第一次加密，密钥序列 $K$ 应形如 $\{t,2,2,3,1,4,-1\}$ 。

全部 $t$ 次加密过程结束后，最终结果图 $A_t$ 和密钥 $K$ 会被输出至系统文件中。

题目描述

小 C 对 InkGraph 系统的解码方法非常感兴趣，想要上手编写这个解码的程序。换句话说，现在他获得了一份系统文件，含有加密的最终结果图 $A_t$ 与对应的密钥序列 $K$ ，他的程序需要能够还原出加密方导入的原始的图片 $P$ 。现在，请你帮他完成这个任务。

输入格式

从标准输入读入数据。

输入的第一行是一个正整数 $Z$ 。保证 $Z$ 不小于加密方输入图片的长和宽，也即加密程序能够正常运作；

接下来的 $Z$ 行为最终的结果图片 $A_t$ 。保证每行恰有 $Z$ 个字符，且输入的字符仅包含大小写字母、数字、下划线和问号。

接下来输入一行一个正整数 $k$ ，表示密钥 $K$ 的长度；然后下一行输入 $k$ 个由空格分隔的整数，表示密钥 $K$ 。

输出格式

输出到标准输出。

第一行输出用空格分隔的两个整数 $n$ 和 $m$ ，表示还原出的图片 $P$ 的宽度与长度。

接下来输出 $n$ 行，每行 $m$ 个字符，仅含有大小写字母、数字和下划线，表示原本的图片。

input1

1
2
3
4
5
6
74
?Nk?
??F?
??C?
C1??
13
2 1 2 2 3 90 1 2 2 3 1 3 -1

output1

1
2
32 3
CCF
1Nk

样例 1 解释

样例中系统进行了 $2$ 次加密，原始图片 $A_0$ 如案例所示。第一次加密为旋转加密，过程如案例中所示；第二次加密为翻转加密，其生成的五元向量参数为 $(2,3,1,3,-1)$ 。

样例 2

见题目文件区的 2.in 与 2.ans。

样例 2 解释

该样例中的数据满足 $op_i=2$ 。

样例 3

见题目文件区的 3.in 与 3.ans。

子任务

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	约束
1	25	保证 $op_i=2$ 且 $Z\le 10$
2	25	保证 $op_i=2$
3	25	保证 $Z\le 10$
4	25	保证 $Z\le 400$

图片解码

目录

形式化题目

思路

逆序撤销操作

用逻辑方向避免整图搬运

还原原始尺寸

代码

复杂度

总结