Problem H
Palindromic Paths
In this problem you will be presented with a rectangular grid containing a number of palindromic sentences, one character per cell. They will be spelled out in a path of adjacent cells going in any direction. No cell will be used more than once in a palindrome, though it could be reused in other palindromes. The palindromes will be punctuated, the words will be spaced, and normal capitalization will be done. Your task is to look for palindromes from a list that is provided to you and declare whether or not each exists in the grid.
Input
The first line will contain the number of rows, $r$, and columns, $c$, of the grid, $1 \le r,c \le 100$. The following $r$ lines (one for each row) will contain the $c$ characters for that row of the grid. The next line will contain the number of palindromes, $p$, to search for, $1 \le p \le 100$. The following $p$ lines will contain the palindromes, one per line.
Output
Format the output similar to the sample output below. Start with “Case”, a space, and the number of the case (in the order given). Then a colon ‘:’ and a space. Next output your answer, “Yes” or “No”, for if the palindrome exists in the grid. Print out 4 spaces “ ”, and finally the palindrome that you were given, to finish the line.
| Sample Input 1 | Sample Output 1 |
|---|---|
16 21 G.esI.JbCyda desoH? h wOstep ,ixi.NHc bntaC pSfawnohgegwqInvmtFve pkt onnai .tndb mzevk Siep. rutenn, Obasdt fhkitac?ajbae?ivtrsIn xeetib vtfpmkwhdiio t rdfcnTopoI sagvs sktr orUtoacoi oghi ik.eda tbWas it taketihmfrgl ehbwsgjha cwpcIovtfik jhals mxiyngwz jseicg .lbrjviicedcan.h,s.at a hkwgttine xvcrewlpm ueonvO i,KhRyfhkpjoev ghubrenn tpikdsymbwlg 7 Sit on a potato pan, Otis. Cigar? Toss it in the can. It is so tragic. Taco cat. Step on no pets. Was it a cat I saw? Never odd or even. Do geese see God? |
Case 1: Yes Sit on a potato pan, Otis. Case 2: Yes Cigar? Toss it in the can. It is so tragic. Case 3: Yes Taco cat. Case 4: Yes Step on no pets. Case 5: Yes Was it a cat I saw? Case 6: No Never odd or even. Case 7: No Do geese see God? |
