本文共 2467 字，大约阅读时间需要 8 分钟。

题目描述

Blue Mary最近迷上了玩Starcraft(星际争霸) 的RPG游戏。她正在设法寻找更多的战役地图以进一步提高自己的水平。

由于Blue Mary的技术已经达到了一定的高度,因此，对于用同一种打法能够通过的战役地图，她只需要玩一张，她就能了解这一类战役的打法，然后她就没有兴趣再玩儿这一类地图了。而网上流传的地图有很多都是属于同一种打法，因此Blue Mary需要你写一个程序，来帮助她判断哪些地图是属于同一类的。

具体来说，Blue Mary已经将战役地图编码为$n\times n$的矩阵，矩阵的每个格子里面是一个$32$位（有符号）正整数。对于两个矩阵，他们的相似程度定义为他们的最大公共正方形矩阵的边长。两个矩阵的相似程度越大，这两张战役地图就越有可能是属于同一类的。

输入格式

第一行包含一个正整数$n$。
以下$n$行，每行包含$n$个正整数，表示第一张战役地图的代表矩阵。
再以下$n$行，每行包含$n$个正整数，表示第二张战役地图的代表矩阵。

输出格式

仅包含一行。这一行仅有一个正整数，表示这两个矩阵的相似程度。

样例

输入

31 2 34 5 67 8 95 6 78 9 12 3 4

输出

2

数据范围与提示

$n\le 50$。

分析

读完题，不难想到$O(n^7)$的暴力解法。（枚举正方形长度$O(n)$$\times$枚举正方形一左上顶点$O(n^2)$$\times$枚举正方形二左上顶点$O(n^2)$$\times$判断是否相等$O(n^2)$）这样肯定会$TLE$。
不妨使用$Hash$，用$O(1)$的时间复杂度判断两正方形是否相等。可正方形的$Hash$函数怎么设计呢？其实有很多种方法。$e.g.$使用无符号长整形（自然溢出），对于每一个数$x$，计算$sum=sum\times 131+x$。最后$sum$即为整个正方形的$Hash$值。时间复杂度：$O(n^5)$

代码

#include <cstdio>#include <algorithm>#include <cmath>#include <climits>#include <cstring>#define uLL unsigned long longusing namespace std;const int MAXN = 55;int n, a[MAXN][MAXN], b[MAXN][MAXN], ans;uLL Hash[MAXN][MAXN][MAXN], Hash_[MAXN][MAXN][MAXN];//Hash[k][i][j](Hash_[k][i][j])表示左上角为(i, j)，边长为k的正方形的Hash值void Map_() {   //初始化Hash值	uLL sum, sum_;	for(int i = 1; i <= n; i ++) {   //长度		for(int j = 1; j <= (n - i + 1); j ++) {   			for(int k = 1; k <= (n - i + 1); k ++) {   //正方形一左上角				sum = 0; sum_ = 0;				for(int l = j; l <= (j + i - 1); l ++) {   					for(int m = k; m <= (k + i - 1); m ++) {   //正方形二左上角						sum = sum * 131 + a[l][m];						sum_ = sum_ * 131 + b[l][m];					}				}				Hash[i][j][k] = sum;				Hash_[i][j][k] = sum_;			}		}	}	return;}int Find_Ans() {   //暴力枚举	for(int i = n; i >= 1; i --) {   //从大到小（找到可行的就可以退出）		for(int j = 1; j <= (n - i + 1); j ++) {   			for(int k = 1; k <= (n - i + 1); k ++) {   				for(int l = 1; l <= (n - i + 1); l ++) {   					for(int m = 1; m <= (n - i + 1); m ++) {   						if(Hash[i][j][k] == Hash_[i][l][m]) return i;					}				}			}		}	}	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]);		}	}	for(int i = 1; i <= n; i ++) {   		for(int j = 1; j <= n; j ++) {   			scanf("%d", &b[i][j]);		}	}	Map_();	ans = Find_Ans();	printf("%d", ans);	return 0;}

转载地址：http://axve.baihongyu.com/