There exits 2D array. We need to find out whether a given string ("microsoft") exits in the given matrix. The string can be vertical or horizontal or

There exits 2D array. We need to find out whether a given string ("microsoft") exits in the given matrix. The string can be vertical or horizontal or in snake form but not in diagonal.

mi..
...c.o..oft
.....r.s

the basic way is just scan the 2d array row by row (col by col ) and find the matching, we can use backtrack
{{{
int row;
int col;
int len;
char str[len]="microsoft";
char a[row][col]="…";
foo(int idx, int i,int j, char* str,const& char a[][col])
{
for(;i < row;i++,j=0)
for(;j < col;j++)
{
if(str[idx]==a[i][j])
{
if(idx==len-1) return true;
bool result=foo(idx+1,i,j+1,str,a);
if(result) return true;
}
}
return false;
}
}}}