Blue Mary的战役地图

Blue Mary的战役地图

题目描述

  • BlueMary最近迷上了玩 Starcraft(星际争霸) 的 RPG 游戏。她正在设法寻找更多的战役地图以进一步提高自己的水平。
  • 由于 BlueMary 的技术已经达到了一定的高度,因此,对于用同一种打法能够通过的战役地图,她只需要玩一张,她就能了解这一类战役的打法,然后她就没有兴趣再玩儿这一类地图了。而网上流传的地图有很多都是属于同一种打法,因此 BlueMary 需要你写一个程序,来帮助她判断哪些地图是属于同一类的。
  • 具体来说,BlueMary 已经将战役地图编码为 n×n 的矩阵,矩阵的每个格子里面是一个 32 位(有符号)正整数。对于两个矩阵,他们的相似程度定义为他们的最大公共正方形矩阵的边长。两个矩阵的相似程度越大,这两张战役地图就越有可能是属于同一类的。

输入格式

  • 输入文件的第一行包含一个正整数 n。
  • 以下 n 行,每行包含 n 个正整数,表示第一张战役地图的代表矩阵。
  • 再以下 n 行,每行包含 n 个正整数,表示第二张战役地图的代表矩阵。

输出格式

  • 输出文件仅包含一行。这一行仅有一个正整数,表示这两个矩阵的相似程度。

样例输入

3
1 2 3
4 5 6
7 8 9
5 6 7
8 9 1
2 3 4

样例输出

2

数据范围与提示

  • 子矩阵:

    5 6
    8 9

    为两个地图的最大公共矩阵

    • 对于 100% 的数据 \(1\le n\le 100\)。

Solve

  • 题目大意

    • 找到最大公共子矩阵(必须为正方形)。
  • 写法类似于Hash表。

  • Hash表是将同一类的放进一个链表中,减少查找的次数。

  • 这道题可以直接将矩阵内的和当做分类的标准,这个可以通过矩阵前缀和进行 \(O(n^2)\) 的预处理,可以\(O(1)\) 的计算出来,将矩阵和相同的放在一条链中,

  • 注意事项

    1. Hash表的数量由子矩阵的数量确定,一个 n×n 的矩阵有 n×n×n 个子矩阵,head数组和链表结构体开 \(n^3\) 的就够的,模数就取数组能开下的范围内最大的质数就可以了。
    2. 本写法比较用于随机数据,因为这样分布到每条链上的个数都会很少,而对于特殊构造的数据,时间复杂度可能会退化到 \(O(n^7)\),但过本题是没问题的。
  • 详细看代码注释。

Code

#include <cstdio>
#define ll long long
using namespace std;
const int N = 105, M = 1157621;//M是105*105*105中最大质数
const int N3 = N*N*N;
int n, a[N][N], b[N][N];
ll s[2][N][N];//存前缀和
struct Node {
    int k, x, y, next;
}h[N3];//链表
int head[N3], tot;
int Ha(int k, int x, int y, int p) {//求Hash值
    x--, y--;
    return (int)(s[p][x+k][y+k] - s[p][x][y+k] - s[p][x+k][y] + s[p][x][y]) % M;//通过前缀和求期间和
}
void Add(int k, int i, int j) {//在Hash表中添加,挺像加边操作
    int ha = Ha(k, i, j, 0);
    h[++tot] = (Node) {k, i, j, head[ha]};
    head[ha] = tot;
}
bool Judge(int n, int k, int x, int y) {//判断是否相同
    if (h[n].k != k) return 0;
    for (int i = 0; i < k; ++i)
        for (int j = 0; j < k; ++j)
            if (a[h[n].x+i][h[n].y+j] != b[x+i][y+j])
                return 0;
    return 1;
}
bool Find(int k, int x, int y) {
    int ha = Ha(k, x, y, 1);
    if (!head[ha]) return 0;
    for (int i = head[ha]; i; i = h[i].next)//遍历这条链
        if (Judge(i, k, x, y)) return 1;
    return 0;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &a[i][j]), 
            s[0][i][j] = s[0][i-1][j] + s[0][i][j-1] - s[0][i-1][j-1] + a[i][j];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &b[i][j]),
            s[1][i][j] = s[1][i-1][j] + s[1][i][j-1] - s[1][i-1][j-1] + b[i][j];
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i + k - 1 <= n; ++i)
            for (int j = 1; j + k - 1 <= n; ++j)
                Add(k, i, j);//将第一个图的所有子矩阵加入
    for (int k = n; k >= 1; --k)//从大到小枚举,找到了直接输出,这个for也可以二分
        for (int i = 1; i + k - 1 <= n; ++i)
            for (int j = 1; j + k - 1 <= n; ++j)
                if (Find(k, i, j)) return printf("%d\n", k), 0;
    puts("0");
    return 0;
}
上一篇:Blue Mary开公司


下一篇:机器学习开端中的PCA算法解析——python