Problem Statement
Elly is playing a new game. On a rectangular board with N rows and M columns are located several spaceships. Each spaceship can move in a single (pre-defined) direction with a speed of one cell per second. It moves until either going beyond the limits of the board (in which case the game ends), or reaches another ship, in which case it crashes into it and disappears. After the crash the other ship starts moving (in its own direction).
The initial board is given to you in the String[] board. Each symbol in board is one of {'.', '<', '>', '^', 'v'}. A '.' denotes an empty cell, and each of the others - a spaceship. The spaceships move in the direction their symbol points to.
Initially none of the spaceships are moving. All the player does is make a single selection - for the first ship to start moving. Depending on which ship is selected, the game can continue various time. Now Elly wonders what is the maximal number of seconds the game can last, if choosing the optimal ship. Please help the girl by finding this amount of time.
The initial board is given to you in the String[] board. Each symbol in board is one of {'.', '<', '>', '^', 'v'}. A '.' denotes an empty cell, and each of the others - a spaceship. The spaceships move in the direction their symbol points to.
Initially none of the spaceships are moving. All the player does is make a single selection - for the first ship to start moving. Depending on which ship is selected, the game can continue various time. Now Elly wonders what is the maximal number of seconds the game can last, if choosing the optimal ship. Please help the girl by finding this amount of time.
Definition
- Class:
- EllysGame
- Method:
- getMax
- Parameters:
- String[]
- Returns:
- int
- Method signature:
- int getMax(String[] board)
- (be sure your method is public)
Notes
- Due to the way the game is played it is guaranteed it will finish in a finite numeber of seconds.
Constraints
- board will contain between 1 and 50 elements, inclusive.
- Each element of board will contain between 1 and 50 characters, inclusive.
- All elements of board will contain the same number of elements.
- Each character in board will be from the alphabet {'.', '<', '^', '>', 'v'}.
- There will be at least one character, different than '.' in board.
Examples
{"vv.^>>", ".^.<>.", ">>.^>v", ".^v>..", "^^...<"}Returns: 21
Pressing the ship in the upper left corner would lead to game lasting for 16 seconds: The first ship will fly downwards for two seconds until crashing into the one at (2, 0). The second ship will fly to the right for one second, until crashing into the one at (2, 1). The third one will fly to the right for two seconds, until crashing into the one at (2, 3). The fourth one will fly upwards for one second, until crashing into the one at (1, 3). The fifth one will fly to the left for two seconds, until crashing into the one at (1, 1). The sixth one will fly upwards for one second, until crashing into the one at (0, 1). The seventh one will fly downwards for three seconds, until crashing into the one at (3, 1). Please note that the ships at (1, 1) and (2, 1) have already moved (and crashed), thus the fields are now empty. The eight one will fly upwards for four seconds, until leaving the board. At that point the game ends. However, it is better to click the ship at (2, 3), which would lead to a game of length 21 seconds.{">>>><<<<"}Returns: 36
Sometimes you can get long games even on a small board.{".^.", "<.>", ".v."}Returns: 1
Sometimes you can't.{"...v<.^.v<...<>", ".>..^...^v<...v", "<^v..^v^.^v.>.^", "..<.^^>.v<><..v", ".v.>.<^..vv^<<.", "..^^.>^>.^<<>>.", ".<v<v^v.^<^v>..", ".>v>.v^<..<v..^", "^>.<.v.v.v^<..>", "^>..>vv>><v.v..", "..>v^...<^....>", ">..^>.^<.^<^.v.", "..<..^^..vv.^.>", "v><v^..><...>.^", "..>^>^..v...<v.", "^...^.<v..v<^..", ">.<v^.^v^^>>.v.", "v.^..^.<.<>.<<.", ".^.v><..<<...^.", "<.vv.v<>^.>.^..", "<><...>^...^.>v"}Returns: 177
Back to all problems