暴力。

Table of Contents

  1. Description
  2. Solution

Description

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

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

（1）印章不可以旋转。

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

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

多组询问.

Solution

直接暴力匹配是$O(n^4)$的, 怎么优化呢?

每一次印都会从当前没印的最左上开始印, 把印章的最左上印在上面, 否则后面就再也没办法印了.

记录每个需要印的位置, 和一个印章的偏移量序列, 每个需要印的点只会访问一次, 就降到了$O(n^2)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int maxn = 1005;

char s[maxn];
int n, m, a, b;
int mtr[maxn][maxn], pa[maxn][maxn];
int needx[maxn * maxn], needy[maxn * maxn], deltx[maxn * maxn], delty[maxn * maxn];
int num_n, num_d;
int sx, sy;

bool chk(int x, int y) {
  for (int i = 1; i <= num_d; ++i) {
    int ix = x + deltx[i], iy = y + delty[i];
    if (ix < 1 || ix > n || iy < 1 || iy > m) return 0;
    if (!mtr[ix][iy]) return 0;
    mtr[ix][iy] = 0;
  }
  return 1;
}

int main() {
  int T; scanf("%d", &T);
  while (T--) {
    num_d = num_n = 0;
    scanf("%d%d%d%d", &n, &m, &a, &b);
    for (int i = 1; i <= n; ++i) {
      scanf("%s", s + 1);
      for (int j = 1; j <= m; ++j) {
        mtr[i][j] = (s[j] == 'x');
        if (mtr[i][j]) {
          needx[++num_n] = i;
          needy[num_n] = j;
        }
      }
    }
    for (int i = 1; i <= a; ++i) {
      scanf("%s", s + 1);
      for (int j = 1; j <= b; ++j) {
        pa[i][j] = (s[j] == 'x');
        if (pa[i][j]) {
          if (!num_d) {
            sx = i; sy = j; ++num_d;
          } else {
            deltx[++num_d] = i - sx;
            delty[num_d] = j - sy;
          }
        }
      }
    }
    bool sol = true;
    for (int i = 1; i <= num_n; ++i)
      if (mtr[needx[i]][needy[i]])
        if (!chk(needx[i], needy[i])) {
          puts("NIE"); sol = false; break;
        }
    if (sol) puts("TAK");
  }
  return 0;
}