/* File:    WordSearch.java
 * Created: 9/19/2018
 * Author:  Sabbir Manandhar
 *
 * Copyright (c) 2018 WorldLingo Inc.
 */

//=======================================================================================

/**
 * @author Sabbir Manandhar manandharsabbir@gmail.com
 * @version 1.0
 */
public class WordSearch {

  /**
   * Verifies if the given word can be found in the given board by moving left, right, top and bottom
   * unvisited cells of the board.
   * @param board Given board.
   * @param word Given word.
   * @return True if the word is found in the board, False otherwise.
   */
  public boolean exist(char[][] board, String word) {
    int ROW = board.length;
    int COL = board[0].length;
    for (int row = 0; row < ROW; row++) {
      for (int col = 0; col < COL; col++) {
        if (dfs(board, new boolean[ROW][COL], word, 0, row, col, ROW, COL)) return true;
      }
    }
    return false;
  } // exist

  //-------------------------------------------------------------------------------------

  /**
   * Searches for the occurrence of characters in given word from the position <code>cursor</code>
   * in the given 2D board starting from given row and col.
   *
   * @param board Input 2D board of characters
   * @param visited Visited characters in the cell
   * @param word Given input word
   * @param cursor current location in the given word
   * @param row current row in the board
   * @param col current column in the board
   * @param ROW number of Rows in the board
   * @param COLUMN number of Columns in the board
   * @return True if the word occurs in the board, False otherwise
   */
  public boolean dfs(char[][] board, boolean[][] visited, String word, int cursor, int row, int col, int ROW, int COLUMN) {
    if (cursor == word.length()) return true;
    if (!inBoard(row, col, ROW, COLUMN)) return false;
    if (visited[row][col]) return false;

    if (board[row][col] == word.charAt(cursor)) {
      visited[row][col] = true;
      boolean exist = dfs(board, visited, word, cursor + 1, row + 1, col, ROW, COLUMN) ||
          dfs(board, visited, word, cursor + 1, row, col + 1, ROW, COLUMN) ||
          dfs(board, visited, word, cursor + 1, row - 1, col, ROW, COLUMN) ||
          dfs(board, visited, word, cursor + 1, row, col - 1, ROW, COLUMN);
      if (exist) return true;
      visited[row][col] = false;
    } else {
      return false;
    }
    return false;
  } // dfs

  //-------------------------------------------------------------------------------------

  /**
   * Verify if given row and column are withing the limit
   * @param row given row
   * @param col given column
   * @param ROW ROW limit
   * @param COLUMN Column limit
   * @return True if the row and column are within the limit, False otherwise
   */
  private boolean inBoard(int row, int col, int ROW, int COLUMN) {
    return row >= 0 && row < ROW && col >= 0 && col < COLUMN;
  } // inBoard

} // WordSearch