The Grid Search

Back

Problem

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 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.

Solution


// Complete the gridSearch function below.
static string gridSearch(string[] G, string[] P) {
    string found = "NO";

    // search each row of the grid
    for (int gRow = 0; gRow <= G.Length - P.Length; gRow++)
    {
        // cycle through G[gRow] to find P[0]
        for (int gLetter = 0; gLetter <= G[0].Length - P[0].Length; gLetter++)
        {
            bool match = false;
            // get substring of G[gRow] and compare to P[0]
            if (G[gRow].Substring(gLetter, P[0].Length) == P[0])
            {
                // get index of P[0]
                int index = gLetter;
                match = true;
                // search rows of P against G
                for (int pRow = 0; pRow < P.Length; pRow++)
                {
                    if (P[pRow] != G[gRow+pRow].Substring(index, P[pRow].Length))
                    {
                        match = false;
                        break;
                    }
                }
                if (match) { found = "YES"; break; }
            }
            if (match) break;
        }
    }

    return found;
}
			

Top