UVA201正方形

2019-11-10 17:25:10

字体：大中小

来源：转载

供稿：网友

像我其他文章中写的一样，读题很重要，CSDN上有紫书的原题资源。这题我的思路是用数组存储线段，用r1,r2,c1,c2的值使不同的线段被储存。（可以理解成不同的向量）这里写图片描述

#include<stdio.h>#include<string.h>#define maxn 12#define c1 1 //此部分是我的解题#define c2 10 //思想的核心#define r1 100 //<---------#define r2 1000 //<---------int q[maxn][maxn],cnt[maxn],m,n;int main(){ char cmd[2]; int x,y,kase=0; while(scanf("%d %d",&n,&m)==2){ memset(q,0,sizeof(q)); memset(cnt,0,sizeof(cnt)); while(m--){ scanf("%s %d %d",cmd,&x,&y); //输入线段 if(cmd[0]=='H'){ q[x][y]+=r1; q[x][y+1]+=r2; } else{ q[y][x]+=c1; q[y+1][x]+=c2; } } for(int i=1;i<=n;i++){//每个正方形从左上角开始判断 for(int j=1;j<=n;j++){ if(q[i][j]%r2>=r1 && q[i][j]%c2>=c1){ search(i,j);//为r或c线段的第一条时 } //进行下面的判断 } } PRintf("Problem #%d/n/n",++kase);//没怎么看输出格式，可能格式不标准 int count=0; for(int i=1;i<=n;i++){ if(cnt[i]){ printf("%d square(s) of size %d/n",cnt[i],i); count++; } } if(!count) printf("No completed squares can be found/n"); printf("/n"); for(int i=0;i<34;i++) printf("*"); printf("/n"); } return 0;}void search(int x,int y){ int i,j,mark; for(i=1;i<=n&&x+i<=n&&y+i<=n;i++){ for(j=1,mark=1;j<=i;j++){ if(q[x][y+j]/r2==0 || q[x+j][y]%r1<c2 || q[x+i][y+j]/r2==0 || q[x+j][y+i]%r1<c2) mark=0; } if(mark) cnt[i]++; }}/*sample input&output416H 1 1H 1 3H 2 1H 2 2H 2 3H 3 2H 4 2H 4 3V 1 1V 2 1V 2 2V 2 3V 3 2V 4 1V 4 2V 4 323H 1 1H 2 1V 1 2*/

画出我上面的图能更好地理解。