湖南省第七届大学生计算机程序设计竞赛

傷城~ 2022-06-14 12:14 242阅读 0赞

给一个大多连块和小多连块，你的任务是判断大多连块是否可以由两个这样的小多连块拼成。小多连块只能平移，不能旋转或者翻转。两个小多连块不得重叠。左下图是一个合法的拼法，但右边两幅图都非法。中间那幅图的问题在于其中一个小多连块旋转了，而右图更离谱：拼在一起的那两个多连块根本就不是那个给定的小多连块（给定的小多连块画在右下方）。

![1102.png][]

## 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 ##

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n,m,bx,by,sx,sy;
    char map1[11][11],map2[11][11];
    void findmap1()
    {
        int ok=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(map1[i][j]=='*')
                {
                    bx=i;
                    by=j;
                    ok=1;
                    break;
                }
            }
            if(ok)
                break;
        }
       // printf("%d %d\n",bx,by);
    }
    void findmap2()
    {
        int ok=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(map2[i][j]=='*')
                {
                    sx=i;
                    sy=j;
                    ok=1;
                    break;
                }
            }
            if(ok)
                break;
        }
        //printf("%d %d\n",sx,sy);
    }
    int isok()
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(map1[i][j]=='*')
                    return 0;
            }
        }
        return 1;
    }
    int solve()
    {
        int t=2;
        while(t>0)
        {
            t--;
            findmap1();
            for(int i=0;i<m;i++)
            {
                for(int j=0;j<m;j++)
                {
                    if(map2[i][j]=='*')
                    {
                        if(map1[i+bx-sx][j+by-sy]!='*')
                        {
                            return 0;
                        }
                        else
                            map1[i+bx-sx][j+by-sy]='.';
                    }
                }
            }
        }
        return isok();
    }
    int main()
    {
        while(~scanf("%d %d",&n,&m),(n||m))
        {
            for(int i=0;i<n;i++)
                scanf("%s",map1[i]);
            for(int i=0;i<m;i++)
                scanf("%s",map2[i]);
            findmap2();
            printf("%d\n",solve());
        }
        return 0;
    }

[1102.png]: http://acm.csu.edu.cn/upload/problem_attach/2017-03-22_E1B095C678838D45/1102.png