1161 . Wrong Answer
Description
You are solving a crossword puzzle and you have already written down the answers to all questions. While ?lling in the answers in the diagram, you notice that some answers have overlapping letters that do not match, so you must have made some mistakes in the answers. Instead of checking your answers, you decide to write a computer program to ?nd the maximum number of answers that could have been correct.
Input Format
The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:
- One line with two integers H and V, satisfying 1<= H, V<=500: the number of horizontal and vertical words, respectively.
- H lines, one for each horizontal word, each with two integers x and y and a string W, satisfying 0<= x, y<= 1000 and 1<= Length(W)<= 1000: the location of the first letter and the answer.
- V lines, one for each vertical word, each with two integers x and y and a string W, satisfying 0<= x, y<= 1000 and 1<= Length(W)<= 1000: the location of the first letter and the answer.
The top left corner of the diagram is at x = y = 0, x runs in the horizontal direction, and y runs in the vertical direction (downwards).
Output Format
For every test case in the input, the output should contain a single number, on a single line: the
maximum number of answers that can fit in the crossword.
Sample Input 1
2 2 2 0 1 BAPC 0 2 LEIDEN 0 0 SOLUTION 2 1 WINNER 1 4 0 1 HELLO 1 0 HI 2 0 BYE 3 0 GOODBYE 4 0 FAREWELL
Sample Output 1
3 4
Hints
Problem Source
Migrated from old NTUJ.
2010 Benelux Algorithm PC
Subtasks
| No. | Testdata Range | Score |
|---|