Word Search in Grid

Given a 2D grid of characters and a target word, determine if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are those horizontally or vertically neighboring. Note that the same cell may not be used more than once in constructing the word.

The problem can be formally stated as: Given a grid ( G ) of size ( r \times c ) and a string ( W ), check if there exists a path in ( G ) such that concatenating the characters along the path yields ( W ).

Example: For a grid:

A B C E
S F C S
A D E E

• Word = ABCCED returns True.
• Word = SEE returns True.
• Word = ABCB returns False.

This problem requires implementing an efficient backtracking algorithm (depth-first search) that avoids revisiting grid cells during the search for the target word.

inputFormat

The first line of input contains two integers ( r ) and ( c ), representing the number of rows and columns in the grid. Each of the next ( r ) lines contains a string of length ( c ) representing a row in the grid. The last line contains the target word ( W ). For example:

3 4 ABCE SFCS ADEE ABCCED

outputFormat

Output a single line: either "True" if the word exists in the grid, or "False" if it does not.## sample

3 4
ABCE
SFCS
ADEE
ABCCED

True