← 返回题目列表

AtCoder · joi2023_yo2_c

C. 绘画

中文机器翻译题面 查看原题

配点: 100 点

問題文

JOI君正在玩画图软件。

在绘图软件中,垂直 H 行,横 W 您可以在列中的矩形网格上绘图。每个方格都有指定的颜色,颜色为 1 以上 10^9 由以下整数表示。

从上面 i 行目 (1 \leqq i \leqq H),从左起 j 列目 (1 \leqq j \leqq W) 它被称为 (i,j) 。目前,大众 (i,j) 的颜色是 A_{i,j} 。

质量 重复从 (i,j) 到与边缘接触的方块的移动,并且 (i,j) 是方块的集合,无需进入不同颜色的方块即可移动。质量 重复从 (i,j) 的面积 它被称为。

绘图软件包括填充 有一个名为的函数。该功能可以让您 (x,y) (1 \leqq x \leqq H,1 \leqq y \leqq W)和颜色 c (1 \leqq c \leqq 10^9) 指定质量 (x,y) 区域中包含的所有方块的颜色都是 更改为 c 。

JOI君是某个方块 (x,y) 和颜色 选择 c ,指定正方形和颜色,然后准确填充。 使用 1 次。使用填充后的正方形 区域 (x,y) 中包含的方格数就是JOI君的分数。

编写一个程序来找出 JOI-kun 可达到的最高分数。

制約

  • 1 \leqq H \leqq 500.
  • 1 \leqq W \leqq 500.
  • 1 \leqq A_{i,j} \leqq 10^9 (1 \leqq i \leqq H,1 \leqq j \leqq W).
  • 所有输入值都是整数。

小課題

  1. (9 点) H = 1.
  2. (32 点) H \leqq 30,W \leqq 30,A_{i,j} \leqq 5 (1 \leqq i \leqq H,1 \leqq j \leqq W).
  3. (18 点) H \leqq 30,W \leqq 30.
  4. (10 点) A_{i,j} \leqq 2 (1 \leqq i \leqq H,1 \leqq j \leqq W).
  5. (31 点)没有额外的限制。

入力

输入按照以下格式给出。

H W
A_{1,1} A_{1,2} \cdots A_{1,W}
A_{2,1} A_{2,2} \cdots A_{2,W}
\vdots
A_{H,1} A_{H,2} \cdots A_{H,W}

出力

JOI君可达到的最高分数。 在 1 行输出。


入力例 1

4 4
1 2 3 1
2 2 3 1
1 2 3 1
3 3 2 2

出力例 1

9

一开始,质量 (2,2) 区域中包含的单元格是 (1,2), (2,1), (2,2), (3,2) 的 4 。因此,质量 如果指定 (2,2) 和颜色 选择 3 并使用 fill,这些 4 方块的颜色 3 。

使用填充后,质量 将会有 (2,2) 区域中包含的单元格是 (1,2), (1,3), (2,1), (2,2), (2,3), (3,2), (3,3), (4,1), (4,2) 的 9 件。因此,JOI君的分数是 9 变为。

JOI君的分数 10 或更多是不可能的,所以9 。

此输入是一个小作业 2, 3, 5 满足约束。


入力例 2

2 10
1 2 2 1 3 3 3 3 1 1
1 1 1 1 1 1 1 3 3 3

出力例 2

18

此输入是一个小作业 2, 3, 5 满足约束。


入力例 3

5 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

出力例 3

25

此输入是一个小作业 2, 3, 4, 5 满足约束。