// https://leetcode.com/problems/word-search
fun exist(board: Array<CharArray>, word: String): Boolean {
    val visited = Array(board.size) { BooleanArray(board.first().size) }
    for (row in board.indices) {
        for (col in board.first().indices) {
            if (dfs(row = row, col = col, index = 0, word = word, board = board, visited = visited)) {
                return true
            }
        }
    }
    return false
}

fun dfs(
    row: Int,
    col: Int,
    index: Int,
    word: String,
    board: Array<CharArray>,
    visited: Array<BooleanArray>
): Boolean {
    if (visited[row][col] || board[row][col] != word[index]) return false
    if (index == word.lastIndex) return true
    visited[row][col] = true
    if (board.valid(row - 1, col) && dfs(row - 1, col, index + 1, word, board, visited)) return true
    if (board.valid(row + 1, col) && dfs(row + 1, col, index + 1, word, board, visited)) return true
    if (board.valid(row, col - 1) && dfs(row, col - 1, index + 1, word, board, visited)) return true
    if (board.valid(row, col + 1) && dfs(row, col + 1, index + 1, word, board, visited)) return true
    visited[row][col] = false
    return false
}

private fun Array<CharArray>.valid(row: Int, col: Int): Boolean {
    return row >= 0 && row <= this.lastIndex && col >= 0 && col <= this.first().lastIndex
}

// https://leetcode.com/problems/word-search
fun exist(board: Array<CharArray>, word: String): Boolean {
    val visited = Array(board.size) { BooleanArray(board.first().size) }
    for (row in board.indices) {
        for (col in board.first().indices) {
            if (dfs(row = row, col = col, index = 0, word = word, board = board, visited = visited)) {
                return true
            }
        }
    }
    return false
}

fun dfs(
    row: Int,
    col: Int,
    index: Int,
    word: String,
    board: Array<CharArray>,
    visited: Array<BooleanArray>
): Boolean {
    if (visited[row][col] || board[row][col] != word[index]) return false
    if (index == word.lastIndex) return true
    visited[row][col] = true
    if (board.valid(row - 1, col) && dfs(row - 1, col, index + 1, word, board, visited)) return true
    if (board.valid(row + 1, col) && dfs(row + 1, col, index + 1, word, board, visited)) return true
    if (board.valid(row, col - 1) && dfs(row, col - 1, index + 1, word, board, visited)) return true
    if (board.valid(row, col + 1) && dfs(row, col + 1, index + 1, word, board, visited)) return true
    visited[row][col] = false
    return false
}

private fun Array<CharArray>.valid(row: Int, col: Int): Boolean {
    return row >= 0 && row <= this.lastIndex && col >= 0 && col <= this.first().lastIndex
}
