Problem C
Ascii Art(Hard)
Don is a hard-core algorithms
programmer. He’s recently been interested in an OS developer
named Joan he met in a competitive programming forum. They
spend all night exchanging ASCII art over IRC. She was telling
him about an idea she had for an ASCII image search. Given a
search image and a template image, she would be able to find
any pictures with a particular face!
The next day, Don was surprised to hear that Joan had asked you for help instead of him! Deing as clever as he is, quickly made some calculations and came up with some very tricky test cases. You should update your program before he sends them to Joan!
The problem format is the same as in "asciiarteasy" except that the images could be anything
Input
The first line of the input contains four integers $W_ S, H_ S, W_ T, H_ T$ where $0<W_ S,H_ S<=1000, 0<W_ T<=W_ S, 0<H_ T<=H_ S$.
This is followed by a sample ASCII image comprised of $H_ S$ lines containing $W_ S$ characters. Then follow $H_ T$ lines containing $W_ T$ characters that comprise the template image.
Output
If you find the entire template image in the sample image, your program should output two integers $X$ and $Y$ on one line, where $(X, Y)$ is the position of the top left character of the top-most, left-most match. If such a match does not exist, your program will output no match.
Positions on the image start from $(0,0)$ at the top left and continue until $(W_ S, H_ S)$. Assume $0<=X<=W_ S-W_ T$ and $0<=Y<=H_ S-H_ T$.
Sample Input 1 | Sample Output 1 |
---|---|
42 11 4 3 #----------------------------------------# # ______________________________________ # #/ Does an ASCII cow \# #\ produce Unicode milk? /# # -------------------------------------- # # \ ^__^ # # \ (oo)\_______ # # (__)\ )\/\ # # ||----w | # # || || # #----------------------------------------# ^__^ (oo) (__) |
12 5 |
Sample Input 2 | Sample Output 2 |
---|---|
14 8 2 1 *------------* | /))))))))) | |//) __ __\| |C==/_o|^|o_\| || _\ )| | \ .--. / | |_/`-. __./_ | *------------* <3 |
no match |