#P12328. [蓝桥杯 2023 省 Java B] 合并区域

[蓝桥杯 2023 省 Java B] 合并区域

题目背景

本题测试数据可能较水,仅供参考。

题目描述

小蓝在玩一款种地游戏。现在他被分配给了两块大小均为 N×NN \times N 的正方形区域。这两块区域都按照 N×NN \times N 的规格进行了均等划分,划分成了若干块面积相同的小区域,其中每块小区域要么是岩石,要么就是土壤,在垂直或者水平方向上相邻的土壤可以组成一块土地。现在小蓝想要对这两块区域沿着边缘进行合并,他想知道合并以后可以得到的最大的一块土地的面积是多少(土地的面积就是土地中土壤小区域的块数)?

在进行合并时,小区域之间必须对齐。可以在两块方形区域的任何一条边上进行合并,可以对两块方形区域进行 9090 度、180180 度、270270 度、360360 度的旋转,但不可以进行上下或左右翻转,并且两块方形区域不可以发生重叠。

输入格式

第一行一个整数 NN 表示区域大小。

接下来 NN 行表示第一块区域,每行 NN 个值为 0011 的整数,相邻的整数之间用空格进行分隔。值为 00 表示这块小区域是岩石,值为 11 表示这块小区域是土壤。

再接下来 NN 行表示第二块区域,每行 NN 个值为 0011 的整数,相邻的整数之间用空格进行分隔。值为 00 表示这块小区域是岩石,值为 11 表示这块小区域是土壤。

输出格式

一个整数表示将两块区域合并之后可以产生的最大的土地面积。

4
0 1 1 0
1 0 1 1
1 0 1 0
1 1 1 0
0 0 1 0
0 1 1 0
1 0 0 0
1 1 1 1
15

提示

样例说明

第一张图展示了样例中的两块区域的布局。第二张图展示了其中一种最佳的合并方式,此时最大的土地面积为 1515

评测用例规模与约定

  • 对于 30%30\% 的数据,1N51 \leq N \leq 5
  • 对于 60%60\% 的数据,1N151 \leq N \leq 15
  • 对于 100%100\% 的数据,1N501 \leq N \leq 50