C++程序检查矩阵的所有行是否是彼此的循环旋转

背景

在矩阵中，如果两行之间可以通过旋转得到彼此，那么我们称这两行是循环旋转的。如果一整个矩阵中的所有行都是彼此的循环旋转，那么我们就可以说这是一个循环旋转矩阵。此时，我们需要编写一个C++程序去判断一个给定的矩阵是否为循环旋转矩阵。

实现方法

为了判断矩阵是否为循环旋转矩阵，我们可以按照以下步骤进行：

按照行的字典序从小到大排序，将矩阵变成按照行字典序排序后的新矩阵。(注意不要改变原有矩阵)
以每一行为起点，逐次旋转该行，在排序后的矩阵中搜索旋转后是否存在该行的循环旋转行。
如果所有行的循环旋转行都存在，则该矩阵为循环旋转矩阵，否则不是。

接下来我们来看看代码实现。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// 旋转一行并返回一个字符串
string rotate(string s)
{
    string res;
    int n = s.size();
    res.resize(n);
    for (int i = 0; i < n; i++)
        res[(i + 1) % n] = s[i];
    return res;
}

// 判断两行是否循环旋转，是返回true,否则返回false
bool isSame(string s1, string s2)
{
    if (s1.size() != s2.size())
        return false;
    string temp = s1;
    for (int i = 0; i < s1.size(); i++)
    {
        temp = rotate(temp);
        if (temp == s2)
            return true;
    }
    return false;
}

// 判断矩阵是否为循环旋转矩阵
bool isCycleMatrix(vector<string>& matrix)
{
    int n = matrix.size();
    vector<string> matrixCopy = matrix;  // 拷贝排序后的矩阵，不影响原矩阵
    sort(matrixCopy.begin(), matrixCopy.end());  // 按行字典序排序

    // 遍历矩阵中所有行
    for (int i = 0; i < n; i++)
    {
        bool flag = false;
        // 在排序后的矩阵中搜索第i行的循环旋转行是否存在
        for (int j = 0; j < n; j++)
            if (isSame(matrixCopy[j], matrix[i]))  // 找到了
            {
                flag = true;
                break;
            }
        // 如果第i行的循环旋转行不存在，则该矩阵不是循环旋转矩阵
        if (!flag)
            return false;
    }
    // 所有行的循环旋转行都存在，则该矩阵是循环旋转矩阵
    return true;
}

int main()
{
    int n;
    cin >> n;
    vector<string> matrix(n);
    for (int i = 0; i < n; i++)
        cin >> matrix[i];
    if (isCycleMatrix(matrix))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}