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