#include <iostream>
#include <fstream>
#include <cctype>
using namespace std;

const int SIZE = 8;
enum direction{U, UR, R, DR, D, DL, L, UL};

bool findWord(char puzzle[][SIZE], string word);
void readPuzzle(char puzzle[][SIZE]);
bool search(string, char puzzle[][SIZE], int, int, int, int);

int main() {
  string word;
  char puzzle[SIZE][SIZE];
  int score = 0;

  readPuzzle(puzzle);

  cout << "\nEnter words to search for or Q to quit:" << endl;
  getline(cin, word);

  while ((word != "Q") && (word != "q")) {
    if(findWord(puzzle, word)) {
      cout << "Found" << endl;
      score++;
    } else
      cout <<"Not found" << endl;
    
    cout << endl;
    getline(cin, word);
  }
  cout << "Final Score: " << score << endl;
  return 0;
}

bool findWord(char puzzle[][SIZE], string word) {
  // Look for the first letter of the word on the board.
  for(int i = 0; i < SIZE; i++) 
    for(int j = 0; j < SIZE; j++)
      if(tolower(puzzle[i][j]) == tolower(word[0]))
        // Search in every direction for the rest of the word.
        for(int d = U; d <= UL; d++) 
          if(search(word, puzzle, d, 0, i, j))
            return true;
  return false;
}

bool search(string word, char puzzle[][SIZE], int dir, int index, int row,
    int	col) {
  if(index == word.length())
    return true;

  if(row < 0 || row >= SIZE || col < 0 || col >= SIZE )
    return false;

  if(tolower(puzzle[row][col]) != tolower(word[index]))
    return false;

  // Directions with up or down
  if (dir == U || dir == UL || dir == UR)
    row--;
  else if (dir == D || dir == DL || dir == DR)
    row++;

  // Directions with left or right.
  if (dir == L || dir == UL || dir == DL)
    col--;
  else if (dir == R || dir == UR || dir == DR)
    col++;
  
  return search(word, puzzle, dir, index + 1, row, col);
}

void readPuzzle(char puzzle[][SIZE]) {
  ifstream in("input");

  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++) {
      in >> puzzle[i][j];
      cout << puzzle[i][j] << " ";
    }
    cout << endl;
  }	
  in.close();
}