Grid Search

GRID SEARCH

We are given a 2D array of digits of and we are supposed to find the location of a 2D pattern of digits.

For eg: 
consider a 5x5 2D array of digits :

12345
14568
16845
95782
57864

and we have to search for the following pattern of digits:

568
845
782

we can see it matches at the location 2,3


Program: 

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int row,col,prow,pcol;
char str[101][101],pattern[101][101];

// this function checks if the pattern had a match in the 2d array
int check(int k,int l){
    int a,b,m,n; 
// m,n for rows and columns in pattern matrix
  // a,b for rows and colums in 2d string in which pattern is to be matched

    for(m=0,a=k;a<=k+prow&& m<prow;m++,a++)
 for(n=0,b=l;b<=l+pcol&& n<pcol;b++,n++){
     if(str[a][b]==pattern[m][n])
  continue;
     else
  return 0;
    }
    return 1;
}


int main() {

    int i,j,flag=0,t;
 printf("Enter the number of rows and column in 2D array:-");
  printf("\nRows:");
  scanf("%d",&row);
  printf("Columns:");
  scanf("%d",&col);

   printf("Enter the digits in the 2D matrix (Press enter after each row):\n");
 for(i=0;i<row;i++)
     scanf("%s",str[i]);

   printf("\nEnter the number of rows and column in the pattern to be matched:-");
  printf("\nRows:");
  scanf("%d",&prow);
  printf("Columns:");
  scanf("%d",&pcol);

      printf("Enter the digits in the Pattern matrix (Press enter after each row):\n");
 for(i=0;i<prow;i++)
     scanf("%s",pattern[i]);


  for(i=0;i<=row-prow;i++)
     for(j=0;j<=col-pcol;j++){
  if(str[i][j]==pattern[0][0])
   {
      flag=check(i,j);
      if(flag==1)
      {
      printf("The pattern match found at location: %d,%d \n",i+1,j+1);
       goto next;
      }
   }
 }
 if(flag==0)
     printf("NO match found for the given pattern!!\n");
 next: ;

    return 0;
}

Sample Output: