CCO '99 P1 - You Can't Get There From Here

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 64M

Problem type
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 (0,0) and the northeast corner has coordinates (r,c) where 0 < r \le 10 and 0 < c \le 10. The southeast corner has coordinates (0,c) and the northwest corner has coordinates (r,0). 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 A and B lying on the grid, and an initial direction, you are to determine if the spot moves from A to B and, if so, how far the spot moves (in terms of number of grid positions) before reaching B the first time.

Input Specification

The input consists of an integer n, followed by n data sets. Each data set begins with a line containing r and c, followed by two lines containing the coordinates of points A and B 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 B can be reached, and, if it can, how far the spot moves before reaching B.

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

There are no comments at the moment.