我要评论题目描述
Blue Mary最近迷上了玩Starcraft(星际争霸) 的RPG游戏。她正在设法寻找更多的战役地图以进一步提高自己的水平。
由于Blue Mary的技术已经达到了一定的高度,因此，对于用同一种打法能够通过的战役地图，她只需要玩一张，她就能了解这一类战役的打法，然后她就没有兴趣再玩儿这一类地图了。而网上流传的地图有很多都是属于同一种打法，因此Blue Mary需要你写一个程序，来帮助她判断哪些地图是属于同一类的。
具体来说，Blue Mary已经将战役地图编码为的矩阵，矩阵的每个格子里面是一个位（有符号）正整数。对于两个矩阵，他们的相似程度定义为他们的最大公共正方形矩阵的边长。两个矩阵的相似程度越大，这两张战役地图就越有可能是属于同一类的。
输入格式
第一行包含一个正整数。
以下行，每行包含个正整数，表示第一张战役地图的代表矩阵。
再以下行，每行包含个正整数，表示第二张战役地图的代表矩阵。
输出格式
仅包含一行。这一行仅有一个正整数，表示这两个矩阵的相似程度。
样例
输入
3
1 2 3
4 5 6
7 8 9
5 6 7
8 9 1
2 3 4
输出
2
数据范围与提示
。
分析
读完题，不难想到的暴力解法。（枚举正方形长度枚举正方形一左上顶点枚举正方形二左上顶点判断是否相等）这样肯定会。
不妨使用，用的时间复杂度判断两正方形是否相等。可正方形的函数怎么设计呢？其实有很多种方法。使用无符号长整形（自然溢出），对于每一个数，计算。最后即为整个正方形的值。时间复杂度：
代码
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstring>
#define uLL unsigned long long
using 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;
}
本文地址：https://blog.csdn.net/Clever_Hard/article/details/107899470
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论