1999 Canadian Computing Competition, Stage 2

Day 1, Problem 1: You Can't get There from Here

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 ≤ 10,000 and 0 < c ≤ 10,000. 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. 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.

Grading

50% of the test data will have r, c ≤ 10.

Input

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

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.

All Submissions
Best Solutions

Point Value: 20
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 19, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...