The Grid Search Hackerrank problem solution

The Grid Search Hackerrank

As you already know the question The Grid Search Hackerrank problem
But let’s understand it in a more simple way.

 

We have to find a 2D matrix in a big 2D Matrix. suppose we have a matrix like

123456
125456
675432
435683

and if we want to find
545
543
yes, we can find it, it starts from 2nd row 3rdcolumn.
In the problem, the value will be given like these. No. of matrix we want to search that is ‘T’

size of big matrix rowXcolumn that is R&C

then the array or matrix value or element in G[]

then the size of small searchable matrix that is r X c  and the elements are stored in P.

Limtation
1<=T<=5
1<=r,R,c,C<=1000
1<=r<=R
1<=c<=C

Output sample

Display ‘YES’ or ‘NO’, depending on whether (or not) you find that the larger grid contains the rectangular pattern . The evaluation will be case sensitive.

Example Input

2
10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530
5 5
40045
95628
40400
54904
96241
2 2
99
99
Example  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 2D grid is indeed 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:

5 5
40045
95628
40400
54904
96241
2 2
99
99
The search pattern is:

99
99
This cannot be found in the larger grid.

Solution

There are 2 approaches demonstrated here.
One is the C++ Program which does an element by element match for the smaller array in the larger 2D and breaks as soon as there is a mismatch.
Using RUBY regex can be used also
It will be great exercise for the coder to brainstorm on how and why it works!

#include<bits/stdc++.h>
using namespace std;
int main()
{
 int t;
 cin>>t;
 for(int k=0;k<t;k++)
 {
 string s;
 int count=0;
 int m,n,r,c;
 cin>>m>>n;
 string a[m];
 for(int i=0;i<m;i++)
 cin>>a[i];
 cin>>r>>c;
 string p[r];
 for(int i=0;i<r;i++)
 cin>>p[i];
 bool flag;
 for(int i=0;i<m;i++)
 {
  flag=false;
  for(int j=0;j<n;j++)
  {
   int count=0;
   if((a[i][j]-'0')==(p[0][0]-'0'))
   {
    bool anflag=false;
    for(int e=0;e<r;e++)
    {
     for(int f=0;f<c;f++)
     {
      if(((i+e)<=(m-1))&&((j+f)<=(n-1)))
      {if((a[i+e][j+f]-'0')==(p[e][f]-'0'))
       count++;
       else
       anflag=true;
       if(count==(r*c))
       {flag=true;
       break;}}
      if(flag||anflag)
      break;
     }
     if(flag||anflag)
     break;
    }
   }
   if(flag)
   break;
  }
   if(flag)
   break;
 }
  if(flag)
  cout<<"YES"<<endl;
  else
  cout<<"NO"<<endl;
 }
 return 0;
}

A very good Programm and simple i found somewhere.

#include<iostream>

using namespace std;

int main()
{
int T,i;
cin>>T;
for(i=1;i<=T;i++)
{
    int R,C,r,c,flag=0,final=0;
    cin>>R>>C;
    char G[R][C];
    for(int j=0;j<R;j++)
    for(int k=0;k<C;k++)
    cin>>G[j][k];
    cin>>r>>c;
    char P[r][c];
    for(int j=0;j<r;j++)
    for(int k=0;k<c;k++)
    cin>>P[j][k];

for(int j=0;j<R;j++)
for(int k=0;k<C;k++)
{   

if(G[j][k]==P[0][0])
    {   
        int flag=1;
    if(C-k>=c)  
    for(int pr=1;pr<r;pr++)
    {
    if(flag==0)
    break;  
    for(int pc=0;pc<c;pc++)
    {   

        if(G[j+pr][k+pc]==P[pr][pc]){
            if(pr==r-1&&pc==c-1)
                final=1;
            flag=1;
            }
        else{   
        flag=0;
        break;
        }
    }
}
}
}
if(final)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
    return 0;
}
for _ in range(input()):
    big = []
    small = []
    R, C = map(int, raw_input().split())
    for __ in range(R):
        big.append(raw_input())
    r, c = map(int, raw_input().split())
    for __ in range(r):
        small.append(raw_input())
    found = False
    for i in range(R - r + 1):
        for j in range(C - c + 1):
            flag = True
            for k in range(r):
                for l in range(c):
                    if big[i + k][j + l] != small[k][l]:
                        flag = False
                        break
                if not flag:
                    break
            if flag:
                print "YES"
                found = True
                break
        if found:
            break
    else:
        print "NO"
import java.util.Scanner;

public class Solution {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int i = 0; i < T; i++) {
			String[] G = new String[sc.nextInt()];
			sc.nextInt();
			for (int j = 0; j < G.length; j++) {
				G[j] = sc.next();
			}
			String[] P = new String[sc.nextInt()];
			sc.nextInt();
			for (int j = 0; j < P.length; j++) {
				P[j] = sc.next();
			}
			System.out.println(search(G, P) ? "YES" : "NO");
		}
		sc.close();
	}

	private static boolean search(String[] G, String[] P) {
		for (int i = 0; i <= G.length - P.length; i++) {
			for (int j = 0; j <= G[0].length() - P[0].length(); j++) {
				if (search(G, P, i, j)) {
					return true;
				}
			}
		}
		return false;
	}

	private static boolean search(String[] G, String[] P, int i, int j) {
		for (int k = 0; k < P.length; k++) {
			for (int l = 0; l < P[0].length(); l++) {
				if (G[i + k].charAt(j + l) != P[k].charAt(l)) {
					return false;
				}
			}
		}
		return true;
	}
}

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.