Interesting Maze Game
Time limit1sMemory limit128 MB
Given a 7x7 labyrinth and one extra card, decide whether inserting and rotating that card lets the piece walk to the target in a single move.
- Level
Medium6 of 10
- Topics
- Simulation, Implementation, BFS, Matrix
- Solved
- No attempts yet
Problem
The Police President recently bought a new game -- the famous Ravensburger's aMAZEing Labyrinth. He is so keen on it that he spends any free time playing it. Because we need the Police President to make far more important decisions during the Summit, we need a program that can play the game in his place.
The game is played on a field of 7 x 7 squares, with an equally sized card lying on each square. Various path patterns are drawn on the cards; these paths join an arbitrary subset of the four edges of a single square. When the patterns line up, they can form longer paths running across the whole field. You may move from a square to a neighbouring square only if both squares contain a path leading to their common edge. Diagonal moves are not allowed. See the picture for an idea of how the game looks.

At the start of a move, the player's piece sits on one of the cards, and the goal is to move the piece along valid paths to some other (target) card. Before walking, the player changes the state of the maze by inserting one extra card into it.
The extra card may only be inserted at a position on the field margin. The insertion shifts the whole affected row or column of cards one position further, which makes another card fall out at the opposite end of the field. (That card becomes the new extra card for the next move, but this problem deals with a single move only.)
Because the cards whose row and column are both odd are stuck firmly to the desk, only even rows and columns can be shifted. Thus the extra card can be inserted into an even row or an even column only. Numbering the rows and columns from 1 to 7, there are 12 positions where the new card can be inserted: (1,2), (1,4), (1,6), (7,2), (7,4), (7,6), (2,1), (4,1), (6,1), (2,7), (4,7), and (6,7). For instance, insertion at position (7,6) causes the following shift:
(7,6) → (6,6) → (5,6) → (4,6) → (3,6) → (2,6) → (1,6)
The extra card ends up at position (7,6), and the card formerly at (1,6) is removed from the field for the rest of the move.
Before insertion, the extra card may be rotated to any of the four directions. No other card can be rotated. This gives a maximum of 48 possible moves (if the extra card is asymmetric).
Another important rule concerns the case where the target card or the card with the player's piece lies in the row or column being shifted. In that case the position of the piece or the target is shifted as well, which makes it possible to move the target to a more convenient place.
If the target is shifted off the field (the target card falls out), it can no longer be reached in this move -- the piece cannot leave the field. On the other hand, if the piece's card is shifted off the field, the piece's position wraps around to the opposite end, that is, onto the card that was just inserted.
A valid move therefore consists of two parts: inserting the extra card into the game (this action must always be performed) and then walking a path of arbitrary length (including zero, i.e. staying on the same square). Your task is to decide whether the target can be reached in a single move -- in other words, whether the extra card can be inserted so that the piece can then walk to the target position.
Input
The input consists of several game descriptions. The first line of each description contains four integers R1, C1, R2, and C2 separated by spaces, with . (R1, C1) is the position (row and column) of the piece and (R2, C2) is the position of the target. As explained above, these positions may be shifted during the move. The four numbers are followed by one blank line.
The next three lines describe the first row of the field. Each of these lines contains 27 characters: three for the card in the first column, one space, three characters for the card in the second column, and so on. Every card is thus represented by a 3 x 3 square of nine characters. The middle character is always the capital letter 'O'. The four corner characters are always dots ('.'). The left and right characters are either a dot ('.') or a dash ('-'); a dash means a path leading to the left or right edge. The top and bottom characters are either a dot or a pipe ('|'); a pipe means a path leading to the top or bottom edge.
After the first row there is one blank line and three more lines describing the second row, then another blank line and three lines for the third row, and so on. After the seventh row there is a blank line and three more lines containing exactly three characters each. This is the description of the extra card, given in the same way as the cards on the field.
The input is terminated by a line containing four zeros instead of the piece and target coordinates.
Output
For each game, output a single line. If the extra card can be inserted so that a path exists from the piece to the target, print "You can win in one move." Otherwise print "Bad luck!".