import java.util.*;

class Position
{
    public Position(int r,int c)
    {
	row = r;
	col = c;
    }
    int row;
    int col;
}

public class JoggleGraph
{
    public final static int ALPH = 26;
    
    public JoggleGraph(Vector words)
    {
	myLetters = new Vector[ALPH];
	int k;
	for(k=0;k < ALPH; k++)
	{
	    myLetters[k] = new Vector();
	}
	myVisited = new boolean[ALPH];
	myWords = words;
    }

    public void init(char board[][])
    {
	int j;
	int k;
	mySize = board[0].length;

	// clear old vectors

	for(j=0; j < ALPH; j++)
	{
	    myLetters[j].removeAllElements();
	}
	
	for(j=0; j < mySize; j++)
	{
	    for(k=0; k < mySize; k++)
	    {
		myLetters[charToInt(board[j][k])].addElement(new Position(j,k));
	    }
	}
    }

    public boolean isWord(String s)
    {
	int k;
	for(k=0; k < ALPH; k++)
	{
	    myVisited[k] = false;
	}
	Enumeration e = myLetters[charToInt(s.charAt(0))].elements();
	while (e.hasMoreElements())
	{
	    if (checkString((Position)e.nextElement(),s))
	    {
		return true;
	    }
	}
	return false;
    }

    boolean checkString(Position pos,String s)
    {
	int loc = pos.row * mySize + pos.col;

	if(myVisited[loc])
	{
	    return false;
	}

	if(s.length()==1)
	{
	    return true;
	}

	myVisited[loc] = true;
	Enumeration e = myLetters[charToInt(s.charAt(1))].elements();
	while (e.hasMoreElements())
	{
	    Position p = (Position) e.nextElement();
	    if (isNeighbor(pos,p) &&
		checkString(p,s.substring(1)))
	    {
		return true;
	    }
	}
        myVisited[loc] = false;
	return false;
    }
    
    int charToInt(char ch)
    {
	return (int) (ch - 'a');
    }

    boolean isNeighbor(Position m, Position n)
    {
	int rowdiff = m.row - n.row;
	int coldiff = m.col - n.col;
	return m != n && (rowdiff*rowdiff + coldiff*coldiff <=2);
    }    

    private Vector[] myLetters;
    private boolean[] myVisited;
    Vector myWords;
    int mySize;
}