Problem Statement
You are being chased in a maze. Can you escape the maze before you are caught? At each time step, you must first move one square in one of the four cardinal directions. Your opponent then moves up to speed times (he may optionally move less times if he so chooses). If you move off the playing field, you win. If your opponent moves to the same square as you, you lose. Assuming that your opponent moves optimally (trying to catch you, and if he can't, to delay you as much as possible), how quickly can you escape? Return the number of moves you must make, or -1 if escape is impossible.
You will be given the maze as a String[], each element of which represents a row in the maze. You are denoted by 'A', while your opponent is 'B', and 'X' denotes an impassible region.
You will be given the maze as a String[], each element of which represents a row in the maze. You are denoted by 'A', while your opponent is 'B', and 'X' denotes an impassible region.
Definition
- Class:
- Chaser
- Method:
- chase
- Parameters:
- String[], int
- Returns:
- int
- Method signature:
- int chase(String[] maze, int speed)
- (be sure your method is public)
Notes
- Both you and your opponent are aware of the other's position at all times.
Constraints
- maze will be rectangular.
- maze will have at least 1 row and 1 column and at most 16 rows and at most 16 columns.
- speed will be between 1 and 100, inclusive.
- maze will contain exactly one 'A' and 'B' and all other characters will be 'X' or '.'.
Examples
{ "XXXXX", "X...X", "XAXB.", "X...X", "XXXXX" }1
Returns: -1
A draw.{"XXXXXXXXXX", "....A....B", "XXXXXXXXXX"}2
Returns: 5
You can escape in the nick of time.{"XXXXXXXXXXXXXX.X", "X..............X", "X.XXXXXXXXXXXXXX", "X..............X", "XXXXXXXXXXXXXX.X", "X..............X", "X.XXXXXXXXXXXXXX", "X..............X", "XXXXXXXXXXXXXX.X", "X..............X", "X.XXXXXXXXXXXXXX", "X..............X", "XXXXXXXXXXXXXX.X", "X..............X", "XAXXXXXXXXXXXX.X", "XB.............X"}1
Returns: 106
Back to all problems