Word Search in a Grid

Given an m x n 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 horizontally or vertically neighboring. Note that the same letter cell cannot be used more than once.

Formally, if we denote the grid by \( grid[i][j] \) then starting from some cell \( grid[i][j] \), you can only move to \( grid[i+1][j] \), \( grid[i-1][j] \), \( grid[i][j+1] \), or \( grid[i][j-1] \). The search stops when either the entire word is found or all possible paths have been explored.

inputFormat

The input is given via standard input (stdin) in the following format:

1. The first line contains two integers \( m \) and \( n \) which represent the number of rows and columns in the grid.
2. The next \( m \) lines each contain \( n \) space-separated characters representing the grid.
3. The last line contains the target word.

outputFormat

Print a single line to standard output (stdout): print true if the word exists in the grid, otherwise print false.

3 4
A B C E
S F C S
A D E E
ABCCED

true