luogu#P4380. [USACO18OPEN] Multiplayer Moo S

    ID: 8407 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>并查集枚举暴力随机贪心随机化USACO2018

[USACO18OPEN] Multiplayer Moo S

题目描述

奶牛们提出了一款创新性的新游戏,令人惊讶的是她们给这款游戏取了个最没创意的名字:“Moo”。
Moo 游戏在一个由 N×NN \times N 个正方形格子组成的棋盘上进行。一头奶牛可以通过大叫一声“哞!”然后把她的数字编号写在这个格子里来占有这个格子。

在游戏结束时,每个格子中都包含一个数。此时,如果一头奶牛创建了一个由连通的格子组成的领域,且该领域的大小不小于其他所有领域,那么这头奶牛就获胜。一个“领域”被定义为一些具有相同数字编号的格子,其中每个格子都直接与另一个同一领域中的格子通过上、下、左或右相邻(对角线不计)。

由于以单牛形式进行游戏有点无聊,奶牛们也对双牛组队进行游戏感兴趣。同一队的两头奶牛可以创建一个领域,但现在领域中的格子可以属于队伍中的任一头奶牛。

给定游戏棋盘的最终状态,请帮助奶牛们计算:

  1. 任何单头奶牛占有的最大领域包含的格子数量。
  2. 任何两头奶牛组成的队伍占有的最大领域包含的格子数量。

注意,两头奶牛占有的领域必须同时包含队伍中两头奶牛的编号,不能仅仅包含一头。

输入格式

输入的第一行包含 NN1N2501 \leq N \leq 250)。接下来的 NN 行,每行包含 NN 个整数(每个整数在 01060 \ldots 10^6 之间),描述棋盘的最终状态。棋盘中至少出现两种不同的数字。

输出格式

输出的第一行描述任何单头奶牛占有的最大领域大小,第二行描述任何两头奶牛的队伍占有的最大领域大小。

4
2 3 9 3
4 9 9 1
9 9 1 7
2 1 1 9
5
10

提示

在这个例子中,单头奶牛占有的最大领域是由五个 99 组成的。如果编号为 1199 的奶牛组队,她们可以形成一个大小为 1010 的领域。

供题:Brian Dean