| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12197 | Word Puzzle (Quiz) |
|
Description
What:
The Data Structures TAs enjoy making word puzzles. They aren't good at it though, and sometimes forget some words. They want to write a program to help them check the solutions.
Help them build that program!
You will be given 3 things: the word puzzle dimension, the word puzzle, and the words you should look for. Read the ‘input’/ ‘output’ part below for details.
The words are in one direction, either horizontal or vertical, no diagonals. Words can be read from left to right, right to left, up to bottom or bottom to up.
Example:
For example, take the word puzzle below:
Words: cool cat vain soul
The first word, cool, begins at row 1, col 0 and ends at row 4, col 0. You should return:
cool Yes 1,0-4,0 oocl
The second word, cat, begins at row 0, col 2 and ends at row 0, col 4. You should return:
cat Yes 0,2-0,4 act
The third word, vain, begins at row 4, col 4 and ends at row 4, col 1. You should return:
vain Yes 4,4-4,1 aivn
The last word, soul, is not in the matrix. You should return:
soul No
HINT: use queue/stack to solve this problem.
Input
1 line: an integer n and a new line character → matrix dimension (n*n)
n lines: n lines of n characters followed by a new line character → word puzzle layout
1 line: an integer m → the number of words you need to find
1 line: m words separated by spaces, new line character at the end → list of m words you should find in the puzzle
(n+2 lines in total)
Output
You should output m lines of coordinates, one for each word in the wordlist, in the same order you read them,followed by a new line character at the end.
For each line, you should return (separated by spaces) :
-
If the word is in the matrix:
-
The word
-
The string: Yes
-
The coordinates, written like “x1,y1-y2,x2”, with 4 integers x1,x2,y1,y2 separated by commas and a dash(-), with a newline character at the end. Integers 1 and 3 should be rows, 2 and 4 should be columns.
-
The rearranged word (vowels first, consonants afterwards)
-
If the word is in the matrix:
-
The word
-
The string: No