第C語言打印正方形實例代碼目錄題目描述輸入輸出樣例輸入樣例輸出

題目描述

由火柴棍組成的一個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

3121723

樣例輸出

14

5

這道題還是有一定難度的，我的思路是：

將橫棍與豎棍分別用二維數組表示，每一個棍賦值為1，而移除后其值被賦為0。

從長度為1的小正方形開始。

計算長度時將所在區(qū)間的值加起來，若四條邊相等，且都等于小正方形邊長，則符合。

#includestdio.h

intheng[55][55],shu[55][55];

voidgive(intn)

inti,j;

for(i=1;i=n+1;i++)

for(j=1;j=n+1;j++)

heng[i][j]=1;

shu[i][j]=1;

voidRemove(intn,intm)//去除木棍

intx,p;

x=m/(2*n+1)+1;

p=m%(2*n+1);

if(p=1p=n)

heng[x][p]=0;

elseif(p==0)

shu[x-1][n+1]=0;

elseif(pnp=2*n)

shu[x][p-n]=0;

inthl(inth,ints,intw)//h行從s到w列的橫的長度

intsum=0;

for(;ss++)

sum+=heng[h][s];

returnsum;

intsl(ints,inti,intj)//s列從i到j行豎的長度

intsum=0;

for(;ii++)

sum+=shu[i][s];

returnsum;

intcount(intlen,intn)//len+1為小正方形邊長

inti,j,sum=0;

for(i=1;i+leni++)

for(j=1;j+lenj++)

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++;

returnsum;

intmain()

intn,t,m,i,j,len,ans,num;

scanf("%d",

while(t--)

ans=0;

scanf("%d",

give(n);

scanf("%d",num);

for(i=0;inum;i++)

scanf("%d",

Remove(n,m);

for(