本文共 1115 字，大约阅读时间需要 3 分钟。
为了解决这个问题，我们需要计算一个N×M的农田中所有满足特定条件的正方形农田的数量。每个正方形必须满足至少一个条件：边长不同或左上角的方格不同。
我们可以使用动态规划的方法来解决这个问题。具体步骤如下：
问题分析：我们需要找到所有可能的正方形，其中每个正方形的左上角和右下角都是农田，且内部全部是农田。动态规划可以帮助我们高效地计算这些正方形的数量。
动态规划数组定义：定义一个二维数组f，其中f[i][j]表示以(i, j)为右下角的最大正方形的边长。
递推关系：对于每个位置(i, j)，如果当前方格是农田（即值为1），则f[i][j]可以通过以下公式计算：[f[i][j] = \min(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1]这表示以(i, j)为右下角的最大正方形边长，其值取决于其左边、上边和左上角的最大正方形边长。
结果计算：将所有f[i][j]的值累加，得到所有满足条件的正方形数量。
n, m = map(int, input().strip().split())grid = []for _ in range(n): line = input().strip() grid.append([c for c in line])# 初始化f数组，f[i][j]表示以(i,j)为右下角的最大正方形的边长f = [[0] * (m + 1) for _ in range(n + 1)]ans = 0for i in range(1, n + 1): for j in range(1, m + 1): if grid[i-1][j-1] == '1': f[i][j] = min(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1 ans += f[i][j] else: f[i][j] = 0print(ans)
读取输入：首先读取输入的N和M，然后读取接下来的N行数据，构建一个二维数组grid，其中grid[i][j]表示对应的方格是否为农田。
初始化数组：定义一个二维数组f，大小为(n+1)×(m+1)，初始化为0。ans数组用于存储最终结果。
遍历计算：遍历每个方格(i, j)，如果当前方格是农田，则计算f[i][j]，否则设置为0。ans累加每个方格的f[i][j]值。
输出结果：打印最终的ans值，即满足条件的正方形数量。
通过这种方法，我们可以高效地计算出所有满足条件的正方形数量。
转载地址：http://buug.baihongyu.com/