#P1324. Exca王者之剑

    ID: 336 传统题 1000ms 512MiB 尝试: 868 已通过: 357 难度: 7 上传者: 标签>CF2300提高+/省选-奇偶性分析最大权独立集二分图建模补集转化顶点覆盖最小割建模最大流最小割定理Dinic闭合子图问题

Exca王者之剑

题目描述

给定一个 N×MN\times M 的网格,每个格子中有一颗宝石,矩阵中的数表示该宝石的价值。你可以任选起点,从第 00 秒开始行动。每秒依次执行:

  1. 取走当前格子中尚未消失的宝石。
  2. 如果当前为偶数秒,当前格子上下左右四个相邻格子中尚未取走的宝石全部消失。
  3. 移动到上下左右的一个相邻格子,或者留在原地;不能离开网格。

每颗宝石只能取得一次。求能够取得的宝石总价值的最大值。

输入格式

第一行两个整数 N,MN,M,1≤N,M≤1001\le N,M\le100。接下来 NN 行每行 MM 个整数,为宝石价值。

输出格式

一个整数,表示最大总价值。

样例输入

2 2
1 2
2 1

样例输出

4

来源

2007 年 Amber 国家队论文《最小割模型在信息学竞赛中的应用》第 5.4.2 节。

当前数据版本约定

本站当前评测数据保证宝石价值为 [0,999][0,999] 内的整数。