1 条题解
-
0
题解
本题要求判断一个给定的正方形网格是否能通过仅旋转其各同心环来变成排序好的网格。排序好的网格指的是$N \times N$的网格,其元素为从$1$到$N^2$的整数,按行主序排列。
思路分析
- 将给定网格和目标排序网格(即从1到$N^2$顺序排列)都按环的顺序展开成多个一维数组(每个环一个数组)。
- 每个环是一条闭合的环状序列,旋转相当于对数组进行循环移动。
- 对每一层环,判断给定网格该环数组是否可以通过旋转变为目标网格该环的数组。
- 如果所有环均满足条件,则输出“YES”,否则输出“NO”。
关键步骤
-
构造目标网格:$ans[i][j] = (i-1)*N + j$,即按行主序填充数字。
-
提取每个环的元素:
-
从外层环开始,依次向内层环提取元素,顺序为:
- 上边行,从左到右
- 右边列,从上到下
- 下边行,从右到左
- 左边列,从下到上
-
这四部分拼接成一个环的数组。
-
-
判断旋转匹配:
- 对给定网格的该环序列
huan[i]
,在目标网格的对应环序列anshuan[i]
中寻找一个位置,使得从该位置起旋转后的序列与huan[i]
完全相同。 - 如果找不到匹配,说明该环无法通过旋转达到排序状态,输出“NO”。
- 对给定网格的该环序列
-
循环判断所有环,如果所有环均满足旋转条件,输出“YES”。
代码实现
#include <iostream> #include <cstdio> using namespace std; int a[1005][1005]; // 输入的网格 int ans[1005][1005]; // 目标排序网格 int huan[1005][4000]; // 提取的当前环元素(给定网格) int anshuan[1005][4000]; // 提取的目标环元素 int main(void) { int n; int case_t = 1; while (~scanf("%d", &n) && n) // 读入测试用例直到N=0结束 { // 输入网格 for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]); // 构造目标排序网格 int cnt = 1; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) ans[i][j] = cnt++; int tmp = (n + 1) / 2; // 环数 int t1 = 1, t2 = n, t3 = 1, t4 = n; // 四个边界索引 int flag = 0; // 标记是否能匹配 for (int i = 1; i <= tmp; i++) { int cnt1 = 0, cnt2 = 0; // 提取第i层环的元素(给定网格) for (int j = t1; j <= t2; j++) huan[i][cnt1++] = a[t1][j]; t1++; for (int j = t1; j <= t4; j++) huan[i][cnt1++] = a[j][t4]; t4--; for (int j = t4; j >= t3; j--) huan[i][cnt1++] = a[t2][j]; t2--; for (int j = t2; j >= t1; j--) huan[i][cnt1++] = a[j][t3]; t3++; // 提取第i层环的元素(目标网格) t1--; t4++; t2++; t3--; cnt2 = 0; for (int j = t1; j <= t2; j++) anshuan[i][cnt2++] = ans[t1][j]; for (int j = t1 + 1; j <= t4; j++) anshuan[i][cnt2++] = ans[j][t4]; for (int j = t4 - 1; j >= t3; j--) anshuan[i][cnt2++] = ans[t2][j]; for (int j = t2 - 1; j >= t1 + 1; j--) anshuan[i][cnt2++] = ans[j][t3]; t1++; t4--; t2--; t3++; // 判断huan[i]是否是anshuan[i]的旋转版 int k = 0; for (; k < cnt2; k++) if (huan[i][0] == anshuan[i][k]) break; bool matched = false; for (int start = 0; start < cnt2; start++) { bool ok = true; for (int j = 0; j < cnt2; j++) { if (huan[i][j] != anshuan[i][(start + j) % cnt2]) { ok = false; break; } } if (ok) { matched = true; break; } } if (!matched) { flag = 1; break; } } if (flag) printf("%d. NO\n", case_t++); else printf("%d. YES\n", case_t++); } return 0; }
复杂度分析
- 对于每个测试用例,提取每层环的时间为$O(N)$,环数约为$O(N/2)$,总共$O(N^2)$。
- 对每个环进行旋转匹配判断,最多$O(N)$个元素,循环检测$O(N)$,整体仍是$O(N^2)$。
- 该复杂度在$N \leq 1000$范围内可接受。
总结
本题的核心是将二维网格的旋转问题转换为一维数组的循环匹配问题。通过分层提取环并逐个判断是否是目标环的旋转变体,即可判断整个网格是否可以通过旋转环排序完成。
- 1
信息
- ID
- 2510
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 4
- 已通过
- 1
- 上传者