多连块拼图
时间限制：1000 ms | 内存限制：65535 KB 难度：4
- 描述
- 多连块是指由多个等大正方形边与边连接而成的平面连通图形。 ———— 维基百科
给一个大多连块和小多连块，你的任务是判断大多连块是否可以由两个这样的小多连块拼成。小多连块只能平移，不能旋转或者翻转。两个小多连块不得重
叠。左下图是一个合法的拼法，但右边两幅图都非法。中间那幅图的问题在于其中一个小多连块旋转了，而右图更离谱：拼在一起的那两个多连块根本就不是那个给
定的小多连块（给定的小多连块画在右下方）。- 输入
- 输
入最多包含 20 组测试数据。每组数据第一行为两个整数 n 和 m(1<=m<=n<=10)。以下 n
行描述大多连块，其中每行恰好包含 n 个字符*或者.，其中*表示属于多连块，.表示不属于。以下 m
行为小多连块，格式同大多连块。输入保证是合法的多连块（注意，多连块至少包含一个正方形）。输入结束标志为 n=m=0。 - 输出
- 对于每组测试数据，如果可以拼成，输出 1，否则输出 0。
- 样例输入
4 3
.**.
****
.**.
....
**.
.**
...
3 3
***
*.*
***
*..
*..
**.
4 2
****
....
....
....
*.
*.
0 0- 样例输出
1
0
0
模拟,记录小矩形中*号第一次出现的位置a,b，大矩形中*号第一次出现的位置 c,d.小矩形与大矩形的映射关系是 g[i][j] <---> G[c+i-a][d+j-b],匹配两次即可。#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define Lim 0.999999
#define EPS 1e-2
#define PI acos(-1.0)
using namespace std;
int n,m;
char graph1[][],graph[][];
int a,b,c,d; ///分别记录大矩形和小矩形内*第一次出现
void get(){
bool flag = false;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(graph[i][j]=='*'&&!flag){
flag = true;
c = i;
d = j;
}
}
}
}
bool judge(){
get();
for(int i=;i<=m;i++){
for(int j=;j<=m;j++){
if(graph1[i][j]=='*'){
if(graph[c+i-a][d+j-b]=='*'){
graph[c+i-a][d+j-b] = '.';
}else return ;
}
}
}
get();
for(int i=;i<=m;i++){
for(int j=;j<=m;j++){
if(graph1[i][j]=='*'){
if(graph[c+i-a][d+j-b]=='*'){
graph[c+i-a][d+j-b] = '.';
}else return ;
}
}
}
return ;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF,n+m){
for(int i=;i<=n;i++){
scanf("%s",graph[i]+);
}
bool flag = false;
for(int i=;i<=m;i++){
scanf("%s",graph1[i]+);
for(int j=;j<=m;j++){
if(graph1[i][j]=='*'&&!flag){
flag = true;
a = i,b = j;
}
}
}
if(judge()) printf("1\n");
else printf("0\n");
}
}