方格取数问题： 在一个有m×n个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。 输入：第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。 输入样例： 3 3 1 2 3 3 2 3 2 3 1 输出：程序运行结束时，将取数的最大总和输出；用python编写

以下是 Python 3 的参考代码：

m, n = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
dp = [[0] * n for _ in range(m)]
for i in range(m-1, -1, -1):
    for j in range(n-1, -1, -1):
        if i+2 < m and j+1 < n:
            dp[i][j] = max(dp[i][j], a[i][j]+dp[i+2][j+1])
        if i+2 < m and j-1 >= 0:
            dp[i][j] = max(dp[i][j], a[i][j]+dp[i+2][j-1])
        if i+1 < m and j+2 < n:
            dp[i][j] = max(dp[i][j], a[i][j]+dp[i+1][j+2])
        if i+1 < m and j-2 >= 0:
            dp[i][j] = max(dp[i][j], a[i][j]+dp[i+1][j-2])
for i in range(m-1, -1, -1):
    for j in range(n-1, -1, -1):
        if i+1 < m and j+2 < n:
            dp[i][j] = max(dp[i][j], a[i][j]+dp[i+1][j+2])
        if i+1 < m and j-2 >= 0:
            dp[i][j] = max(dp[i][j], a[i][j]+dp[i+1][j-2])
        if i+2 < m and j+1 < n:
            dp[i][j] = max(dp[i][j], a[i][j]+dp[i+2][j+1])
        if i+2 < m and j-1 >= 0:
            dp[i][j] = max(dp[i][j], a[i][j]+dp[i+2][j-1])
print(dp[0][0])

时间复杂度为 $O(mn)$。