ABC300B Same Map in the RPG World

题意分析

给定两个大小为 $N \times M$ 的字符矩阵 $A$ 和 $B$，你可以对矩阵 $A$ 做两种循环操作：

• 循环上移 $s$ 次：将矩阵的每一行整体向上移动一格，最顶行移到最底部；
• 循环左移 $t$ 次：将矩阵的每一列整体向左移动一格，最左列移到最右边。

目标是判断是否存在某一对整数 $(s, t)$，使得对 $A$ 进行这两种循环操作之后，得到的矩阵与 $B$ 完全相同。

---

解题思路

枚举所有可能的偏移量：

由于矩阵大小为 $N \times M$，所以可能的上移次数 $s$ 为 $0$ 到 $N-1$，左移次数 $t$ 为 $0$ 到 $M-1$，共 $N \times M$ 种偏移组合。

检查某一对偏移是否满足条件：

对于任意给定的 $(s, t)$：

• 通过循环位移后的矩阵 $A'$ 中的位置 $(i,j)$，对应的是原矩阵 $A$ 的位置：
  • 行：int x = (i - s) % N，若小于 $0$ 加上 $N$ 即可。
  • 列：int y = (j - t) % N，若小于 $0$ 加上 $M$ 即可。
• 对比 $A[x][y]$ 是否等于 $B[i][j]$，只要有任意位置不等就跳出。

实现细节：

• 利用双重循环遍历所有 $s, t$；
• 对每种情况遍历所有矩阵元素检查是否一致；
• 一旦找到匹配情况立即输出 Yes；
• 所有情况都试完未匹配，则输出 No。

---

示范代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
char a[35][35], b[35][35];
bool check(int s, int t)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int x = (i - s) % n;
            if (x < 0) x += n;
            int y = (j - t) % m;
            if (y < 0) y += m;
            if (a[x][y] != b[i][j]) return 0;
        }
    }
    return 1;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> b[i][j];
    for (int s = 0; s < n; s++)
    {
        for (int t = 0; t < m; t++)
        {
            if (check(s, t)) 
            {
                cout << "Yes";
                return 0;
            }
        }
    }
    cout << "No";
    return 0;
}

---

时间复杂度分析

• 枚举所有偏移组合：$O(N \times M)$
• 对每组偏移检查整个矩阵是否匹配：$O(N \times M)$
• 总体复杂度：$O(N^2 \times M^2)$，最多约为 $30^4 = 810{,}000$，在题目数据范围内可接受。

---

总结

• 关键是通过取模实现循环的索引变换；
• 适合用来训练二维矩阵下标操作与取余技巧；
• 一种常见技巧是将所有位置的坐标转换成基于偏移的表达，便于对比。