A2131. 方格取数问题
编程题
省选/NOI-
知识点
题目描述
有一个 $m$ 行 $n$ 列的方格图，每个方格中都有一个正整数。现要从方格中取数，使任意两个数所在方格没有公共边，且取出的数的总和最大，请求出最大的和。
输入格式
第一行是两个用空格隔开的整数，分别代表方格图的行数 $m$ 和列数 $n$。
第 $2$ 到第 $(m + 1)$ 行，每行 $n$ 个整数，第 $(i + 1)$ 行的第 $j$ 个整数代表方格图第 $i$ 行第 $j$ 列的的方格中的数字 $a_{i, j}$。
第 $2$ 到第 $(m + 1)$ 行，每行 $n$ 个整数，第 $(i + 1)$ 行的第 $j$ 个整数代表方格图第 $i$ 行第 $j$ 列的的方格中的数字 $a_{i, j}$。
输出格式
输出一行一个整数，代表和最大是多少。
输入输出样例
输入 #1
3 3 1 2 3 3 2 3 2 3 1
输出 #1
11
说明/提示
**数据规模与约定**
对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 100$，$1 \leq a_{i, j} \leq 10^5$。
**提示**
请注意输入的第一行先读入 $m$ 再读入 $n$。
对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 100$，$1 \leq a_{i, j} \leq 10^5$。
**提示**
请注意输入的第一行先读入 $m$ 再读入 $n$。