#P1324. Exca王者之剑
Exca王者之剑
题目描述
给定一个 的网格,每个格子中有一颗宝石,矩阵中的数表示该宝石的价值。你可以任选起点,从第 秒开始行动。每秒依次执行:
- 取走当前格子中尚未消失的宝石。
- 如果当前为偶数秒,当前格子上下左右四个相邻格子中尚未取走的宝石全部消失。
- 移动到上下左右的一个相邻格子,或者留在原地;不能离开网格。
每颗宝石只能取得一次。求能够取得的宝石总价值的最大值。
输入格式
第一行两个整数 ,。接下来 行每行 个整数,为宝石价值。
输出格式
一个整数,表示最大总价值。
样例输入
2 2
1 2
2 1
样例输出
4
来源
2007 年 Amber 国家队论文《最小割模型在信息学竞赛中的应用》第 5.4.2 节。
当前数据版本约定
本站当前评测数据保证宝石价值为 内的整数。