1 条题解
-
0
主要思想是判断两个路径是否可以通过旋转操作互相转换。具体来说,给定两个由方向指令(字符 'a'-'f')组成的路径,判断它们在经过某种旋转后是否完全相同。使用数组 nextvec 将字母 a 到 f 映射为六个方向的位移向量(右、右上、上、左、左下、下)。计算路径 stra 经过的所有点坐标,存储在 pa 数组中,并添加起点 (0,0)。路径预处理:对 pa 数组按 x 升序、y 升序排序,消除顺序影响。旋转与起点调整验证:旋转:尝试所有 6 种可能的方向旋转(每个方向旋转 60 度)。起点调整:对每个旋转后的路径,尝试以 pa 中的每个点为起点,生成新路径 pb。匹配验证:将生成的 pb 数组排序后与 pa 比较,若完全相同则匹配成功。
#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; struct Point2D { int x, y; }; int nextvec[6][2] = { {1, 0}, {1, 1}, {0, 1}, {-1, 0}, {-1, -1}, {0, -1} }; char stra[1024]; char strb[1024]; char buff[1024]; Point2D pa[2000]; Point2D pb[2000]; bool cmp(const Point2D& a, const Point2D& b) { if (a.x == b.x) return a.y < b.y; return a.x < b.x; } int main() { int N; scanf("%d%*c", &N); // %*c 消耗行末换行符 while (N--) { memset(pa, 0, sizeof(pa)); memset(pb, 0, sizeof(pb)); // 使用 fgets 读取输入,并指定缓冲区大小和输入流 fgets(stra, sizeof(stra), stdin); fgets(strb, sizeof(strb), stdin); fgets(buff, sizeof(buff), stdin); // 移除字符串末尾的换行符(如果存在) stra[strcspn(stra, "\n")] = '\0'; strb[strcspn(strb, "\n")] = '\0'; buff[strcspn(buff, "\n")] = '\0'; int lena = strlen(stra); int lenb = strlen(strb); if (lena == 0 && lenb == 0) { printf("true\n"); continue; } else if (lena != lenb) { printf("false\n"); continue; } int x = 0, y = 0; for (int i = 0; i < lena; i++) { int dir = stra[i] - 'a'; x += nextvec[dir][0]; y += nextvec[dir][1]; pa[i].x = x; pa[i].y = y; } pa[lena].x = 0; pa[lena].y = 0; sort(pa, pa + lena + 1, cmp); int flag = 0; for (int dirCLT = 0; dirCLT < 6; dirCLT++) { for (int startID = 0; startID <= lena; startID++) { x = pa[startID].x; y = pa[startID].y; for (int i = 0; i < lenb; i++) { int dir = (strb[i] - 'a' + dirCLT) % 6; x += nextvec[dir][0]; y += nextvec[dir][1]; pb[i].x = x; pb[i].y = y; } pb[lenb].x = pa[startID].x; pb[lenb].y = pa[startID].y; sort(pb, pb + lenb + 1, cmp); int tflag = 0; for (int i = 0; i <= lena; i++) { if (pa[i].x != pb[i].x || pa[i].y != pb[i].y) { tflag = 1; break; } } if (!tflag) { flag = 1; break; } } if (flag) break; } printf("%s\n", flag ? "true" : "false"); } return 0; }
- 1
信息
- ID
- 958
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者