Problems

3. BouncingBall

The Bouncing Ball

A ball got itself stuck in a 2-dimensional space. The two dimensional space consists of a N*M rectangular grid of squares. Some squares contain bricks while others are empty. So, the ball will bounce off those bricks. The outer boundary of the two dimensional space is always made up of bricks. You are given the description of the 2-dimensional space, the initial position of the ball, the initial direction of motion of the ball and a final destination. Determine whether the ball will ever reach the destination.

How things bounce:

These sets of three pictures each represent what exactly happens when a ball encounters a particular configuration and how exactly it bounces. In each of these cases, the ball is moving towards the north-east. The grid behaves the same way in every direction. The ball is the red cell and the blocks are the black cells.

Input Format:

  • Line 1 : A single integer T, the number of testcases.
  • This is followed by T test cases.
    • First line of each test case consists of two integers N and M.
    • This is followed by N lines of input with M integers each.
    • The jth integer on the (i+1)th line of a particular testcase is 1 if the square (i,j) contains a brick, otherwise it is 0.
    • The next line contains two integers, the initial co-ordinates of the ball.
    • The next line contains an integer, giving the initial direction of motion of the ball (explained below).
    • The next line contains two integers, which are the final destination of the ball.

Explanation of the co-ordinate system:

Co-ordinates are measured with top-left corner of the grid(as specified in input) as origin. The jth cell in the ith row of the grid has co-ordinates (i,j).

In the specification of initial direction of motion of the ball, directions are denoted by integers as follows:

  • 1 - North-East;
  • 2 - South-East;
  • 3 - South-West;
  • 4 - North-West.

Output Format:

Output consists of T lines.
One line for each test case containing "YES" if the ball can reach the destination or "NO" otherwise(without the quotes).

Constraints:

1 <= T <= 5
3 <= N,M <= 100

Points:

350

Scoring:

Absolute Score = 1000000 / ( 5*S + 2*C + 10*K + 3*O + 20*I + 20*Q + 100*W )
where,
S = Number of semicolons ;
C = Number of non-whitespace characters
K = Number of keywords
O = Number of commas ,
I = Number of occourances of string "if" (without quotes)
Q = Number of question marks ?
W = Number of occourances of string "switch" (without quotes)

Allowed Header Files:

stdio.h

Sample Input:

2 5 5 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 1 1 1 1 3 2 1 4 3 5 5 1 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 1 1 1 1 3 2 1 4 2

Sample Output:

YES NO

Time Limit: 1 second

Memory Limit: 64 MB