# HackerRank The Grid Search （思维）

## Description

Given a 2D array of digits or grid, try to find the occurrence of a given 2D pattern of digits. For example, consider the following grid:

1234567890
0987654321
1111111111
1111111111
2222222222


Assume we need to look for the following 2D pattern array:

876543
111111
111111


The 2D pattern begins at the second row and the third column of the grid. The pattern is said to be present in the grid.

## Input Format

The first line contains an integer $t$, the number of test cases.

Each of the $t$ test cases is represented as follows:

The first line contains two space-separated integers $R$ and $C$, indicating the number of rows and columns in the grid $G$.

This is followed by $R$ lines, each with a string of $C$ digits representing the grid $G$.

The following line contains two space-separated integers, $r$ and $c$, indicating the number of rows and columns in the pattern grid $P$.

This is followed by $r$ lines, each with a string of $c$ digits representing the pattern $P$.

## Constraints

$1≤T≤5$

$1≤R, r, C, c≤1000$

$1≤r≤R$

$1≤c≤C$

## Output Format

Display ‘YES’ or ‘NO’, depending on whether $p$ is present in $G$.

## Sample Input

2
10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530
15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99


## Sample Output

YES
NO


## AC 代码

#include <bits/stdc++.h>
#define IO                       \
ios::sync_with_stdio(false); \
cin.tie(0);                  \
cout.tie(0);
using namespace std;
typedef long long LL;
const int maxn = 1e3 + 10;

int r, c;
int r2, c2;
char str[maxn][maxn];
char str2[maxn][maxn];
int rl[maxn][maxn][10];
LL bj[maxn][maxn];

bool judge(int x, int y, LL test) {
if (bj[x][y] != test) {
return false;
}
for (int i = 0; i < r2; i++) {
for (int j = 0; j < c2; j++) {
if (str2[i][j] != str[x - r2 + i][y - c2 + j]) {
return false;
}
}
}
return true;
}

bool solve() {
memset(rl, 0, sizeof(rl));
memset(bj, 0, sizeof(bj));
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
for (int k = 0; k < 10; k++) {
rl[i][j][k] =
rl[i - 1][j][k] + rl[i][j - 1][k] - rl[i - 1][j - 1][k];
}
++rl[i][j][str[i - 1][j - 1] - '0'];
}
}
for (int i = r2; i <= r; i++) {
for (int j = c2; j <= c; j++) {
int sm[10] = {0};
LL flag = 0;
for (int k = 0; k < 10; k++) {
sm[k] = rl[i][j][k] - rl[i - r2][j][k] - rl[i][j - c2][k] +
rl[i - r2][j - c2][k];
flag <<= 6;
flag |= sm[k] & ((1 << 6) - 1);
}
bj[i][j] = flag;
}
}
LL test = 0;
int sm[10] = {0};
for (int i = 0; i < r2; i++) {
for (int j = 0; j < c2; j++) {
++sm[str2[i][j] - '0'];
}
}
for (int i = 0; i < 10; i++) {
test <<= 6;
test |= sm[i] & ((1 << 6) - 1);
}
for (int i = r2; i <= r; i++) {
for (int j = c2; j <= c; j++) {
if (judge(i, j, test)) {
return true;
}
}
}
return false;
}

int main() {
#ifdef LOCAL_IM0QIANQIAN
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#else
// IO;
#endif // LOCAL_IM0QIANQIAN

int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &r, &c);
for (int i = 0; i < r; i++) {
cin >> str[i];
}
scanf("%d%d", &r2, &c2);
for (int i = 0; i < r2; i++) {
cin >> str2[i];
}
cout << (solve() ? "YES" : "NO") << endl;
}
return 0;
}