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)\) 的计算出来,将矩阵和相同的放在一条链中,
-
注意事项
- Hash表的数量由子矩阵的数量确定,一个 n×n 的矩阵有 n×n×n 个子矩阵,head数组和链表结构体开 \(n^3\) 的就够的,模数就取数组能开下的范围内最大的质数就可以了。
- 本写法比较用于随机数据,因为这样分布到每条链上的个数都会很少,而对于特殊构造的数据,时间复杂度可能会退化到 \(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;
}