bzoj#P1567. [JSOI2008]Blue Mary的战役地图

[JSOI2008]Blue Mary的战役地图

题目描述

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

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

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

输入格式

第一行包含一个正整数 nn

以下 nn 行,每行包含 nn 个正整数,表示第一张战役地图的代表矩阵。

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

输出格式

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

样例输入

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

样例输出

2

提示

样例解释

5 6
8 9

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

数据范围

对于 100100% 的数据:n50n\leq 50,且地图中的每一个数都在 int 范围内。