题目名称 3045. [USACO Open18] Multiplayer Moo
输入输出 multimoo_silver_18open.in/out
难度等级 ★★
时间限制 1000 ms (1 s)
内存限制 256 MB
测试数据 10 简单对比
题目来源 程远洋 2018-11-03
开放分组 全部用户
提交状态
分类标签
通过:7, 提交:59, 通过率:11.86%
GravatarConsciousness.M 100 0.131 s C++
GravatarBenjamin 100 0.139 s C++
Gravatar雾茗 100 0.234 s C++
Gravatar橡桦 100 0.780 s C++
GravatarShallowDream雨梨 100 0.781 s C++
GravatarShallowDream雨梨 100 0.785 s C++
Gravatarleon 100 0.798 s C++
Gravatar倾城倾国的金克斯美丽女神最漂亮 100 1.103 s C++
Gravatar梦那边的美好ETMN 100 3.556 s C++
Gravatar梦那边的美好ETMN 100 3.687 s C++
关于 Multiplayer Moo 的讨论
不加剪枝倒数第二个点T,加了剪枝最后一个点莫名输入都错了,,真烦。
最后算是打表一个点,这题真jb拉低我正确率,最后还没写对。。。。。。。。。。。
顺便膜神犇hxf~~~~~~~~~~~
自己总共交了41遍。。。。
成功把这题通过率拉到4%~~~~~~~~~~
GravatarShallowDream雨梨
2018-11-05 19:50 1楼

3045. [USACO Open18] Multiplayer Moo

★★   输入文件:multimoo_silver_18open.in   输出文件:multimoo_silver_18open.out   简单对比
时间限制:1 s   内存限制:256 MB

【题目描述】


奶牛们提出了一款创新性的新游戏,惊讶的是她们给这款游戏取了个最没创意的名字:“Moo”。


Moo游戏在一个由N×N个正方形格子组成的棋盘上进行,一头奶牛可以通过大叫一声“哞!”然后把她的数字编号写在这个格子里来占有这个格子。


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


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


给定游戏棋盘的最终状态,请帮助奶牛们计算任何单头奶牛拥有的最大的领域包含的格子数量,以及任何两头奶牛组成的队伍占有的最大的领域包含的格子的数量。两头奶牛占有的领域必须要同时包含队伍中两头奶牛的编号,不能仅仅包含一头。


【输入格式】


输入的第一行包含N(1≤N≤250)。下面N行,每行包含N个整数(每个都在0…10^6之间),描述棋盘的最终状态。棋盘中至少出现两种不同的数字。


【输出格式】


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


【样例输入】

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

【样例输出】

5
10

【数据规模】

50%数据N<=100;

100%数据N<=250;

【提示】

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

【来源】

USACO 2018 OPEN CONTEST Silver Problem 3

供题:Brian Dean