UVA - 12291 Polyomino Composer (模拟题)

xiaoxiao2021-02-28  14

题意:给出一个n*n的大图形和一个小m*m图形,看大图中的‘*’的图形能不能由小图'*'的图形构成,图形只能平移,不能反转,旋转。

要考虑一些点,模拟不难

第一点:我们先判断大图和小图中'*'的个数,大图的个数不是小图的二倍就不行。

第二点:我们可以先找出一个特殊点比如最左上的点,当然坐上没有点就最左边,我们从这种特殊点用小图形开始消除大图形,再找的过程中记得如果小图形中的'*'在大图中的相应位置并没有找到'*'的话那就失败。

第三点:消除过程中,小图消除的数量比大图少不行

第四点:消除过后,大图中还有点就不行

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; char s1[15][15],s2[15][15]; int x,y,xx,yy; int n,m; int s22()//计算小图形里的'*'个数,并找出最左边的'*',尽量向左上找 { int res=0; for(int i=0; i<m; i++) { for(int j=0; j<m; j++) { if(s2[j][i]=='*') { if(res==0) { xx=i; yy=j; } res++; } } } return res; } int s11()//计算大图中'*'的个数 { int res=0; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { if(s1[i][j]=='*') res++; } } return res; } int zuizuo()//找大图最左的'*' { for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { if(s1[j][i]=='*') { x=i; y=j; return 1; } } } return 0; } int judge(int i,int j)//判断越界问题 { if(i>=0&&i<m&&j>=0&&j<m) return 1; return 0; } int xiaochu(int x1,int y1,int ans)//用小图形来消除掉大图形,判断能不能组成大图形 { int res=0; for(int i=0; i<n; i++)//那第一个图做样例,这个for可以判断上方有没有点,也就可以判断累加在上边的图形 { for(int j=0; j<n; j++) { if(judge(yy+i-y1,xx+j-x1)&&s2[yy+i-y1][xx+j-x1]=='*') { if(s1[i][j]!='*') return 0; s1[i][j]='.'; res++; } } } if(res!=ans) return 0; return 1; } int main() { while(~scanf("%d%d",&n,&m)) { if(n==0&&m==0) break; for(int i=0; i<n; i++) scanf("%s",s1[i]); for(int i=0; i<m; i++) scanf("%s",s2[i]); int ans=s22(); int flag; if(s11()%ans==0) flag=1; else flag=0; x=-1,y=-1; int sum=0; while(flag) { sum++; flag=zuizuo(); flag=xiaochu(x,y,ans); if(s11()==0) break; if(sum>=2) flag=0; } if(flag&&sum!=2) flag=0; printf("%d\n",flag); } }
转载请注明原文地址: https://www.6miu.com/read-2450350.html

最新回复(0)