Count Valid Words in a Grid

In this problem, you are given a grid of characters and a list of words. Your task is to determine how many words from the list can be found in the grid. A word is said to be found if it can be constructed from letters of sequentially adjacent cells, where adjacent cells are those horizontally or vertically neighboring. Each cell may be used only once in the construction of a word. This is a typical backtracking problem where you need to perform a depth-first search (DFS) on the grid to check for the existence of each word.

For example, given a 3 (\times) 4 grid and the words "abcced" and "see", if both words exist following the rules of adjacent moves, then the answer is 2.

(Note:) Any necessary formulas are represented in (\LaTeX) format.

inputFormat

The first line contains two space-separated integers (m) and (n), representing the number of rows and columns in the grid. The next (m) lines each contain (n) space-separated lowercase letters representing the grid. The following line contains an integer (k), the number of words. Each of the next (k) lines contains a word consisting of lowercase letters.

outputFormat

Output a single integer indicating the number of words that can be found in the grid according to the above rules.## sample

3 4
a b c e
s f c s
a d e e
2
abcced
see

2