1 条题解

  • 0
    @ 2025-5-25 18:19:04

    主要思想是判断两个路径是否可以通过旋转操作互相转换。具体来说,给定两个由方向指令(字符 '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
    上传者