# Hackerrank - The Grid Search Solution

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.

**Function Description**

Complete the *gridSearch* function in the editor below. It should return `YES`

if the pattern exists in the grid, or `NO`

otherwise.

gridSearch has the following parameter(s):

*G*: the grid to search, an array of strings*P*: the pattern to search for, an array of strings

**Input Format**

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

Each of the test cases is represented as follows:

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

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

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

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

**Constraints**

**Output Format**

Display `YES`

or `NO`

, depending on whether is present in .

**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
```

**Explanation**

The first test in the input file is:

```
10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530
```

As one may see, the given pattern is present in the larger grid, as marked in bold below.

```
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
```

The second test in the input file is:

```
15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99
```

The search pattern is:

`99 99`

This cannot be found in the larger grid.

### Solution in Python

```
import re
def gridSearch(G, P):
l = len(P)
m = len(P[0])
for x,y in enumerate(G):
for i in ((m.start(0)) for m in re.finditer("(?=%s)"%P[0], y)):
for a in range(1,l):
if G[a+x][i:i+m]!=P[a]:
break
else:
return "YES"
return "NO"
for _ in range(int(input())):
R,C = map(int,input().split())
G = [input() for _ in range(R)]
r,c = map(int,input().split())
P = [input() for _ in range(r)]
print(gridSearch(G, P))
```