TopCoder problem "BallBouncing" used in SRM 281 (Division I Level Two)



Problem Statement

    

A ball is moving diagonally on a rectangular board composed of unit squares in rows rows and columns columns. Each square is identified by its row and column number. The lowermost row is marked row 0 and the leftmost column is column 0.

The ball is initially located in the middle of a starting square given by two integers, startrow and startcol, and is moving diagonally up-right at an angle of 45 degrees. Whenever it reaches a wall, it bounces off it at a right angle (an angle of 90 degrees) and continues moving. If the ball runs into a corner, it bounces back in the opposite direction from which it came..

A number of holes have been drilled in the board and the ball will fall in upon reaching a square with a hole. Given the board size, starting location and locations of holes, return the number of times the ball will bounce off a wall before falling into a hole, or -1 if the ball will continue bouncing indefinitely.

 

Definition

    
Class:BallBouncing
Method:bounces
Parameters:int, int, int, int, String[]
Returns:int
Method signature:int bounces(int rows, int columns, int startrow, int startcol, String[] holes)
(be sure your method is public)
    
 

Notes

-Bouncing back from a corner counts as only one bounce.
 

Constraints

-rows and columns will be between 1 and 1000000, inclusive.
-startrow will be between 0 and rows-1, inclusive.
-startcol will be between 0 and columns-1, inclusive.
-holes will contain between 0 and 50 elements, inclusive.
-Each element of holes will be formatted as "row column" (quotes for clarity), where row and column will be integers with no leading zeros representing a square inside the board.
-There will be no holes at the starting position of the ball.
-No two holes will occupy the same position on the board.
 

Examples

0)
    
8
11
2
1
{ "1 5", "5 3", "4 4" }
Returns: 3
This example corresponds to the image in the problem statement.
1)
    
6
5
5
3
{ "1 3" }
Returns: 7
Bouncing back from a corner counts as only one bounce.
2)
    
6
7
4
4
{ }
Returns: -1
With no holes, the ball is bound to bounce around for quite a while.
3)
    
3
3
1
1
{ "2 2" }
Returns: 0
4)
    
6
6
0
5
{ "4 1", "3 2", "4 3", "2 1", "3 0", "5 2" }
Returns: -1
5)
    
1000000
999999
66246
84332
{ "854350 4982" }
Returns: 1662562
6)
    
5
7
3
4
{ "0 6", "2 3" }
Returns: 5
7)
    
1
5
0
1
{ "0 3" }
Returns: 2

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=5919

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8078&pm=5919

Writer:

lovro

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Simulation