1567: [JSOI2008]Blue Mary的战役地图
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1011 Solved: 578
[Submit][Status][Discuss]
Description
Blue Mary最近迷上了玩Starcraft(星际争霸) 的RPG游戏。她正在设法寻找更多的战役地图以进一步提高自己的水平。 由于Blue Mary的技术已经达到了一定的高度,因此，对于用同一种打法能够通过的战役地图，她只需要玩一张，她就能了解这一类战役的打法，然后她就没有兴趣再玩儿这一类地图了。而网上流传的地图有很多都是属于同一种打法，因此Blue Mary需要你写一个程序，来帮助她判断哪些地图是属于同一类的。 具体来说，Blue Mary已经将战役地图编码为n*n的矩阵，矩阵的每个格子里面是一个32位（有符号）正整数。对于两个矩阵，他们的相似程度定义为他们的最大公共正方形矩阵的边长。两个矩阵的相似程度越大，这两张战役地图就越有可能是属于同一类的。
Input
第一行包含一个正整数n。 以下n行，每行包含n个正整数，表示第一张战役地图的代表矩阵。 再以下n行，每行包含n个正整数，表示第二张战役地图的代表矩阵。
Output
仅包含一行。这一行仅有一个正整数，表示这两个矩阵的相似程度。
Sample Input
3
1 2 3
4 5 6
7 8 9
5 6 7
8 9 1
2 3 4
1 2 3
4 5 6
7 8 9
5 6 7
8 9 1
2 3 4
Sample Output
2
HINT
样例解释：
子矩阵：
5 6
8 9
为两个地图的最大公共矩阵
约定：
n<=50
题目大意：求两个矩形的最大公共子正方形的边长
题解：O(n^7)暴力...从大到小枚举边长
代码：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int n;int a[55][55],b[55][55];inline int read(){ ???char ch=getchar();int x=0,f=1; ???for(;!isdigit(ch);ch=getchar())if(ch==‘-‘)f=-1; ???for(;isdigit(ch);ch=getchar())x=x*10+ch-‘0‘; ???return x*f;}int main(){ ???scanf("%d",&n); ???for(int i=1;i<=n;i++) ????for(int j=1;j<=n;j++) ?????a[i][j]=read(); ???for(int i=1;i<=n;i++) ????for(int j=1;j<=n;j++) ?????b[i][j]=read(); ???for(int i=n;i>=1;i--){ ???????for(int k=1;k<=n-i+1;k++){ ???????????for(int p=1;p<=n-i+1;p++){ ???????????????for(int q=1;q<=n-i+1;q++){ ???????????????????for(int y=1;y<=n-i+1;y++){ ???????????????????????bool flag=true; ???????????????????????for(int j=0;j<i;j++){ ???????????????????????????for(int l=0;l<i;l++){ ???????????????????????????????if(a[k+j][p+l]!=b[q+j][y+l]){ ???????????????????????????????????flag=false; ???????????????????????????????????break; ???????????????????????????????} ???????????????????????????} ???????????????????????????if(flag==false)break; ???????????????????????} ???????????????????????if(flag){ ???????????????????????????printf("%d\n",i); ???????????????????????????return 0; ???????????????????????} ???????????????????} ???????????????} ???????????} ???????} ???} ???return 0;}BZOJ 1567: [JSOI2008]Blue Mary的战役地图
原文地址：http://www.cnblogs.com/zzyh/p/7593691.html