title: search a pattern in a 2D matrix
body: <p>This is an interview question </p>
  
  <p>You have to find a string in two-dimensional array. The input contains 2-D array of characters and given string. You can move in one of eight directions . The output contains location of first letter of string if string found completely, otherwise return -1. Any one out of multiple answers is accepted, if possible.</p>
  
  <p>For example, Input:</p>
  
  <pre><code>b t g
  p a d
  r k j
  
  String: rat
  Output: (2,0)
  </code></pre>
  
  <p>I tried this but getting wrong output for </p>
  
  <pre><code> 5 5
      A C P R C
      X S O P C
      V O V N I
      W G F M N
      Q A T I T
  
      MICROSOFT
  </code></pre>
  
  <p>please help</p>
  
  <pre><code>#include&lt;iostream&gt;
  #include&lt;string&gt;
  using namespace std;
  bool isInside(int x,int y,int m,int n)
  {
      if(x&gt;=0&amp;&amp;x&lt;m&amp;&amp;y&gt;=0&amp;&amp;y&lt;n)return true;
      return false;
  }
  void findString(char mat[10][10],int m,int n,string str)
  {
      int i,j;
  
      for(i=0;i&lt;m;i++)
          for(j=0;j&lt;n;j++)
      {
          int k=0,x=i,y=j;
          bool flag=true;
          if(mat[i][j]==str[k])
          {
              while(flag&amp;&amp;k&lt;str.size())
              {
                  int x1=x-1,x2=x+1,y1=y-1,y2=y+1;
                  if(isInside(x1,y1,m,n)&amp;&amp;mat[x1][y1]==str[k])
                      {
                          x=x1; y=y1; k++;
                      }
                  else if(isInside(x1,y,m,n)&amp;&amp;mat[x1][y]==str[k])
                      {
                          x=x1; y=y; k++;
                      }
                  else if(isInside(x1,y2,m,n)&amp;&amp;mat[x1][y2]==str[k])
                      {
                          x=x1; y=y2; k++;
                      }
                  else if(isInside(x,y1,m,n)&amp;&amp;mat[x][y1]==str[k])
                      {
                          x=x; y=y1; k++;
                      }
                  else if(isInside(x,y2,m,n)&amp;&amp;mat[x][y2]==str[k])
                      {
                          x=x; y=y2; k++;
                      }
                  else if(isInside(x2,y1,m,n)&amp;&amp;mat[x2][y1]==str[k])
                      {
                          x=x2; y=y1; k++;
                      }
                  else if(isInside(x2,y,m,n)&amp;&amp;mat[x2][y]==str[k])
                      {
                          x=x2; y=y; k++;
                      }
                  else if(isInside(x2,y2,m,n)&amp;&amp;mat[x2][y2]==str[k])
                      {
                          x=x2; y=y2; k++;
                      }
                  else flag=false;
              }
              if(flag==true)
              {
                  cout&lt;&lt;endl&lt;&lt;"\("&lt;&lt;i&lt;&lt;","&lt;&lt;j&lt;&lt;")"&lt;&lt;endl;
                  return;
              }
          }
      }
      cout&lt;&lt;endl&lt;&lt;"-1"&lt;&lt;endl;
      return;
  }
  int main()
  {
      int i,j,n,m;
      char mat[10][10];
      string str;
      cout&lt;&lt;"enter the dimention of the matrix: ";
      cin&gt;&gt;m&gt;&gt;n;
      cout&lt;&lt;endl&lt;&lt;"enter the char matrix:"&lt;&lt;endl;
      for(i=0;i&lt;m;i++)
          for(j=0;j&lt;n;j++)
          cin&gt;&gt;mat[i][j];
      cout&lt;&lt;endl&lt;&lt;"enter the test string: ";
      cin&gt;&gt;str;
      findString(mat,m,n,str);
      return 0;
  }
  </code></pre>