Loading...
Loading...
Loading...
For the college fest, the quiz club makes a letter grid puzzle. A word is hidden in the grid if you can spell it by starting at some cell and moving one step up, down, left or right for each next letter. The same cell cannot be used twice in one word.
For each of q words, print YES if it is hidden in the grid, otherwise NO.
YES or NO for each word, in the input order.Example 1
Input
3 4 fest aqui club 5 fest faq suit bus fef
Output
YES YES YES NO NO
faq goes down then right, and suit turns a corner. bus fails because no s is next to a u that is next to b. fef would need the f twice.
Example 2
Input
1 1 a 2 a aa
Output
YES NO
A one-letter word needs one cell. aa would use the only cell twice.
Try the problem first. Open one hint at a time.
Try every cell as the starting cell. From a cell, the next letter must be in one of its four side neighbours.
Write a method find(row, col, index) that returns true if the word from position index onwards can be spelled starting at that cell.
Mark the cell as used before you look at its neighbours, and unmark it before you return, so other paths can use it later.
Stop as soon as one path works. Return false early when the cell is outside the grid, already used, or has the wrong letter.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor