904 . Domino!
TopCoder
Description
Alice and Bob are playing a game using a chessboard and 1x2 dominoes.
First, Alice selects an arbitary region on the chessboard. Bob has to cover that region by non-overlapping 1x2 dominoes, and avoids the two distasteful pattern shown below.
For example, two possible tilings of a 3x4 rectangular region is shown,
the first one is tasteful, while the second is not, due to the vertical dominoes in the upper right corner.
Bob is stupid, he can only cover the region by dominoes, but maybe lots of distasteful pattern on it.
Can you help Bob modify his solution to avoid the distasteful patterns?
Input Format
The first line of input consists of an integer T: the number of test cases.
Each testcase start with an integer 1 ≦ N ≦ 150, followed by N lines contains at most 150 '<', '>', '', 'v', and whitespaces.
"<>" and "
| <tr style="font-size:small"> | v |
The upper-left corner of the chessboard is always a white cell.
Output Format
For each chessboard, if any solution exists, output it using the same format as input data without trailing whitespaces.
Otherwise, output "Run away little girl. Run Away!" (without quotes).
It is guaranteed that there's a unique solution.
Print a blank line after each testcase.
Sample Input 1
3
<>^^
^^vv
vv<>
3
<><>
^ ^
v v
4
<>
<><>
<><>
<>
Sample Output 1
^<>^
v<>v
<><>
^ ^
v v
^^
^vv^
v^^v
vv
Hints
Problem Source
Migrated from old NTUJ.
BEE
Subtasks
| No. | Testdata Range | Score |
|---|