Canadian Computing Competition: 1999 Stage 2, Day 1, Problem 1
In a primitive video game, a spot bounces around within a rectangular grid. The southwest corner of the grid has coordinates and the northeast corner has coordinates
where
and
. The southeast corner has coordinates
and the northwest corner has coordinates
. The spot always travels on the diagonal; that is, in one of the directions
NE
, NW
, SE
, SW
. The outer edges of the grid serve as mirrors: after visiting a position on the edge of the grid the spot "bounces" off according to the normal rules of reflection (Snell's Law). For example, if the spot were travelling NE
and hit the east edge of the grid, it would change direction to NW
. If the spot were to hit the corner of the grid it would change to the opposite direction.
Given a grid size, two points and
lying on the grid, and an initial direction, you are to determine if the spot moves from
to
and, if so, how far the spot moves (in terms of number of grid positions) before reaching
the first time.
Input Specification
The input consists of an integer , followed by
data sets. Each data set begins with a line containing
and
, followed by two lines containing the coordinates of points
and
respectively, followed by one line containing
NE
, NW
, SE
, or SW
- the initial direction of travel.
Output Specification
For each case, print a sentence as shown below indicating whether or not can be reached, and, if it can, how far the spot moves before reaching
.
Sample Input
2
3 4
0 0
0 4
NE
4 2
3 1
3 2
NW
Sample Output
B can be reached from A after 12 move(s).
B cannot be reached from A.
Comments