// Use a depth‑first search (DFS) from every cell that matches the first letter,
// exploring all valid directions until the full word is matched.
object WordSearch {
def dfs(
grid: Array[Array[Char]],
visited: Array[Array[Boolean]],
r: Int,
c: Int,
word: String,
index: Int
): Boolean = {
if (index == word.length)
return true
val rows = grid.length
val cols = grid(0).length
if (r < 0 || c < 0 || r >= rows || c >= cols)
return false
if (visited(r)(c))
return false
if (grid(r)(c) != word(index))
return false
visited(r)(c) = true
val found =
dfs(grid, visited, r + 1, c, word, index + 1) ||
dfs(grid, visited, r - 1, c, word, index + 1) ||
dfs(grid, visited, r, c + 1, word, index + 1) ||
dfs(grid, visited, r, c - 1, word, index + 1)
visited(r)(c) = false
found
}
def wordExist(grid: Array[Array[Char]], word: String): Boolean = {
val rows = grid.length
val cols = grid(0).length
val visited = Array.fill(rows, cols)(false)
(0 until rows).exists { r =>
(0 until cols).exists { c =>
dfs(grid, visited, r, c, word, 0)
}
}
}
def main(args: Array[String]): Unit = {
val grid = Array(
Array('a', 'b', 'c', 'e'),
Array('s', 'f', 'c', 's'),
Array('a', 'd', 'e', 'e')
)
val word = "see"
val result = wordExist(grid, word)
println(if (result) 1 else 0)
}
}
/*
run:
1
*/
