CareerCup

Java:

public class Solution {
    public static void main(String... args){
        char[][] map = {{ 'S', 'N', 'B', 'S', 'N' },
                        { 'B', 'A', 'K', 'E', 'A' }, 
                        { 'B', 'K', 'B', 'B', 'K' },
                        { 'S', 'E', 'B', 'S', 'E' }};

        System.out.println(findPath(map, "SNAKES"));
    }
    
    public static int findPath(char[][] map, String target){
        int count = 0;
        for(int i = 0; i < map.length ; i++){
            for(int j = 0; j < map[i].length; j++){
                count += findPath(map, target, i, j, 0);
            }
        }
        return count;
    }
    
    public static int findPath(char[][] map, String target, int startX, int startY, int targetIndex){
        
        if(startX < 0 || startY < 0 || startX >= map.length || startY >= map[startX].length){
            return 0;
        }
        
        char original = map[startX][startY];
        
        if(original != target.charAt(targetIndex))
            return 0;
        
        if(targetIndex == target.length() - 1)
            return 1;

        int count = 0;
        map[startX][startY] = '\0';         // avoid return back to visited node

        count += findPath(map, target, startX+1, startY, targetIndex+1);
        count += findPath(map, target, startX, startY+1, targetIndex+1);
        count += findPath(map, target, startX-1, startY, targetIndex+1);
        count += findPath(map, target, startX, startY-1, targetIndex+1);
        
        map[startX][startY] = original;
        return count;
    }
}

To compute the time complexity, we can consider the searching path a DFS 4-way tree traversal with the depth equal to the length of searched string k - 1 (root's depth is 0), so searching each tree takes O(4^(k-1)) = O(2^2(k-1)) = O(2^2k). Since each node can be a root, there will be m*n (dimension of the map) trees to search. Therefore, the general time complexity is O(m*n*2^2k). Since 2^2k grows much faster than m*n, simply O(2^2k).

If there is no turning back, it would be a 3-way tree search except that the root has 4 child nodes, but this would have little impact on the time complexity (O(4*3^(k-2)) = O(2^2k)).

//How many occurrences of a given search word can you find in a two-dimensional
// array of characters given that the word can go up, down, left, right, 
//and around 90 degree bends?

//Ex:
//Count of occurrences of SNAKES
//S N B S N
//B A K E A
//B K B B K
//S E B S E

//The answer is 3. 

#include<iostream>
#include<stdlib.h>
using namespace std;

//Maximum movement allowed is equal to length of target word
int FoundWaysToMakeWord(int arr[][5],int i, int j,int m, int n,int index, int maxIndex,int curr[], int target[])
{
   if(i == -1 || i == m)  //allowed index are upto m-1
   {
        return 0;
   }
   if(j == -1 || j == n)//allowed index are upto n-1
   {
        return 0;
   }

   if(index > maxIndex)//SNAKE max index = 4 we can fill char 0 1 2 3 4 position
   {
      return 0;
   }

   curr[index] = arr[i][j];

   if(curr[index] != target[index])
   {
        return 0;//char mismatch found
   }

   if(index == maxIndex)//it mean last char also matched mean we done it 
   {
      return 1;
   }

  return (FoundWaysToMakeWord(arr,i+1,j,m,n,index+1,maxIndex,curr,target) +
  FoundWaysToMakeWord(arr,i-1,j,m,n,index+1,maxIndex,curr,target) +
  FoundWaysToMakeWord(arr,i,j+1,m,n,index+1,maxIndex,curr,target) +
  FoundWaysToMakeWord(arr,i,j-1,m,n,index+1,maxIndex,curr,target));
   
}

/*
//start point can be only (0,0),(m-1,0),(0,n-1),(m-1,n-1)
int FoundWaysToMakeWordUtil(int arr[][5],int target[], int m, int n,int length)
{ 
    int *p = new int[length];
   
    return FoundWaysToMakeWord(arr,0,0,m,n,0,length-1,p,target)+
           FoundWaysToMakeWord(arr,0,n-1,m,n,0,length-1,p,target)+
           FoundWaysToMakeWord(arr,m-1,n-1,m,n,0,length-1,p,target)+
           FoundWaysToMakeWord(arr,m-1,0,m,n,0,length-1,p,target);
}
*/

int FoundWaysToMakeWordUtil(int arr[][5],int target[], int m, int n,int length)
{ 
    int *p = new int[length];

    int count = 0;
    
    for(int i = 0; i < m;i++)
    {
       for(int j = 0; j < n; j++)
       {
           if(arr[i][j] == 'S')
           {
               count += FoundWaysToMakeWord(arr,i,j,m,n,0,length-1,p,target);
           }
       }
    }

    return count;
}


int main()
{
   int p[4][5] = {
                   {'S', 'N', 'B', 'S', 'N'},
                   {'B', 'A', 'K', 'E', 'A'},
                   {'B', 'K', 'B', 'B', 'K'},
                   {'S', 'E', 'B', 'S', 'E'}
                 };
   int target[] = {'S','N','A','K','E','\0'};

   cout<<FoundWaysToMakeWordUtil(p,target,4,5,5)<<endl;
}

I jus want to give a brief explanation about this question since all the others just posted their code. The basic idea is to do search at each possible possition. In this example, we want to find "SNAKE", then the possible start positions are the positions where the character is "S", then you keep a visited array to avoid going back to the same position. The visited array is a little bit tricky. For example, if the matrix is :
S N B S N
B A K E A
B K B B K
S E B S E
Then you go from (0, 0) to (1, 0), to (2, 0), you visited array in these three positions are set as true, but when you discovered that (2, 0) is not a possible answer, you should reset the visited array at position (2, 0) to false immediately since you may go to it later.

#include<iostream>
 using namespace std;
     
    void RecursiveCount(int X, int Y, int Xhigh, int Yhigh, int it, char Search[7], int length,char Word[4][6], int *Count)
	{
		char c = Word[X][Y];

		if( c == Search[it])
		{
			//cout<<X<<"--"<<Y<<"--it:"<<it<<"--length:"<<length<<endl;
			if( it == length-1)
			{
				(*Count)++;
			}
			else if(it < length-1)
			{
				if(X-1 > -1)		RecursiveCount(X-1,Y,Xhigh,Yhigh, it+1,Search,length,Word,Count);
				if(X+1 < Xhigh)		RecursiveCount(X+1,Y,Xhigh,Yhigh, it+1,Search,length,Word,Count);
				if(Y-1 > -1)		RecursiveCount(X,Y-1,Xhigh,Yhigh, it+1,Search,length,Word,Count);
				if(Y+1 < Xhigh)		RecursiveCount(X,Y+1,Xhigh,Yhigh, it+1,Search,length,Word,Count);

			}
	
		}

	}
     
   
    int main()
    {
	char Word[4][6] = {"SNBSN","BAKEA","BKBBK","SEBSE"};
	char Search[7] = {"SNAKES"};
	int length = 6;
	int Count = 0;
    
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<5;j++)
		{
			if(Word[i][j] == Search[i])	RecursiveCount(i,j,5,5,0,Search,length,Word,&Count);
		}
	}
	cout<<"No.of Occurences for the Search Word ="<<Count<<endl;

	getchar();
    return 0;
    }

Confirmed working Java solution below. You also have to keep track of which nodes you've visited so far.

import java.util.ArrayList;

public class Boggle {

    private static class Position {
        public int row;
        public int col;

        public Position(int row, int col) {
            this.row = row;
            this.col = col;
        }

        public boolean equals(Object o) {
            if (!(o instanceof Position)) return false;

            Position other = (Position) o;
            return (this.row == other.row) && (this.col == other.col);
        }

        public String toString() {
            return "(" + row + "," + col + ")";
        }
    }

    public static int wordCount(char[][] grid, String word) {
        int count = 0;
        Position p = new Position(0, 0);
        ArrayList<Position> visited;

        for (int row = 0; row < grid.length; row++) {
            p.row = row;
            for (int col = 0; col < grid[0].length; col++) {
                p.col = col;

                visited = new ArrayList<Position>();
                count += wordCountHelper(grid, word, p, visited);
            }
        }
        return count;
    }

    // number of rows = grid.length
    // number of cols = grid[0].length

    // returns the # of times we can find the word word starting at position p in the grid
    public static int wordCountHelper(char[][] grid, String word, Position p, ArrayList<Position> visited) {
        if (word.charAt(0) != grid[p.row][p.col]) return 0;
        
        // if p is in the list visited, then return 0;
        for (Position visited_pos : visited) {
            if (p.equals(visited_pos)) return 0;
        }
        visited.add(p);

        if (word.length() == 1) {
            System.out.println(visited);
            return 1;  // word.charAt(0) == grid[p.row][p.col]
        }

        int count = 0;
        int n_visited = visited.size();

        // check up
        if (p.row != 0) {
            Position p_next = new Position(p.row - 1, p.col);
            count += wordCountHelper(grid, word.substring(1), p_next, visited);
        }

        // check down
        if (p.row != grid.length - 1) {
            Position p_next = new Position(p.row + 1, p.col);
            keepFirstKPositions(visited, n_visited);
            count += wordCountHelper(grid, word.substring(1), p_next, visited);
        }

        // check left
        if (p.col != 0) {
            Position p_next = new Position(p.row, p.col - 1);
            keepFirstKPositions(visited, n_visited);
            count += wordCountHelper(grid, word.substring(1), p_next, visited);
        }

        // check right
        if (p.col != grid[0].length - 1) {
            Position p_next = new Position(p.row, p.col + 1);
            keepFirstKPositions(visited, n_visited);
            count += wordCountHelper(grid, word.substring(1), p_next, visited);
        }

        return count;
    }

    public static void keepFirstKPositions(ArrayList<Position> list, int k) {
        int size = list.size();
        if (k >= size) return;

        for (int i = 0; i < size - k; i++) {
            int idx = size - 1 - i;
            list.remove(idx);
        }
    }

    public static void main(String[] args) {
        char[][] grid = {
            {'s', 'n', 'b', 's', 'n'},
            {'b', 'a', 'k', 'e', 'a'},
            {'b', 'k', 'b', 'b', 'k'},
            {'s', 'e', 'b', 's', 'e'}
        };

        String word = "snakes";

        System.out.println("The word " + word + " appears " + wordCount(grid, word) + " times.");
    }
}

/*
	 * we need prevRow and preCol to stop going in the route we came from 
	 */
	public static int findOccurence(char[][] a, int row, int col, String text,
			int textIndex, int prevRow, int prevCol) {

		//base condition
		if (row < 0 || col < 0 || row >= a.length || col >= a[row].length)
			return 0;
		if (a[row][col] == text.charAt(textIndex) && textIndex == text.length()-1)
			return 1;

		int retValue = 0;

		//if character matches then try to match next character by incrementing textIndex
		if (a[row][col] == text.charAt(textIndex)) {
			if (prevRow != row + 1 || prevCol != col)//This if condition prevents going in the route we came from
				retValue += findOccurence(a, row + 1, col, text, textIndex + 1,	row, col);

			if (prevRow != row || prevCol != col + 1)//This if condition prevents going in the route we came from 
				retValue += findOccurence(a, row, col + 1, text, textIndex + 1,row, col);
			
			if (prevRow != row - 1 || prevCol != col)//This if condition prevents going in the route we came from 
				retValue += findOccurence(a, row - 1, col, text, textIndex + 1,row, col);
			
			if (prevRow != row || prevCol != col - 1)//This if condition prevents going in the route we came from 
				retValue += findOccurence(a, row, col - 1, text, textIndex + 1,row, col);
		}

		return retValue;
	}
	
	public static void main(String[] args) {
		char[][] a = { { 'S', 'N', 'B', 'S', 'N' },
				{ 'B', 'A', 'K', 'E', 'A' }, 
				{ 'B', 'K', 'B', 'B', 'K' },
				{ 'S', 'E', 'B', 'S', 'E' } };

		String str = "SNAKES";
		int result = 0;

		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++)
				result += findOccurence(a, i, j, str, 0, -1, -1);
		}

		System.out.println(result);
	}
}

/**
 * Time complexity: O(N^3)
 * Space complexity: O(1)
*/

import java.util.ArrayList;
import java.util.List;

public class FindOccurences
{
	private int count;
	private boolean[][] visited;
	private int[] dx = {0,0 ,1, -1};
	private int[] dy = {1,-1,0,0 };
	private String key;
	private char[][] input;
	private int rowCount;
	private int colCount;
	
	class Location
	{
		int x;
		int y;
		Location(int x, int y)
		{
			this.x = x;
			this.y = y;
		}
	}
	
	public int find(char[][] input, String key)
	{
		List<Location> locationList = findLocations(input, key.charAt(0));
		visited = new boolean[input.length][input[0].length];
		this.input = input;
		this.key = key;
		this.rowCount = input.length;
		this.colCount = input[0].length;
		for(Location loc : locationList)
		{
			List<Character> list = new ArrayList<Character>();
			list.add(key.charAt(0));
			search(loc.x, loc.y, list, 0);
		}
		return count;
	}
	

	private void search(int x, int y, List<Character> arrayList, int index) 
	{
	     if (index == this.key.length()-1)
	     {
	    	 StringBuffer sb = new StringBuffer();
	    	 for(int i = 0 ; i < arrayList.size() ; i++)
	    	 {
	    		 sb.append(arrayList.get(i));
	    	 }
	    	 if (sb.toString().intern().equals(this.key))
	    	 {
	    		 count++;
	    	 }
	    	 return;
	     } 
	     else 
	     {
	        if (arrayList.get(arrayList.size()-1) != this.key.charAt(index))
	        {
	        	return;
	        }
	     }
		
	     for(int i = 0 ; i < 4 ; i++)
	     {	 
	    	 if (valid(x+dx[i], y+dy[i]))
	    	 {
	             arrayList.add(input[x+dx[i]][y+dy[i]]);
	             visited[x+dx[i]][y+dy[i]] = true;
	             search(x+dx[i], y+dy[i], arrayList, index+1);
	             visited[x+dx[i]][y+dy[i]] = false;
	             arrayList.remove(arrayList.size()-1);	             
	    	 }
	     }
	}


	private boolean valid(int i, int j) 
	{
	    return (i>= 0 && i < rowCount && j >=0 && j < colCount && visited[i][j] == false);
		
	}


	private List<Location> findLocations(char[][] input, char key)
	{
		List<Location> retVal = new ArrayList<Location>();
	    for(int i = 0 ; i < input.length ; i++)
	    {
	    	for(int j = 0 ; j < input[0].length ; j++)
	    	{
	    		if (input[i][j] == key)
	    		{
	    			retVal.add(new Location(i,j));
	    		}
	    	}
	    }
        return retVal;
	}


	/**
	 * @param args
	 */
	public static void main(String[] args) 
	{
		char[][] a = { { 'S', 'N', 'B', 'S', 'N' },
				       { 'B', 'A', 'K', 'E', 'A' }, 
				       { 'B', 'K', 'B', 'B', 'K' },
				       { 'S', 'E', 'B', 'S', 'E' } };

		String str = "SNAKES";
		int result = new FindOccurences().find(a, str);
		System.out.println(result);
	}

}

Here is the code in C :)

#include <stdio.h>
#include <conio.h>
#include <string.h>

int row=4,col=5;

int occur(char a[][5],int x,int y,char targ[],int index,int n)
{
	if(x<0||y<0||x>=row||y>=col)
		return 0;
	if(index>n)
		return 0;
	if(a[x][y]!=targ[index])
	{
			return 0;
	}
	if(index==strlen(targ)-1)
	{
		return 1;
	}
	return (occur(a,x,y+1,targ,index+1,n)	
		+occur(a,x+1,y,targ,index+1,n)
		+occur(a,x-1,y,targ,index+1,n)
		+occur(a,x,y-1,targ,index+1,n));
		
}
int count(char a[][5],char targ[])
{
	int d=0;
	for(int i=0;i<row;i++)
	{
		for(int j=0;j<col;j++)
		{
			if(a[i][j]=='S')
				d+=occur(a,i,j,targ,0,strlen(targ)-1);
		}
	}
	return d;
}

int main()
{
	char a[][5]={{'S','N','B','S','N'},{'B','A','K','E','A'},{'B','K','B','B','K'},{'S','E','B','S','E'}};
	char c[]={"SNAKES"};
	printf("No of occurences are %d ",count(a,c));

}

#include "stdafx.h"
#include <iostream>

using namespace std;
int moveAndCheckRemainingString(char a[][5],char* c, int starttingIndex , int length, int i , int j, int arrayH, int Dir);
bool isMoveValid(int i, int j , int arrayH, int arrayL);
bool isRightBan(int Dir);
bool isLeftBan(int Dir);
bool isUpBan(int Dir);
bool isDownBan(int Dir);

int main()
{
char a[][5]={{'S','N','B','S','N'},{'B','A','K','E','A'},{'B','K','B','B','K'},{'S','E','B','S','E'}};
char c[]={"SNAKES"};
int i = 0;
int j = 0;
int occurance = 0;
for(;i< 4 ; i++)
for(; j< 5 ; j++)
{
if(a[i][j] == 'S')
{
occurance += moveAndCheckRemainingString(a, c, 1, 6, i, j, 4 ,-1);
}

}
cout << "occurance : " << occurance;
return 0;
}

int moveAndCheckRemainingString(char a[][5],char* c, int starttingIndex , int length, int i , int j, int arrayH, int Dir)
{
int occ = 0;
if(starttingIndex == length-1)
{
return 1;
}

// check right move
if(isMoveValid(i, j+1, arrayH, 5) && !isRightBan(Dir) && a[i][j+1] == c[starttingIndex])
{
occ += moveAndCheckRemainingString(a, c, starttingIndex+1, length, i, j+1, arrayH, 2);
}

// check left
if(isMoveValid(i, j-1, arrayH, 5) && !isLeftBan(Dir) && a[i][j-1] == c[starttingIndex])
{
occ += moveAndCheckRemainingString(a, c, starttingIndex+1, length, i, j+1, arrayH, 1);
}

// check Up
if(isMoveValid(i+1, j, arrayH, 5) && !isUpBan(Dir) && a[i+1][j] == c[starttingIndex])
{
occ += moveAndCheckRemainingString(a, c, starttingIndex+1, length, i+1, j, arrayH, 3);
}

// Check down
if(isMoveValid(i, j-1, arrayH, 5) && !isDownBan(Dir) &&a[i-1][j] == c[starttingIndex])
{
occ += moveAndCheckRemainingString(a, c, starttingIndex+1, length, i-1, j, arrayH, 4);
}

return occ;
}

bool isMoveValid(int i, int j , int arrayH, int arrayL)
{
return (i<arrayH) && (j < arrayL);
}

// 1 = left
// 2 = right
// 3 = up
// 4 = down
bool isRightBan(int Dir)
{
if(Dir == 1)
{
return true;
}

return false;
}

bool isLeftBan(int Dir)
{

if(Dir == 2)
{
return true;
}

return false;
}




bool isUpBan(int Dir)
{
if(Dir == 4)
{
return true;
}

return false;

}

bool isDownBan(int Dir)
{
if(Dir == 3)
{
return true;
}

return false;
}

#include<stdio.h>
#include<string.h>
int count,len;
char a[100][100],s[50],cc;
int m,n;
int vis[100][100];
int see;
void dfs(int i,int j){
	vis[i][j]=1;
	if(see==len){
		count++;
		return;
	}
	if(i-1>=0 && j>=0){
		if(s[see]==a[i-1][j] && vis[i-1][j]==0){
			see++;
			dfs(i-1,j);
			vis[i-1][j]=0;
			see--;
		}
	}
	if(i>=0 && j-1>=0){
		if(s[see]==a[i][j-1] && vis[i][j-1]==0){
			see++;
			dfs(i,j-1);
			vis[i][j-1]=0;
			see--;
		}
	}
	if(i+1>=0 && j>=0){
		if(s[see]==a[i+1][j] && vis[i+1][j]==0){
			see++;
			dfs(i+1,j);
			vis[i+1][j]=0;
			see--;
		}
	}
	if(i>=0 && j+1>=0){
		if(s[see]==a[i][j+1] && vis[i][j+1]==0){
			see++;
			dfs(i,j+1);
			vis[i][j+1]=0;
			see--;
		}
	}
}
int main(){
	scanf("%d %d",&m,&n);
	count=0;
	for(int i=0;i<m;i++){
		scanf("%c",&cc);
		for(int j=0;j<n;j++){
			scanf("%c",&a[i][j]);
			vis[i][j]=0;
		}
	}
	scanf("%c",&cc);
	scanf("%s",s);
	len=strlen(s);
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			if(a[i][j]==s[0]){
				see=1;
				dfs(i,j);
			}
		}
	}
	printf("%d\n",count);
	return 0;
}

Input :
4 5
snbsn
bakea
bkbbk
sebse
snakes

Output :
3

Would it be easier to look for the string backwards? like.. "EKANS", that way you dont have to remember if you found "AKE" from "SNAKE" along the way if there is another "SN" next to the "A" later on.. just go from right to left till you hit every letter you want.

int EightDMove[8][2] = { { 0,1},{1,0},{1,1},{0,-1},{-1,0},{-1,-1},{1,-1},{-1,1} };
#define IS_VALID_MOVE(i,j) ( i>=0 && i<4 && j>=0 && j<5 )

int countOccZigZag(char maze[4][5], int i, int j, char *in)
{
	/* Yes Match found and ends here */
	if(*in == '\0')
	  return 1;
	
    /* yet to match something */
	int sum =0;
	for (int k =0 ;k<8;k++)
	{   int a = i+EightDMove[k][0];
	    int b =i+EightDMove[k][1];
		if(IS_VALID_MOVE(a,b) && maze[a][b] == *in)
		{
			sum += countOccZigZag(maze,a,b,in+1);
		}
	}	
	return sum;
}

void test()
{
	/* Initilaize the board and text */
	char p[4][5] = {
                   {'S', 'N', 'B', 'S', 'N'},
                   {'B', 'A', 'K', 'E', 'A'},
                   {'B', 'K', 'B', 'B', 'K'},
                   {'S', 'E', 'B', 'S', 'E'}
                 };
   char target[] = {'S','N','A','K','E','\0'};
   
   /* Call the util when there is a match */
   int sum =0;
   for (int i=0 ;i<4;i++)
     for (int j=0;j<5;j++)
       if (p[i][j] == *target )
         sum += countOccZigZag(p,i,j,target+1);
   printf ("Count : %d",sum);
}

A bruteforce recursion based solution in java without any optimization

public class SnakeFinder {
	public static char board[][];
	public static char[] tstr;
	public static int maxr, maxc;

	public static void main(String args[]) {
		String str[] = { "SNBSN", "BAKEA", "BKBBK", "SEBSE" };
		maxr = str.length;
		maxc = str[0].length();
		board = new char[maxr][maxc];
		for (int s = 0; s < str.length; s++)
			board[s] = str[s].toCharArray();
		tstr = "SNAKES".toCharArray();
		int count = 0;
		for (int r = 0; r < maxr; r++) {
			for (int c = 0; c < maxc; c++) {
				if (board[r][c] == tstr[0]) {
					count += find(r, c, 1);
				}// if end
			}// for c end
		}// for r end
		System.out.println(count);
	}// end of main

	//searches for the character targetString[i] from r, c
	public static int find(int r, int c, int i) {
		if (i == tstr.length)
			return 1;
		
		int count = 0;
		if (r - 1 > -1 && board[r-1][c] == tstr[i])
			count += find(r - 1, c, i + 1);
		if (r + 1 < maxr  && board[r+1][c] == tstr[i])
			count += find(r + 1, c, i + 1);
		if (c - 1 > -1 && board[r][c-1] == tstr[i])
			count += find(r, c - 1, i + 1);
		if (c + 1 < maxc && board[r][c+1] == tstr[i])
			count += find(r, c + 1, i + 1);
		return count;
	}

}

/*
How many occurrences of a given search word can you find in a two-dimensional array
of characters given that the word can go up, down, left, right, and around 90 degree bends?
*/
int findSnake(char board[4][5], int x, int y, string word, int index,
              vector<pair<int,int> > path) {

    int back = (int)word.size() - 1;
    char letter = word[index];

    // base case: out of bounds
    if(x < 0 || y < 0 || x > 3 || y > 4) {
        return 0;
    }

    // base case: already visited
    if(find(path.begin(), path.end(), pair<int,int>(x,y)) != path.end()) {
        return 0;
    }
    path.push_back(pair<int,int>(x,y));
    cout << "Visit (" << x << "," << y << ")" << endl;

    // base case: snake chain broken
    if(board[x][y] != letter) {
        return 0;
    }

    // base case: snake chain succeeded
    if(index == back) {
        return 1;
    }

    int count = 0;
    count += findSnake(board, x+1, y, word, index+1, path);
    count += findSnake(board, x, y+1, word, index+1, path);
    count += findSnake(board, x-1, y, word, index+1, path);
    count += findSnake(board, x, y-1, word, index+1, path);
    return count;
}

int countSnakes() {
    char board[4][5] = {{'S','N','B','S','N'},
                        {'B','A','K','E','A'},
                        {'B','K','B','B','K'},
                        {'S','E','B','S','E'}};

    int count = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 5; j++) {
            vector<pair<int,int> > path;
            if (board[i][j] == 'S') {
                path.clear();
                count += findSnake(board, i, j, "SNAKE", 0, path);
                cout << "Found " << count << " snakes" << endl;
            }
        }
    }

    return count;
}

Recursion based solution in Java, that searches given word in all directions starting from every char in the input array. Tested with all possible combination, I hope it helps.

public static void main(String[] args) {
		char inputArray[][] = 
				{{'S','N','B','S','N'},
                {'B','A','K','E','A'},
                {'B','K','B','B','K'},
                {'S','E','B','S','E'}};
		String wordToSearch = "SNAKE";
		findWord(inputArray, wordToSearch);
	}

	private static void findWord(char[][] inputArray, String wordToSearch) {
		//split given word to the char array
		char[] givenWord = wordToSearch.toCharArray();
		int countOfMatches = 0;
		//find all possible word, with the same length as provided
		for (int col = 0; col<inputArray.length; col++) {
			for (int row = 0; row<inputArray[col].length; row++) {
				//If the first chat matches the array element, start to search
				int startChar = 0;
				if (givenWord[startChar]==inputArray[col][row]) {
					countOfMatches += findWord(inputArray, givenWord, col, row, startChar+1);
				}
			}
		}
		System.out.println(String.format("Found the word: %s %d times", 
				wordToSearch, countOfMatches));
	}
	private static int findWord(char[][] inputArray, char[] wordToSearch,
			int col, int row, int startChar) {
		//Check if the end of the word is reached
		if(startChar<wordToSearch.length) {
			int result = 0;
			int[] newIndex = new int []{col,row+1};
			//Try up to bottom
			if (newIndex[1]<inputArray[col].length && wordToSearch[startChar]==inputArray[col][newIndex[1]]) {
				result += findWord(inputArray, wordToSearch, newIndex[0], newIndex[1], startChar+1);
			}
			//Try bottom to up
			newIndex[1] = row-1;
			if (newIndex[1]>=0 && wordToSearch[startChar]==inputArray[col][newIndex[1]]) {
				result+= findWord(inputArray, wordToSearch, newIndex[0], newIndex[1], startChar+1);
			}
			//Reset the row
			newIndex[1] = row;
			//Try right to left
			newIndex[0] = col-1;
			if (newIndex[0]>=0 && wordToSearch[startChar]==inputArray[newIndex[0]][row]) {
				result+= findWord(inputArray, wordToSearch, newIndex[0], newIndex[1], startChar+1);
			}
			//Try left to right
			newIndex[0] = col+1;
			if (newIndex[0]<inputArray.length && wordToSearch[startChar]==inputArray[newIndex[0]][row]) {
				result+= findWord(inputArray, wordToSearch, newIndex[0], newIndex[1], startChar+1);
			}
			return result;
		} else {
			return 1;
		}
	}

public static int countWordsInMatrix(char[][] matrix, char[] inputString) {
		int col = matrix[0].length;
		int row = matrix.length;
		int count = 0;
		for (int i = 0; i < row - 1; i++) {
			for (int j = 0; j < col - 1; j++) {
				int find = search(matrix, row, col, i, j, inputString, 0);
				count += find;
			}
		}
		return count;
	}

	public static int search(char[][] matrix, int row, int col, int i, int j,
			char[] inputString, int matchIndex) {
		if (matchIndex == inputString.length)
			return 1;
		if (matrix[i][j] != inputString[matchIndex])
			return 0;
		else {
			int count = 0;
			if (i + 1 < row)
				count += search(matrix, row, col, i + 1, j, inputString,
						matchIndex + 1);
			if (j + 1 < col)
				count += search(matrix, row, col, i, j + 1, inputString,
						matchIndex + 1);
			if (i > 1)
				count += search(matrix, row, col, i - 1, j, inputString,
						matchIndex + 1);
			if (j > 1)
				count += search(matrix, row, col, i, j - 1, inputString,
						matchIndex + 1);
			return count;
		}

}

Is palindrome can be a compared string?

So, KOK, or LOL can be a string?

My implementation below in C++ allows for reusing already visited characters. It allows users to specify a matrix size, then creates and randomly populates the matrix, then asks the user for a search string, and then runs DFS without any notion of explored nodes.

As FrederichCheng mentioned, the runtime would be O(M*N*8^(k-1)) for a large matrix of size (M, N) and a search string of length k. (Imagine for example what happens when the matrix is all A's and the search string is AA... (k times).)

#include <iostream>
#include <stack>
#include <set>

#include <string.h>
#include <stdlib.h>
#include <time.h>

typedef std::pair<int, int> Pair;
typedef std::set<Pair> NeighborSet;

int find_wordcount_from_index(char ** arr, int M, int N, int i, int j, char const * search, NeighborSet ** neighbors)
{
    if (arr[i][j] == search[0])
    { // proceed
        if (search[1] == 0)
        {
            std::cout << "Search successfully terminated at: (" << i << "," << j << ") " << std::endl;
            return 1;
        }
        
        std::cout << "Exploring: (" << i << "," << j << ")" << std::endl;

        int totalCount = 0;
        
        NeighborSet n = neighbors[i][j];
        typename NeighborSet::iterator it = n.begin();
        std::cout << "Neighbors are: ";
        for (; it != n.end(); ++it)
        {
            std::cout << "(" << it->first << "," << it->second << ") ";
        }
        std::cout << std::endl;
            
        ++search;
        for (it = n.begin(); it != n.end(); ++it)
        {
            totalCount += find_wordcount_from_index(arr, M, N, it->first, it->second, search, neighbors);
        }
        --search;
        
        return totalCount;
    }
    else 
    {
        // std::cout << "Search failure at: (" << i << "," << j << ") " << std::endl;
        return 0;
    }
}

int find_wordcount_in_matrix(char ** arr, int M, int N, char const * search)
{
    // memoize all neighbors
    NeighborSet ** neighbors = new NeighborSet*[M];
    for (int i = 0; i < M; ++i)
    {
        neighbors[i] = new NeighborSet[N];

        for (int j = 0; j < N; ++j)
        {
            int neighborsRows[] = {i-1, i, i+1};
            int neighborsCols[] = {j-1, j, j+1};
            for (int k = 0; k < 3; ++k)
            {
                for (int l = 0; l < 3; ++l)
                {
                    int row = neighborsRows[k], col = neighborsCols[l];
                    if (row >= 0 && row < M && col >= 0 && col < N)
                    {
                        if (row == i && col == j)
                        {
                            continue;
                        }
                        neighbors[i][j].insert(std::make_pair(row, col));
                    }
                }
            }
        }
    }

    int totalCount = 0;
    for (int i = 0; i < M; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            totalCount += find_wordcount_from_index(arr, M, N, i, j, search, neighbors);
        }
    }

    return totalCount;
}

int main(int argc, char ** argv)
{
    int M = 4;
    int N = 5;

    if (argc > 1)
    {
        M = atoi(argv[1]);
    }
    if (argc > 2)
    {
        N = atoi(argv[2]);
    }
    
    srand(time(NULL));

    char ** arr = new char*[M];
    for (int i = 0; i < M; ++i)
    {
        arr[i] = new char[N];
        for (int j = 0; j < N; ++j)
        {
            char r = 'A' + rand() % 26;
            arr[i][j] = r;
            std::cout << r << " "; 
        }
        std::cout << std::endl;
    }

    while (true)
    {
        std::string search;
        while (search.size() == 0)
        {
            std::cout << "Enter search string: ";
            std::cin >> search;
        }

        std::cout << "Searching for: " << search << std::endl;

        int totalCount = find_wordcount_in_matrix(arr, M, N, search.c_str());
        std::cout << "Total count is: " << totalCount << std::endl << std::endl;
    }
    return 0;
}

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

const int N = 5, 
		  M = 4;

int checkNeighbor(char arr[M][N], int i, int j, char str[], int next)
{
	if(next == strlen(str)) return 1;
	int counter = 0;

	if(arr[i - 1][j] == str[next] && i - 1 >= 0)
		counter += checkNeighbor(arr, i - 1, j, str, next + 1);

	if(arr[i + 1][j] == str[next] && i + 1 < M)
		counter += checkNeighbor(arr, i + 1, j, str, next + 1);

	if(arr[i][j - 1] == str[next] && j - 1 >= 0)
		counter += checkNeighbor(arr, i, j - 1, str, next + 1);

	if(arr[i][j + 1] == str[next] && j + 1 < N)
		counter += checkNeighbor(arr, i, j + 1, str, next + 1);

	return counter;
}

int main()
{
	char arr[M][N] = {'S', 'N', 'B', 'S', 'N', 
					  'B', 'A', 'K', 'E', 'A',
					  'B', 'K', 'B', 'B', 'K',
					  'S', 'E', 'B', 'S', 'E'},
		 str[] = "SNAKES";
	int counter = 0;
	for(int i = 0; i < M; i++)
		for(int j = 0; j < N; j++)
			if(arr[i][j] == str[0])
				counter += checkNeighbor(arr, i, j, str, 1);

	printf("%d\n", counter);
	return 0;
}

simple dfs whenever the letter 'S' is encountered.

//pat is the pattern to be searched.
//m is size of pattern,n1 & n2 dimensions of the 2-D array
void dfs(int x,int y,int index)
{
	if(x<0 || y<0 || x>=n1 || y>=n2){return;}
	if(vis[x][y]){return;}
	vis[x][y]=1;
	if(v[x][y]!=pat[index] && index==m-1){return;}
	if(v[x][y]==pat[index] && index==m-1){ans++;}
	dfs(x+1,y,index+1);
	dfs(x-1,y,index+1);
	dfs(x,y+1,index+1);
	dfs(x,y-1,index+1);
	return;
}

// java solution

public class WordCounter
{
    private static class Result
    {
        int occurrences;

        public Result(int n)
        {
            occurrences = n;
        }
    }

    public static int count(char[][] matrix, String s)
    {
        int pos;
        Result r = new Result(0);

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                pos = 0;
                count(matrix, s, i, j, pos, r);
            }
        }

        return r.occurrences;
    }

    private static void count(char[][] matrix, String s, int i, int j, int pos, Result r)
    {
        if (pos >= s.length()) return;

        char c = s.charAt(pos);

        if (matrix[i][j] != c) return;

        if ((matrix[i][j] == c) && (pos == matrix.length - 1)) {
            r.occurrences++;
            return;
        }

        if (i < matrix.length - 1)      	count(matrix, s, i + 1, j, pos + 1, r);
        if (i > 0)                      		count(matrix, s, i - 1, j, pos + 1, r);
        if (j < matrix[0].length - 1)   	count(matrix, s, i, j + 1, pos + 1, r);
        if (j > 0)					count(matrix, s, i, j - 1, pos + 1, r);
    }

    public static void main(String[] args)
    {
        char[][] matrix =   	{
                                		{'S', 'N', 'B', 'S', 'N'},
                                		{'B', 'A', 'K', 'E', 'A'},
                               	 		{'B', 'K', 'B', 'B', 'K'},
                                		{'S', 'E', 'B', 'S', 'E'}
                            		};

        String s = "SNAKE";
        int n = count(matrix, s);

        System.out.println("n = " + n);
    }
}

1) Count word by using DFS from each cell
2) Java implementation of above approach

public static int countWord(char[][] a, String word)
	{
		int wordLength = word.length();
		char[] current = new char[wordLength];
		int row = a.length;
		int col = a[0].length;
		boolean[][] visited = new boolean[row][col];

		int count = 0;

		for (int i = 0; i < row; i++)
		{
			for (int j = 0; j < col; j++)
			{
				if (!visited[i][j])
				{
					count += countWord(a, i, j, current, 0, visited, word, row, col);
				}
			}
		}
		return count;
	}

	private static int countWord(char[][] a, int i, int j, char[] current, int index, boolean[][] visited, String word,
		int row, int col)
	{
		int count = 0;

		if (isSafe(a, visited, i, j, row, col, index, word))
		{
			current[index] = a[i][j];

			if (current[index] != word.charAt(index))
			{
				return 0;
			}

			if (index == word.length() - 1)
			{
				return 1;
			}

			visited[i][j] = true;

			index++;

			count += countWord(a, i + 1, j, current, index, visited, word, row, col);
			count += countWord(a, i - 1, j, current, index, visited, word, row, col);
			count += countWord(a, i, j + 1, current, index, visited, word, row, col);
			count += countWord(a, i, j - 1, current, index, visited, word, row, col);

			visited[i][j] = false;
		}

		return count;
	}

	private static boolean isSafe(char[][] a, boolean[][] visited, int i, int j, int row, int col, int index, String word)
	{
		if ((i >= 0 && i < row) && (j >= 0 && j < col) && (!visited[i][j]) && (index < word.length()))
		{
			return true;
		}
		return false;
	}

WE can use DFS here.
First Note down all the first letter position i.e. positions of 'S'. And do DFS for every S.

There are 4 possible paths if we can bend 90 degree, If the Matrix starts from (1,1) to (5,4), Then S(4,1) N(5,1) A(5,2) K(5,3) E(5,4) S(1,4) is also a path.

I guess, This can be solved in O(m*n*k) space and time using dynamic programming approach.