题目描述
由火柴棍组成的一个n×n的正方形,按从上到下,从左到右的顺序给火柴棍编号,从1开始,比如下图中,一共有24根火柴棍。 问去掉若干个火柴棍之后,这个图形中还存在多少个正方形?
如下图所示,n=3时,去掉12,17,23号火柴棒之后,还剩下5个正方形。
输入
第一行是一个整数T(1≤T≤1000),表示样例的个数。
每个样例的第1行是两个整数n(1≤n≤50),表示图形的宽度。 样例的第2行首先是一个整数m(0≤m≤2n(n+1),表示去掉火柴棍的个数,后面接m个整数,表示去掉火柴棍的序号,所有序号都是唯一的。
输出
依次,每行输出一个样例的结果
样例输入
2 3 0 3 3 12 17 23
样例输出
14 5
这道题还是有一定难度的,我的思路是:
将横棍与竖棍分别用二维数组表示,每一个棍赋值为1,而移除后其值被赋为0。
从长度为1的小正方形开始。
计算长度时将所在区间的值加起来,若四条边相等,且都等于小正方形边长,则符合。
#include <stdio.h>
int heng[55][55],shu[55][55];
void give(int n)
{
int i,j;
for(i = 1;i <= n+1;i++)
{
for(j = 1;j <= n+1;j++)
{
heng[i][j] = 1;
shu[i][j] = 1;
}
}
}
void Remove(int n,int m)//去除木棍
{
int x,p;
x = m / (2*n+1) +1;
p = m % (2*n+1);
if(p>=1 && p<=n)
heng[x][p] = 0;
else if(p==0)
shu[x-1][n+1] = 0;
else if(p>n && p <=2*n)
shu[x][p-n] = 0;
}
int hl(int h,int s,int w)//h行从s到w列的横的长度
{
int sum = 0;
for(;s <= w;s++)
sum += heng[h][s];
return sum;
}
int sl(int s,int i,int j)//s列从i到j行竖的长度
{
int sum = 0;
for(;i <= j;i++)
sum += shu[i][s];
return sum;
}
int count(int len,int n)//len+1为小正方形边长
{
int i,j,sum=0;
for(i = 1;i+len <= n;i++)
{
for(j = 1;j+len <= n;j++)
{
if((hl(i,j,j+len)==len+1) && (sl(j,i,i+len)==len+1)
&& (hl(i+len+1,j,j+len)==len+1) && (sl(j+len+1,i,i+len)==len+1))
{
sum++;
}
}
}
return sum;
}
int main()
{
int n,t,m,i,j,len,ans,num;
scanf("%d",&t);
while(t--)
{
ans = 0;
scanf("%d",&n);
give(n);
scanf("%d",&num);
for(i = 0;i < num;i++)
{
scanf("%d",&m);
Remove(n,m);
}
for(len = 0;len < n;len++)
{
ans += count(len,n);
}
printf("%d\n",ans);
}
return 0;
}