CSU 1102 多连块拼图

多连块拼图

时间限制：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[15][15],graph[15][15];
int a,b,c,d; ///分别记录大矩形和小矩形内*第一次出现
void get(){
    bool flag = false;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(graph[i][j]=='*'&&!flag){
                flag = true;
                c = i;
                d = j;
            }
        }
    }
}
bool judge(){
    get();
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            if(graph1[i][j]=='*'){
                if(graph[c+i-a][d+j-b]=='*'){
                    graph[c+i-a][d+j-b] = '.';
                }else return 0;
            }
        }
    }
    get();
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            if(graph1[i][j]=='*'){
                 if(graph[c+i-a][d+j-b]=='*'){
                    graph[c+i-a][d+j-b] = '.';
                }else return 0;
            }
        }
    }
    return 1;
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF,n+m){
        for(int i=1;i<=n;i++){
            scanf("%s",graph[i]+1);
        }
        bool flag = false;
        for(int i=1;i<=m;i++){
            scanf("%s",graph1[i]+1);
            for(int j=1;j<=m;j++){
                if(graph1[i][j]=='*'&&!flag){
                    flag = true;
                    a = i,b = j;
                }
            }
        }
        if(judge()) printf("1
");
        else printf("0
");
    }
}