Algorithm

We can solve this using backtracking. Starting from each cell in the grid, we explore all four possible directions (up, down, left, right) to try to match the next character in the word. We mark visited cells temporarily to avoid reusing them, and backtrack when a path fails. This ensures we explore all possible connected sequences of characters in the board that might form the target word.

Iterate through each cell in the board.
If the cell matches the first letter of the word, start a DFS search from that cell.
In DFS, check boundary conditions and whether the character matches the current letter in the word.
If matched, temporarily mark the cell as visited.
Recursively search in all four directions for the next letter.
If the whole word is found, return true.
Backtrack by restoring the cell’s original value before returning.
If no path matches the word, return false.