/**
 * https://leetcode.com/problems/word-search/
 * Time O(N * 3^L) | Space O(L)
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    for(let row = 0; row < board.length; row++) {
        for(let col = 0; col < board[0].length; col++){
            if (dfs(board, row, col, word, 0)) return true;
        }
    }

    return false;
}

const dfs = (board, row, col, word, index) => {
    if (index === word.length) return true;
    if (isOutOfBound(board, row, col)) return false;
    if (board[row][col] !== word[index]) return false
        
    board[row][col] = '*';
    
    const hasWord = Object
        .values(directions(row, col))
        .filter(([r, c]) => dfs(board, r, c, word, index + 1))
        .length
    
    board[row][col] = word[index];
    return hasWord;
}

const isOutOfBound = (board, row, col) => {
    const isRowOutOfBound = row < 0 || board.length - 1 < row
    const isColOutOfBound = col < 0 || board[0].length - 1 < col 
    return isRowOutOfBound || isColOutOfBound
}

const directions = (row, col) => ({
    up: [row - 1, col],
    down: [row + 1, col],
    left: [row, col - 1,],
    right: [row, col + 1]
})