给一个大多连块和小多连块，你的任务是判断大多连块是否可以由两个这样的小多连块拼成。小多连块只能平移，不能旋转或者翻转。两个小多连块不得重叠。左下图是一个合法的拼法，但右边两幅图都非法。中间那幅图的问题在于其中一个小多连块旋转了，而右图更离谱：拼在一起的那两个多连块根本就不是那个给定的小多连块（给定的小多连块画在右下方）。
Input
输入最多包含20组测试数据。每组数据第一行为两个整数n和m(1<=m<=n<=10)。以下n行描述大多连块，其中每行恰好包含n个字符*或者.，其中*表示属于多连块，.表示不属于。以下m行为小多连块，格式同大多连块。输入保证是合法的多连块（注意，多连块至少包含一个正方形）。输入结束标志为n=m=0。
Output
对于每组测试数据，如果可以拼成，输出1，否则输出0。
Sample Input
4 3
.**.
****
.**.
....
**.
.**
...
3 3
***
*.*
***
*..
*..
**.
4 2
****
....
....
....
*.
*.
0 0
Sample Output
1
0
0
分析：应该算是模拟题，对小多连块进行分析，找到第一个出现*的位置记录下来，然后找到大多连块第一个出现*的位置，依据小多连块的*逐步枚举，同时消除在大多连块中相对应的*，如果没有*，则说明不能实现拼图。当消除一遍*后，如果大多连块不全为. （即还存在*），则继续下一轮扫描消除，知道不存在*为止。
代码：
#include<iostream>
#include<stdio.h>
using namespace std;
char a1[10][10],a2[10][10];
int n,m,i,j,x1,y1,x2,y2;
void show_a1()//显示消除过程
{
printf("a1:\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%c",a1[i][j]);
printf("\n");
}
}
void a1_get_first()//得到a1数组第一个出现*的位置
{
bool temp=true;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(a1[i][j]=='*')
{
x1=i;
y1=j;
temp=false;
break;
}
}
if(!temp)
break;
}
}
void a2_get_first()//得到a2数组第一个出现*的位置
{
bool temp=true;
for(i=0;i<m;i++)
{
for(j=0;j<m;j++)
{
if(a2[i][j]=='*')
{
x2=i;
y2=j;
temp=false;
break;
}
}
if(!temp)
break;
}
}
bool is_ok()//判断是否将所有*消除完成
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(a1[i][j]=='*')
return false;
return true;
}
int handle()//处理过程
{
a2_get_first();
while(!is_ok())
{
a1_get_first();
for(i=x2;i<m;i++)
for(j=0;j<m;j++)
if(a2[i][j]=='*')//按照a2中出现的*逐个消除a1中的*
{
if(a1[x1+i-x2][y1+j-y2]=='*')
a1[x1+i-x2][y1+j-y2]='.';
else//a2中某位置出现*而a1中未出现则一定会消除不干净
return 0;
}
//show_a1();
}
return 1;
}
int main()
{
while(scanf("%d%d",&n,&m)&&n)
{
for(i=0;i<n;i++)
scanf("%s",&a1[i]);
for(i=0;i<m;i++)
scanf("%s",&a2[i]);
printf("%d\n",handle());
}
return 0;
}
版权声明：本文为xing634325131原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。