logo AlgoBeat OnlineJudge
登录 注册

#214415. [JOI2023 预选赛 R2] 填充 / Painting

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

JOI 君正在玩一个绘图软件。

在该绘图软件中,可以在一个 列的矩形网格上绘制图案。每个网格单元格都有一个颜色,颜色由 之间的整数表示。

从上往下第 行()、从左往右第 列()的单元格称为单元格 。当前,单元格 的颜色为

从单元格 出发,反复移动到与其相邻的、颜色相同的单元格,所能到达的所有单元格的集合,称为单元格 的“区域”。

该绘图软件具有“填充”功能。使用该功能时,指定某个单元格 )和颜色 ),则该单元格 所在区域内的所有单元格颜色将全部变为

JOI 君将选择某个单元格 和颜色 ,并恰好使用一次“填充”功能。使用“填充”功能后,单元格 所在区域内的单元格数量即为 JOI 君的得分。

请编写一个程序,求出 JOI 君可能获得的最大得分。

输入格式

输入数据按以下格式给出:

输出格式

在一行内输出 JOI 君可能获得的最大得分。

样例

样例输入 1

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

样例输出 1

9

样例输入 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

样例输入 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

数据范围与提示

样例 1 解释

在初始状态下,单元格 所在区域包含的单元格有 ,共 4 个。因此,若指定单元格 和颜色 并使用“填充”功能,这 4 个单元格的颜色将变为 ,如图所示。

使用“填充”功能后,单元格 所在区域包含的单元格变为 ,共 9 个。因此,JOI 君的得分为

无法使 JOI 君的得分达到 或以上,故应输出

该输入满足子任务 2、3、5 的约束。

:::align{center} :::

数据范围

  • )。
  • 所有输入值均为整数。

子任务

  1. (9 分)
  2. (32 分),且 )。
  3. (18 分)
  4. (10 分))。
  5. (31 分)无额外约束。

翻译由 Qwen3-235B 完成。