📝 题目大意

给定两个 $N \times N$ 的 01 矩阵 $A$ 和 $B$。可以对 $A$ 进行若干次 90° 顺时针旋转（最多 3 次，因为 4 次回到原位），判断是否存在一种旋转方式，使得 $A$ 中所有为 $1$ 的位置在 $B$ 中也为 $1$（即 $A$ 的 $1$ 是 $B$ 的 $1$ 的子集）。

💡 解题思路

1. 题目分析：$N \leq 100$，数据范围很小，旋转操作只有至多 4 种不同的状态（0°, 90°, 180°, 270°），直接枚举即可。时间复杂度完全允许。

2. 算法推导：

   • 定义矩阵旋转公式（1-indexed）：顺时针旋转 90° 后，新矩阵的 $(i, j)$ 位置等于原矩阵的 $(N+1-j, i)$ 位置。
   • 在 work() 中（std.cpp），每次旋转后检查当前矩阵 $c$ 是否满足条件：对于所有 $c_{i,j}=1$ 的位置，是否都有 $b_{i,j}=1$；若满足则输出 Yes 并退出。
   • 检查完毕后，将 $c$ 顺时针旋转 90° 得到下一个状态。
   • 额外做了一个循环检测：若旋转后的 $c$ 与原始 $a$ 完全相同，说明已经旋转了 360°（回到起点），此时直接输出 No 退出，避免无限循环。
   • 主函数中循环调用 work() 最多 4 次，若全部不满足则输出 No。

3. 边界与细节：

   • 当 $A$ 全为 $0$ 时，无论 $B$ 为何值都满足条件，应输出 Yes（因为没有任何 $A_{i,j}=1$ 需要检查）。
   • 旋转公式 c[n+1-j][i] 是 1-indexed 的写法，对应 0-indexed 的 c[n-1-j][i]，注意不要混淆。
   • 循环检测不是必须的，但可以提前终止，属于优化。

⏱️ 复杂度分析

• 时间复杂度：$O(N^2)$。最多 4 次旋转，每次旋转和检查都是 $O(N^2)$。
• 空间复杂度：$O(N^2)$。需要存储 $A$、$B$ 以及旋转用的临时矩阵。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
#define N 110
int n, a[N][N], b[N][N], c[N][N], d[N][N];

// 检查当前旋转状态是否满足条件，并旋转到下一个状态
void work()
{
    // 检查：对于所有 c[i][j] == 1 的位置，b[i][j] 也必须为 1
    bool book = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (c[i][j] == 1 && b[i][j] == 0) book = 0; // 存在 A 为 1 但 B 为 0，不满足
        }
    }
    if (book) // 当前旋转状态满足条件
    {
        puts("Yes");
        exit(0);
    }

    // 顺时针旋转 90°：d[i][j] = c[n+1-j][i]
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            d[i][j] = c[n + 1 - j][i];
        }
    }
    // 将旋转结果复制回 c
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            c[i][j] = d[i][j];
        }
    }

    // 循环检测：若旋转后等于原始矩阵 a，说明已经转了一圈（360°），无需继续
    book = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (a[i][j] != c[i][j]) book = 0;
        }
    }
    if (book)
    {
        puts("No");
        exit(0);
    }
}

int main()
{
    scanf("%d", &n);
    // 读入矩阵 A，同时初始化 c = A
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &a[i][j]);
            c[i][j] = a[i][j];
        }
    }
    // 读入矩阵 B
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &b[i][j]);
        }
    }

    // 枚举 4 种旋转状态（0°, 90°, 180°, 270°）
    for (int t = 1; t <= 4; t++) work();

    puts("No"); // 所有旋转都不满足
    return 0;
}