//-------------------------------------------------------------------
// File			:search.C
// Author		:Alicia Thorsen
// Course		:CS1129 
//
// Functions to find a word on a Boggle board
//-------------------------------------------------------------------

#include "search.h"
#include "board.h"

#include <iostream>
#include <string>
using namespace std;

//-------------------------------------------------------------------
// Precondition   :The Boggle board is loaded and word contains the search 
// word
// Postcondition  :Returns if the word was found on the board
//-------------------------------------------------------------------

bool findWord(char board[][SIZE], string word) {
  bool used[SIZE][SIZE];

  //Explore each location as a possible starting point
  for (int i = 0; i < SIZE; i++)
    for (int j = 0; j < SIZE; j++) {    
      //Make sure all letters are marked as not used
      reset(used);

      //Try to find word from this location
      if (exploreLocation(word, 0, i, j, board, used))
        return true;
    }
  return false;
}//end findWord()

//-------------------------------------------------------------------
// Precondition   :The Boggle board is loaded and s is the search word
// Postcondition  :Returns if the word was found on the board and
// marks the letters which were used
//-------------------------------------------------------------------

bool exploreLocation(string s, int i, int currRow, int currCol, 
    char board[][SIZE], bool used[][SIZE]) {
  // Directions.
  int up = currRow - 1, down = currRow + 1, left = currCol-1, 
  right = currCol+1;

  //Next letter to visit
  int next = i + 1;

  //Check if we've found the word (matched all letters already)
  if (i == s.length())
    return true;

  //Check if we're still on the board
  if ((currRow < 0) || (currRow >= SIZE) || (currCol < 0) || 
      (currCol >= SIZE))
    return false;

  //Check if this letter matches
  if (s[i] != board[currRow][currCol])
    return false;

  //Check if we've used this letter before
  if (used[currRow][currCol])
    return false;

  //Letter matches, and we haven't used it so use it
  used[currRow][currCol] = true;

  //Look for rest of the word in all eight directions
  if (exploreLocation(s, next,  up, currCol, board, used))
    return true;

  if (exploreLocation(s, next, down, currCol, board, used))
    return true;

  if (exploreLocation(s, next, currRow, left, board, used))
    return true;

  if (exploreLocation(s, next, currRow, right, board, used))
    return true;

  if (exploreLocation(s, next, up, left, board, used))
    return true;

  if (exploreLocation(s, next, up, right, board, used))
    return true;

  if (exploreLocation(s, next, down, left, board, used))
    return true;

  if (exploreLocation(s, next, down, right, board, used))
    return true;

  //We searched all directions and we're still here
  //so we did not find the word. Therefore we didn't use
  //this letter
  used[currRow][currCol] = false;
  
  // Special case for Q. Use the implied u.
  if (s[i] == 'q') {
    // Check for word using Qu on the same tile.
    if ((i < s.length() - 1) && (s[i + 1] == 'u')) {
      // Erase the u and try the search again.
      s = s.erase(i + 1, 1);
      if (exploreLocation(s, i, currRow, currCol, board, used))
        return true;
    }
  }

  return false;
}//end exploreLocation()

//-------------------------------------------------------------------
// Precondition	    :None	
// Postcondition    :Used aray is set to false
//-------------------------------------------------------------------

void reset(bool used[][SIZE]) {
  for (int i =0; i < SIZE; i++)
    for (int j = 0; j < SIZE; j++)
      used[i][j] = false;

}//end reset()