Imports System
' use a depth‑first search (DFS) from every cell that matches the first letter,
' exploring all valid directions until the full word is matched.
Module WordSearch
Function DFS(grid As Char(,), visited As Boolean(,),
r As Integer, c As Integer,
word As String, index As Integer) As Boolean
If index = word.Length Then
Return True
End If
Dim rows As Integer = grid.GetLength(0)
Dim cols As Integer = grid.GetLength(1)
If r < 0 OrElse c < 0 OrElse r >= rows OrElse c >= cols Then
Return False
End If
If visited(r, c) Then
Return False
End If
If grid(r, c) <> word(index) Then
Return False
End If
visited(r, c) = True
Dim found As Boolean =
DFS(grid, visited, r + 1, c, word, index + 1) OrElse
DFS(grid, visited, r - 1, c, word, index + 1) OrElse
DFS(grid, visited, r, c + 1, word, index + 1) OrElse
DFS(grid, visited, r, c - 1, word, index + 1)
visited(r, c) = False
Return found
End Function
Function WordExist(grid As Char(,), word As String) As Boolean
Dim rows As Integer = grid.GetLength(0)
Dim cols As Integer = grid.GetLength(1)
Dim visited(rows - 1, cols - 1) As Boolean
For r As Integer = 0 To rows - 1
For c As Integer = 0 To cols - 1
If DFS(grid, visited, r, c, word, 0) Then
Return True
End If
Next
Next
Return False
End Function
Sub Main()
Dim grid As Char(,) = {
{"a"c, "b"c, "c"c, "e"c},
{"s"c, "f"c, "c"c, "s"c},
{"a"c, "d"c, "e"c, "e"c}
}
Dim word As String = "see"
Dim result As Boolean = WordExist(grid, word)
Console.WriteLine(If(result, 1, 0))
End Sub
End Module
' run:
'
' 1
'
