K15887 正方形（sqr） (100分) 题目描述 求一个n行m列的矩形网格中，包括多少个正方形（每个格子都是完全相同的小正方形格子）。 如2*3的矩形网格中，边长为1的正方形有6个，边长为2的正方形有2个，共包括8个正方形。c++入门代码怎么写

K15887 的题目要求计算给定大小的矩阵中所有可能存在的正方形的数量。正方形的边长可以是1到n*m之间的任意整数。为了求解这个问题，你可以采用动态规划的方法。以下是简单的 C++ 入门代码示例：

#include <iostream>
using namespace std;

int countSquares(int n, int m) {
    // 初始化一个二维数组来存储每个位置上最大包含的正方形边长
    int dp[n][m];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            // 如果当前位置是边界，则最多能形成边长为1的正方形
            if (i == 0 || j == 0 || i == n - 1 || j == m - 1)
                dp[i][j] = 1;
            else {
                // 否则，dp[i][j]等于它上面、左面以及对角线上的较小边长加1
                dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
        }
    }

    int total = 0;
    // 计算并累加所有正方形的数量
    for (int k = 1; k <= n && k <= m; ++k) {
        total += (n - k + 1) * (m - k + 1);
    }

    return total;
}

int main() {
    int n, m;
    cout << "请输入矩阵的行数和列数: ";
    cin >> n >> m;
    cout << "该矩阵中共有 " << countSquares(n, m) << " 个正方形。" << endl;
    return 0;
}

这个程序首先初始化一个动态规划表 `dp`，然后通过遍历每个单元格，更新其能够形成的正方形的最大边长。最后，统计所有可能的边长，乘以其对应的面积（`(n-k+1)*(m-k+1)`），并将它们加起来得到总正方形数。