WORDAMENT( WAP to search a word in N*N grid with one char in each cell.)

WORDAMENT.cpp

/*
 WORDAMENT
 program
  {
   WAP to search a word in N*N grid with one char in
   each cell.
  
   move direction allow::( vertically,horizontal,diagonal)

  direction are
( TOP=T BOTTOM=B LEFT=L RIGHT=R TOP-LEFT=TL
 TOP-RIGHT=TR BOTTOM-LEFT=BL BOTTOM-RIGHT=BR)

 If the word found then out put

  @starting cordinate(i,J) ::right direction in wich you move to       find word OR
          ::you print cordinet

 Not found then out put :NOT FOUND

In case of multiple path found
                        @print all path one bye one
      @For eg .
                 grid 4*4 is = H I T E
                               K L M P
                               H E M N
                               I K P R


                INPUT SRING is="LIKE"
                Then out put::(1,1)=T BL BR

                  OR
                          :: (1,1) (0,1) (1,0) (2,1)



              }

              ::BEST OF LUCK KEEP CODING
              <WORK HARD@HAVE FUN AND MAKE HISTORY>


*/


#include<iostream>
#include<string>
#include<windows.h>
using namespace std;

struct node
{
    int i;
    int j;
    struct node *link;
};

class stack
{
    node *p,*top;

public:

    stack(){ top=NULL; p=NULL; }
    void push(int ii,int jj)
    {
        if(top==NULL)
        {
            p=new node;
            p->i=ii;
            p->j=jj;
            p->link='\0';
            top=p;
        }
        else
        {
             p=new node;
             p->i=ii;
             p->j=jj;
            p->link=top;
            top=p;
        }


    }

    void empty(int l)
    {
        static int d=1;
         int sl=0;
         node *k=top;
        while(k!=NULL)
        {
            k=k->link;
            sl++;
        }

         if(sl==l)
            {
              
              cout<<"path "<<d<<"=";
              d++;

                while(top!=NULL)
                {
                  cout<<"("<<top->i<<","<<top->j<<")"<<" ";
                  top=top->link;
                }
                cout<<endl;

             }

         else
            {
               int r=l-sl;
               cout<<"path "<<d<<"=";d++;
                  
               while(top!=NULL)
                   {
                     if(r!=0)
                          {
                             cout<<"-//> "<<" ";r--;
                          }
                     else{
                          
                     cout<<"("<<top->i<<","<<top->j<<")"<<" ";
                      top=top->link;
                         }


                   }
                cout<<endl;

              }


    }

    void pop()
    {

        if(top==NULL){}
        else{

            top=top->link;

            }
    }



   void rvrs()
   {

      struct node *p,*q,*r;r=NULL;
      p=top;
      while(p!=NULL)
      {

          q=p;
          p=p->link;
          q->link=r;

          r=q;

     }
     top=r;

   }



};

class wordament
{

 //to change grid sting also change row and column value in cons.
  char grid[100][100]={"kgcd",
                    "efgh",
                    "igkl",
                    "mnop"};

  int row=4;
  int column=4;
  stack sp; // stor path direction

  bool isright(int i,int j)
              {
               if(i+1<column)
                  return true;
               else
                  return false;
               }

  bool isleft(int i,int j)
                {
                  if(i-1>=0)
                    return true;
                 else
                    return false;
                }

  bool istop(int i,int j)
                  {
                    if(j-1>=0)
                          return true;
                    else
                         return false;
                  }


  bool isbottom(int i,int j)
                  {
                    if(j+1<row)
                          return true;
                    else
                         return false;
                  }

  bool istl(int i,int j)
               {
                if(i-1>=0&&j-1>=0)
                         return true;
                else
                         return false;
               }


  bool istr(int i,int j)
                {
                if(i+1<column&&j-1>=0)
                      return true;
                else
                      return false;
                }


  bool isbr(int i,int j)
              {
                if(i+1<column&&j+1<row)
                      return true;
                else
                      return false;
              }

  bool isbl(int i,int j)
             {
               if(i-1>=0&&j+1<row)
                    return true;
                else
                    return false;
             }

public:
       wordament(){}
      


       void printgrid()
       {
           for(int i=0;i<row;i++)
           {
               for(int j=0;j<column;j++)
               {
                   cout<<grid[i][j]<<" ";
               }
               cout<<endl<<endl;
           }
       }

       void prntpath(char s[])
       {
           for(int i=0;i<row;i++)
           {
               for(int j=0;j<column;j++)
               {
                  if(grid[i][j]==s[0])
                  {
                        sp.push(i,j);
                        findnext(s,i,j,1);


                  }
               }
               cout<<endl;
           }
       }
       int length(char s[]){int k=0;while(s[k]!=NULL)k++; return k;}
       void findnext(char s[],int i,int j,int k)
       {

           if(isleft(i,j))
                {
                    if(grid[i-1][j]==s[k]&&s[k]!=NULL)
                      {
                        sp.push(i-1,j+j);findnext(s,i-1,j,k+1);
                       }
                }

           if(isright(i,j))
                {
                  if(grid[i+1][j]==s[k]&&s[k]!=NULL)
                   {
                     sp.push(i+1,j);findnext(s,i+1,j,k+1);
                   }
                }

           if(isbottom(i,j))
                     {
                       if(grid[i][j+1]==s[k]&&s[k]!=NULL)
                        {
                         sp.push(i,j+1);findnext(s,i,j+1,k+1);
                        }
                     }

           if(istop(i,j))
                   {
                      if(grid[i][j-1]==s[k]&&s[k]!=NULL)
                       {
                         sp.push(i,j-1);findnext(s,i,j-1,k+1);
                       }
                   }

           if(istl(i,j))
             {
              if(grid[i-1][j-1]==s[k]&&s[k]!=NULL)
                 {
                  sp.push(i-1,j-1);findnext(s,i-1,j-1,k+1);
                 }
             }


           if(istr(i,j))
              {
               if(grid[i+1][j-1]==s[k]&&s[k]!=NULL)
                  {
                   sp.push(i+1,j-1);findnext(s,i+1,j-1,k+1);
                  }
              }

           if(isbl(i,j))
               {
                if(grid[i-1][j+1]==s[k]&&s[k]!=NULL)
                 {
                  sp.push(i-1,j+1);findnext(s,i-1,j+1,k+1);
                 }
               }

           if(isbr(i,j))
                {
                  if(grid[i+1][j+1]==s[k]&&s[k]!=NULL)
                    {
                     sp.push(i+1,j+1);findnext(s,i+1,j+1,k+1);
                    }
               }


           if(s[k]==NULL) {sp.rvrs();sp.empty(length(s));}
           sp.pop();

       }


};


int main()
{

    wordament a;
    a.printgrid();
    while(1){
    char s[1000];

    cout<<"input string=";cin>>s;
    a.prntpath(s);}
}