有趣的数学问题，这是我参加学校的编程比赛时做的一个题目，拿了个三等奖，呵呵！注解比较具体！
问题描述：
亚特兰蒂斯是一块富饶漂亮的土地.恺撒大帝率领他的大军,经过了一整年的浴血奋战,终于将它纳入了罗马的版图.然而,长期的战火彻底抹去了这里的繁华,昔日的富庶之地如今一片荒凉.恺撒大帝作为一位有着雄才大略的君主,决定在战争的废墟上建起一座更为宏伟的城市.所以,在建城之前,他需要对整个城市进行规划.
亚特兰蒂斯是一块矩形平原,恺撒预备在上面修建一些建筑.为了规划方便,他将矩形划分成N*M格.棘手的是,部分古老的神庙残存下来,散布在某些格子内.亚特兰蒂斯的原住民本就十分信仰神灵,而这些经过战火洗礼的神庙被他们视为圣物,是万万不能拆除的,否则将激起民愤,甚至引发暴动.恺撒深知这一点,因此,他的新建筑在选址时要避开这些神庙.
假设新的建筑物有P种规格,每种建筑物都是正方形的,占地为Ti*Ti格(1<=i<=P).恺撒想知道对于每种规格的建筑,有多少种不同的合适选址方案(一种合适的选址方案指的是在该建筑所占的正方形区域内不存在神庙).
输入:
输入文件第一行包含三个数,分别代表N,M,P(1<=N,M<=2000,1<=P<=1000).随后的N行,每行有M个0或1(1表示该格为废墟,0表示该格有神庙).接下来的P行每行有一个整数Ti(1<Ti<=max(M,N)),代表的第i种建筑物的边长.
输出:
输出文件有P行,每行一个整数,每行的数代表边长为Ti的建筑物选址方案数.
样例输入(spuares.in):
4 4 2
1011
1111
1110
1110
2
3
样例输出(squares.out):
5
1
/*********************
ksexe.c
Turboc2.01下编译通过
**********************/
#include "stdio.h"
#include "conio.h"
#include "time.h"
main()
{
FILE *fp,*fout; /* 定义输入输出文件指针 */
int N,M,P,T[1000],Tout[1000]; /* 定义行N,列M,与规格P变量,及规格与输出数组 */
int count,linecount; /* 定义计数变量与行计数变量 */
long X,DATA_START,DATA_END,DataXPos,DataYpos,Pcount,Xpos,Ypos; /* 定义有关的位置变量 */
int DATA,textY; /* 定义数据变量DATA */
void *tmp=0; /* 定义暂存指针变量 */
clock_t start,end; /* 定义计时变量 */
float percent=0.0,TIME=0.0; /* 定义完成百分比与时间变量 */
Pcount=0;count=0;linecount=0; /* 赋初值 */
fp=fopen("squares.in","r"); /* 打开输入文件 */
if(fp==NULL) /* 若未打开,则显示出错 */
{
printf("File squares.in Not Found!");
exit(1);
}
fscanf(fp,"%d %d %d",&N,&M,&P); /* 读取N,M,P */
DATA_START=ftell(fp)+2L; /* 得数据起始位置DATA_START */
printf(" N=%d,M=%d,P=%d",N,M,P); /* 在屏幕上输出N,M,P */
/* 动态分配内存 */
/*if((T=malloc(P))==NULL)
{
printf("Not enough Memory!");
exit(1);
} */
fseek(fp,N*(M+2L)+2L,SEEK_CUR); /* 文件的位置指示定位于规格起始处 */
DATA_END=ftell(fp); /* 得到数据结束位置DATA_END */
for(count=0;count<P;count++)
{
fscanf(fp,"%d%*c",&T[count]); /* 读取规格数 */
printf(" T=%d",T[count]); /* 在屏幕上显示出来 */
Tout[count]=0; /* 输出数组清零 */
}
fseek(fp,DATA_START,SEEK_SET); /* 文件位置指示重新定位于数据开始 */
printf(" ");
textY=wherey(); /* 得当前光标位置的行标值 */
start=clock(); /* 开始计时 */
for(X=DATA_START;X<DATA_END-T[0]*2L-(T[0]-1)*M-T[0]+1L;X++) /* 判定总位置指示是否大于最小规格最后一个起点方格 */
{
if(X>DATA_START+linecount*(M+2L)+M-T[0]) /* 判定是否超出行结束方格 */
{
linecount++; /* 若超出,则行计数器增1 */
X=DATA_START+(M+2L)*linecount; /* X指示为下一行开始 */
}
DataXpos=X; /* 横向读取初值 */
DataYpos=X; /* 纵向读取初值 */
Pcount=0; /* 读取个数初值 */
for(count=0;count<P;count++) /* 循环检测各个规格的选址方案 */
{
for(;Pcount<T[count];Pcount++) /* 读取个数控制,使读取个数逐步递增 */
{
if(DataXpos>DATA_END-2LDataYpos>DATA_START+(M+2L)*(linecount+1)) /* 判定是否到达边界 */
goto next1; /* 若是则跳到next1,退出外循环 */
for(Xpos=DataXpos;Xpos<=DataXpos+Pcount;Xpos++) /* 横向循环读取方格 */
{
fseek(fp,Xpos,SEEK_SET); /* 定位于读取方格 */
fread(tmp,1,1,fp); /* 读取1个数据 */
DATA=atoi(tmp); /* 转换为整型数字 */
if(DATA==0) /* 若为零,则跳到next1,退出外循环 */
goto next1;
}
for(Ypos=DataYpos;Ypos<DataYpos+Pcount*(M+2L);Ypos+=M+2L) /* 纵向循环读取方格 */
{
fseek(fp,Ypos,SEEK_SET); /* 定位于读取方格 */
fread(tmp,1,1,fp); /* 读取1个数据 */
DATA=atoi(tmp); /* 转换为整型数字 */
if(DATA==0) /* 若为零,则跳到next1,退出外循环 */
goto next1;
}
DataXpos+=M+2L; /* 横向读取起始位置指向下一个位置 */
DataYpos++; /* 纵向读取起始位置指向下一个位置 */
}
Tout[count]++; /* 若此种规格的所有方格均为1,则对应输出值增1 */
continue; /* 继续循环,跳过break句 */
next1: break; /* 跳出循环,X值增1,继续 */
}
gotoxy(1,textY); /* 屏幕光标定位 */
end=clock(); /* 获取计时值 */
percent=(X-DATA_START)/(float)(DATA_END-T[0]*2L-(T[0]-1)*M-T[0]-DATA_START); /* 计算完成百分比 */
TIME=(end-start)/18.2; /* 计算用时 */
printf("%.0f%% complished! %02d:%02d used. ",percent*100,(int)TIME/60,(int)TIME%60); /* 输出信息 */
}
if((fout=fopen("squares.out","a"))==NULL) /* 创建输出文件squares.out */
{
printf("Can not create squares.out file!"); /* 若不能创建,则显示出错信息 */
exit(1);
}
for(count=0;count<P;count++)
{
printf(" T=%d: %d",T[count],Tout[count]); /* 在屏幕上输出结果 */
fprintf(fout,"%d ",Tout[count]); /* 将结果输出到文件squares.out */
}
fclose(fout); /* 关闭输出文件 */
fclose(fp); /* 关闭输入文件 */
printf(" You can use [ type squares.out ] to view out file! "); /* 显示提示信息 */
}
|
