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

	/*
	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);}
	}

view raw WORDAMENT.cpp hosted with ❤ by GitHub

eg......

keep coding.......

work hard have fun make history

@hios