Multiplayer Moo

题目描述

奶牛们想出了一个富有创意的新游戏，却出人意料地取了一个最不富有创意的名字："Moo"。 游戏在一个 $N \times N$ 的方格网格上进行。奶牛通过大喊一声 "moo!" 并在格子里写下自己的数字 ID 来占领一个格子。 在游戏结束时，每个格子里都包含一个数字。此时，如果某头奶牛创建了一个连通格子区域，其大小至少与任何其他区域一样大，那么她就赢得游戏。“区域”被定义为一组 ID 数相同的格子，其中区域内的每个格子都与同一区域中的某个格子在上、下、左或右方向直接相邻（对角不算）。 由于单独玩有些无聊，奶牛们也对两两组队感兴趣。由两头奶牛组成的队伍也可以像之前一样创建一个区域，但此时区域中的格子可以属于队伍中的任意一头奶牛。 给定游戏棋盘的最终状态，请帮助奶牛们计算：任意单头奶牛所拥有的最大区域包含的格子数，以及任意两头奶牛组队能够占领的最大区域包含的格子数。两牛队伍占领的区域只有在同时包含这两头奶牛的 ID（而不仅仅包含其中一头）时才计数。

输入格式

第一行输入包含 $N$（$1 \leq N \leq 250$）。接下来的 $N$ 行每行包含 $N$ 个整数（每个都在范围 $0 \ldots 10^6$ 内），描述棋盘的最终状态。棋盘上至少会出现两个不同的 ID 数字。

输出格式

输出第一行应给出任意单头奶牛占领的最大区域大小，第二行应给出任意由两头奶牛组成的队伍占领的最大区域大小。

4
2 3 9 3
4 9 9 1
9 9 1 7
2 1 1 9

5
10

提示

在这个例子中，单头奶牛的最大区域由 5 个数字 9 组成。如果 ID 为 1 和 9 的奶牛组队，她们可以形成一个大小为 10 的区域。 题目致谢：Brian Dean

标签: USACO|2018|Silver

来源

USACO|2018|Silver