给定一个 amxn 矩形，其中有多少个正方形？
例如：
输入： m = 2, n = 2
输出： 5
有 4 个尺寸为 1x1 的正方形 + 1 个尺寸为 2x2 的正方形。
输入： m = 4, n = 3
输出： 20
有 12 个尺寸为 1x1 的正方形 +
6 个尺寸为 2x2 的正方形 +
2 个尺寸为 3x3 的正方形。
我们先针对 m = n 即正方形解决这个问题：
对于 m = n = 1，输出：1
对于 m = n = 2，输出：4 + 1 [ 4 个大小为 1×1 + 1 个大小为 2×2 ] 对于
m = n = 3，输出：9 + 4 + 1 [ 9 个大小为 1×1 + 4 个大小为 2×2 + 1 个大小为 3×3 ]
对于 m = n = 4，输出 16 + 9 + 4 + 1 [ 16 个大小为 1×1 + 9 个大小为 2×2 + 4 个大小为 3×3 + 1 个大小为 4×4 ]
通常，它似乎是 n^2 + (n-1)^2 + … 1 = n(n+1)(2n+1)/6
当 m 可能不等于 n 时，让我们解决这个问题：假设 m <= n
从上面的解释中，我们知道 amxm 矩阵的方格数为 m(m+1)(2m+1)/6
当我们添加一列时会发生什么，即 mx（m+1）矩阵中的方格数是多少？
当我们添加一列时，增加的方块数为 m + (m-1) + … + 3 + 2 + 1
[ m 个大小为 1×1 的方块 + (m-1) 个大小为 2×2 的方块 + … + 1 个大小为 mxm 的方块 ]
等于 m(m+1)/2
因此，当我们添加 (nm) 列时，增加的方格总数为 (nm)*m(m+1)/2。
因此，方格总数为 m(m+1)(2m+1)/6 + (nm)*m(m+1)/2。
使用相同的逻辑，我们可以证明 n <= m 的情况。
因此，总的来说，
当 n 为较大维度时，总方块数 = mx (m+1) x (2m+1)/6 + (nm) xmx (m+1)/2
利用上述逻辑，我们也可以证明正方形中的正方形数量为 n(n+1)(2n+1)/6
以下是上述公式的实现：
// C# program to count squares in a rectangle
// of size m x n
using System;
class GFG {
// Returns count of all squares in a
// rectangle of size m x n
static int countSquares(int m, int n)
{
// If n is smaller, swap m and n
if (n < m)
{
// swap(m,n)
int temp = m;
m = n;
n = temp;
}
// Now n is greater dimension, apply
// formula
return m * (m + 1) * (2 * m + 1) / 6 +
(n - m) * m * (m + 1) / 2;
}
// Driver method
public static void Main()
{
int m = 4, n = 3;
Console.WriteLine("Count of squares is "
+ countSquares(m, n));
}
}
//This code is contributed by vt_m.
输出 ：
方格数为 20
时间复杂度： O（1）
辅助空间： O(1)
替代解决方案：
取 m = 2，n = 3；
边长为 1 的正方形的数量为 6，因为存在两种情况，第一种情况是沿水平方向的边长为 1 单位的正方形（2），第二种情况是沿垂直方向的边长为 1 单位的正方形（3）。这样一来，共有 2*3 = 6 个正方形。
当边长为 2 个单位时，第一种情况是水平方向只有一处有 2 个单位边长的正方形，第二种情况是垂直方向有两处有 2 个单位边长的正方形。因此，正方形的数量=2
因此我们可以推断，大小为 1*1 的正方形的数量为 m*n。大小为 2*2 的正方形的数量为 (n-1)(m-1)。因此，大小为 n 的正方形的数量为 1*(m-n+1)。
总方块数的最终公式为n*(n+1)(3m-n+1)/6。
// C# program to count squares
// in a rectangle of size m x n
using System;
class GFG
{
// Returns count of all squares
// in a rectangle of size m x n
static int countSquares(int m, int n)
{
// If n is smaller, swap m and n
if (n < m)
{
int temp = m;
m = n;
n = temp;
}
// Now n is greater dimension,
// apply formula
return n * (n + 1) * (3 * m - n + 1) / 6;
}
// Driver Code
public static void Main(String[] args)
{
int m = 4;
int n = 3;
Console.Write("Count of squares is " +
countSquares(m, n));
}
}
// This code is contributed by Rajput-Ji
输出 ：
方格数为 20
时间复杂度： O（1）
辅助空间： O(1)
感谢 Pranav 提供这个替代解决方案。
方法＃3：使用循环
此方法通过遍历从 1 到 m 和 n 中的最小值的所有可能的正方形尺寸，并累加可放入矩形的每种尺寸的正方形数量，来计算给定大小为 mxn 的矩形中的正方形数量。
算法
1. 将计数器变量初始化为 0。
2. 遍历所有可能的正方形大小，即从 1 到 min(m, n)。
3. 对于每个正方形大小，计算可以形成的正方形数量。
4. 将此计数添加到计数器变量。
5. 返回最终计数。
using System;
public class CountSquaresInGrid
{
public static int CountSquares(int m, int n)
{
int count = 0;
// Iterate through the side lengths of squares
// from 1 to the minimum of m and n.
for (int i = 1; i <= Math.Min(m, n); i++)
{
// For each side length 'i', calculate
// the number of squares that can fit in the grid.
count += (m - i + 1) * (n - i + 1);
}
return count;
}
public static void Main(string[] args)
{
int m = 4;
int n = 3;
// Call the function to count squares in the grid and print the result.
int result = CountSquares(m, n);
Console.WriteLine(result);
}
}
输出：
20
时间复杂度：O(m * n * min(m, n))
空间复杂度：O(1)
如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。
介绍，附pdf)
