HYSBZ

题目：

一张n*m的方格纸，有些格子需要印成黑色，剩下的格子需要保留白色。

你有一个a*b的印章，有些格子是凸起（会沾上墨水）的。你需要判断能否用这个印章印出纸上的图案。印的过程中需要满足以下要求：

（1）印章不可以旋转。

（2）不能把墨水印到纸外面。

（3）纸上的同一个格子不可以印多次。

思路：

可以先把印章中的凸起先提取出来单独存储，然后遍历这张方格纸，如果遇上x就把存起来的凸起印刷到方格纸上，印刷过程中如果遇到出界、方格纸不是x或者已经印刷过的情况，就是不能完成印刷。

如果全部印刷完就是成功。

代码：

#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define MAX 1000000000
#define inf 0x3f3f3f3f
#define FRE() freopen("in.txt","r",stdin)

using namespace std;
typedef unsigned long long ll;
const int maxn = 1005;
char paper[maxn][maxn],board[maxn][maxn];
int vis[maxn][maxn];
int n,m,a,b;
vector<pair<int,int> > pi;

bool isin(int x,int y)
{
    return x>=0 && x<n && y>=0 && y<m;
}

bool solve()
{
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(paper[i][j]=='x' && !vis[i][j])//对纸张上出现的x进行一次印章印刷
            {
                for(int k=0; k<pi.size(); k++)
                {
                    int tx = i+pi[k].first, ty = j+pi[k].second;
                    if(isin(tx,ty) && !vis[tx][ty] && paper[tx][ty]=='x')
                        vis[tx][ty]++;
                    else//如果遇到不符合的情况就不能完成印刷
                        return false;
                }
            }
        }
    }
    return true;
}

int main()
{
    //FRE();
    int kase;
    scanf("%d",&kase);
    while(kase--)
    {
        pi.clear();
        memset(vis,0,sizeof(vis));
        scanf("%d%d%d%d",&n,&m,&a,&b);
        for(int i=0; i<n; i++)
            scanf("%s",paper[i]);

        bool isfirst = true;
        for(int i=0; i<a; i++)
        {
            scanf("%s",board[i]);
            for(int j=0; j<b; j++)//提取出印章上所有的凸起
            {
                if(board[i][j]=='x' && isfirst)
                {
                    pi.push_back(make_pair(i,j));
                    isfirst = false;
                }
                else if(board[i][j]=='x')
                    pi.push_back(make_pair(i-pi[0].first,j-pi[0].second));//存凸起相对于第一个的相对位置
            }
        }
        pi[0].first = pi[0].second = 0;
        if(solve())
            printf("TAK
");
        else
            printf("NIE
");
    }
    return 0;
}