目录

---

@description@

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

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

（1）印章不可以旋转。

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

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

input

第一行一个整数 q (1<=q<=10)，表示测试点数量。

接下来 q 个测试点，每个测试点中：

第一行包含 4 个整数 n, m, a, b (1<=n,m,a,b<=1000)。

接下来 n 行，每行 m 个字符，描述纸上的图案。'.'表示留白，'x'表示需要染黑。

接下来 a 行，每行 b 个字符，描述印章。'.'表示不沾墨水，'x'表示沾墨水。

output

对于每个测试点，输出 TAK（是）或 NIE（否）。

sample input

2

3 4 4 2

xx..

.xx.

xx..

x.

.x

x.

..

2 2 2 2

xx

xx

.x

x.

sample output

TAK

NIE

@solution@

说实话我一开始看到这道题觉得挺难的

纸上的从上到下，从左到右的第一个黑格一定对应着印章上从上到下，从左到右的第一个黑格。

否则你移动印章要么多盖黑格要么少盖黑格

然后就模拟，再找下一个黑格，再模拟。

为了控制时间复杂度，我们将印章上的黑格坐标存下来而不是将整个印章存下来。

这样每次操作必然会消去一个黑格。

@accepted code@

#include
    
     #include
     
      #include
      
       using namespace std;typedef pair
       
         pii;const int MAXN = 1000 + 5;int read() {    static int x; scanf("%d", &x);    return x;}vector
        
         vec;char pp[MAXN][MAXN], s[MAXN];void solve() {    vec.clear();    int n = read(), m = read(), a = read(), b = read();    for(int i=1;i<=n;i++)        scanf("%s", pp[i] + 1);    int ox = -1, oy = -1;    for(int i=1;i<=a;i++) {        scanf("%s", s + 1);        for(int j=1;j<=b;j++)            if( s[j] == 'x' ) {                if( ox == -1 )                    ox = i, oy = j;                vec.push_back(make_pair(i - ox, j - oy));            }    }    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)            if( pp[i][j] == 'x' ) {                for(int k=0;k
         
           n || y > m ) { puts("NIE"); return ; } if( pp[x][y] == 'x' ) pp[x][y] = '.'; else { puts("NIE"); return ; } } } puts("TAK");}int main() { int q = read(); for(int i=1;i<=q;i++) solve();}
         
        
       
      
     
    

@details@

我一开始还想着什么图染色。

现在看过来都为当时的自己担忧……