object WordSearch { def main(args: Array[String]): Unit = { val board = Array( Array('A', 'B', 'C', 'E'), Array('S', 'F', 'C', 'S'), Array('A', 'D', 'E', 'E') ) val word = "ABCCED" val result = exist(board, word) if (result) println(s"The word '$word' exists in the board.") else println(s"The word '$word' does not exist in the board.") } def exist(board: Array[Array[Char]], word: String): Boolean = { val rows = board.length val cols = board(0).length val visited = Array.ofDim[Boolean](rows, cols) def dfs(row: Int, col: Int, wordIndex: Int): Boolean = { if (wordIndex == word.length) { // We have successfully matched all characters in the word. return true } if (row < 0 || row >= rows || col < 0 || col >= cols || visited(row)(col) || board(row)(col) != word(wordIndex)) { // Out of bounds, already visited, or mismatched character. return false } // Mark the current cell as visited. visited(row)(col) = true // Explore adjacent cells in all four directions. val directions = Array((0, 1), (0, -1), (1, 0), (-1, 0)) for ((dr, dc) <- directions) { val newRow = row + dr val newCol = col + dc if (dfs(newRow, newCol, wordIndex + 1)) { // If any of the recursive calls returns true, we have found a valid path. return true } } // Mark the current cell as unvisited (backtrack). visited(row)(col) = false false } // Start DFS from each cell in the grid. for (row <- 0 until rows) { for (col <- 0 until cols) { if (dfs(row, col, 0)) { return true } } } false } }