30160 - 方格取数问题
时间限制 : 1 秒
内存限制 : 128 MB
有一个 m 行 n 列的方格图，每个方格中都有一个正整数。现要从方格中取数，使任意两个数所在方格没有公共边，且取出的数的总和最大，请求出最大的和。
输入
第一行是两个用空格隔开的整数，分别代表方格图的行数 m 和列数 n。第 2 到第 (m + 1) 行，每行 n 个整数，第 (i + 1) 行的第 j 个整数代表方格图第 i 行第 j 列的的方格中的数字 a_{i, j}。
输出
输出一行一个整数，代表和最大是多少。
样例
输入
3 3 1 2 3 3 2 3 2 3 1
输出
11
提示
对于 100\% 的数据，保证 1 \leq n, m \leq 100，1 \leq a_{i, j} \leq 10^5。提示：请注意输入的第一行先读入 m 再读入 n。
来源
网络流与线性规划24题