Skip to content

1060: L-Bots

题目

题目描述

你的面前有 $R$ 行(从上至下标号为 $1\cdots R$)$C$列(从左至右标号为 $1\cdots C$)的一个网格。每个格子里都有一个 L 形机器人(L-Bot),且位于第 $r$ 行、第 $c$ 列的机器人有着贡献值$P_{rc}$(可以是负值)。

每个机器人有着两个夹角为 $90$ 度的连接口,通过这两个连接口可以至多和另两个机器人相连。机器人可以旋转到如下四种朝向:

如果有两个相邻机器人的连接口对上了,它们就组成了“一对”,这能让你获得价值相当于这两个机器人 $P_{rc}$ 之和的金币。如果两个机器人 $P_{rc}$ 之和为负,你将获得 $0$ 个金币。

因为每个机器人有两个连接口,所以一个机器人最多能处在两个“一对”中。

现在你可以随意旋转每个机器人到最优的朝向。请问最多能获得多少金币?

输入格式

第一行为两个整数,分别代表 $R$ 与 $C$。

接下来为 $R$ 行,每行为 $C$ 个整数,第 $r$ 行的第 $c$ 个数为 $P_{rc}$ 的值。

输出格式

输出包括一个整数,为能获得的金币的最大值。

样例输入

Sample Input 1

c++ 1 7 15 -5 100 -40 10 10 10

Sample Input 2

c++ 2 2 100 100 100 100

Sample Input 3

c++ 3 3 -10 4 -10 3 1 -10 6 2 8

样例输出

Sample Output 1

c++ 115

Sample Output 2

c++ 800

Sample Output 3

c++ 28

数据范围

|子任务|分值|附加条件| |---|---|---| |$1$|$35$|$R, C \leq 3$| |$2$|$15$|$R = 1$| |$3$|$20$|$R = 2$| |$4$|$22$|$P_{i, j} > 0$| |$5$|$8$|无特殊限制|

对于所有测试点有 $1 \leq R,C \leq 1000, -1000 \leq P_{i,j} \leq 1000$。

样例解释

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!