A27206. 正方形的数量
填空题
较难
知识点
题目描述
正方形的数量
题目描述
在一个神奇的王国里，有一块n行m列的格子地板。每个格子都是一个正方形，里面藏着一个秘密。小男孩阿力得到了一张古老的地图，上面标注了这些格子的谜题和宝藏。每天放学后，阿力都会来到这片地板上解开一个新的谜题。有时是数学问题，有时是历史故事，还有时是自然现象。随着他不断探索，他不仅找到了许多宝藏，还学到了无数知识。最终，阿力成为了村里最聪明的小孩，而那片格子地板也成了他心中永远的冒险乐园。阿力想知道格子地板里包含多少个正方形，他需要想出一个高效的办法。
输入
输入只有一行，两个整数n m，中间用空格隔开，代表格子地板大小为n行m列。保证 n和 m 均为不超过 100 的正整数。
输出
输出只有一行，一个整数，代表格子地板里包含多少个正方形。
样例：
输入
2 4输出
11参考答案
//方法1：
#include<bits/stdc++.h>
using namespace std;
/*方法1：暴力枚举
画图：n行m列的格子，n+1行 m+1列的线条
枚举图中的矩形的左上角顶点和右下角顶点，计算矩形的长和宽，并判断是否相等
长和宽相等的矩形是正方形，统计+1
*/
long long n,m,cnt=0;
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){//枚举所有左上角顶点(i,j)
for(int j=0;j<m;j++){
for(int k=i+1;k<=n;k++){//枚举所有右下角顶点(k,h)
for(int h=j+1;h<=m;h++){
if((k-i)==(h-j)) cnt++;//矩形的长和宽相等，就是正方形
}
}
}
}
cout<<cnt;
return 0;
}
//方法2：
#include<bits/stdc++.h>
using namespace std;
/*方法2：数学思维
画图：n行m列的格子，n+1行 m+1列的线条
枚举矩形的所有左上角顶点(i,j)
以(i,j)为左上角顶点的正方形个数为：min(n-i,m-j)
*/
long long n,m,cnt=0;
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){//枚举所有左上角顶点(i,j)
for(int j=0;j<m;j++){
cnt+=min(n-i,m-j);//累加以(i,j)为左上角顶点的正方形个数
}
}
cout<<cnt;
return 0;
}
上一题
下一题