Beam hits a mirror

The Samsung S/W Company plans to develop a game using mirrors on
a nxn 2-dimensional grid. Each mirror is a two-way mirror and ha
s only two directions as follows.


In the game, when a laser beam starts at (0, 0) in right directi
on, they need to count the number of times the beam hits a mirro
r until it hits a wall (boundary) of the grid.

[Example] In the following configuration, the beam hits mirrors
7 times until it hits the upper wall.

For this company, write a program to count the number of times t
he beam hits a mirror until it hits a wall (boundary) of the gri
d.

[Constraints]
1. The size n of a 2-dimensional grid is not more than 100. (5 ≤
 n ≤ 100)
2. No mirror in (0, 0)

[Input]
The test cases consist of the following format. In the first lin
e, the number of test cases is given. From the next line, each t
est case is provided in n+1 lines. In the first line of each tes
t case, n is given. In the next n lines, a nxn 2-dimensional arr
ay is given row-by-row, one row per line. If an element of the a
rray is ‘0’, it indicates an empty cell. When it is ‘1’, there i
s a mirror with [Direction 1] and if it is ‘2’, there is a mirro
r with [Direction 2] in the corresponding cell.

[Output]
Print out the number of mirrors hit by the laser beam that start
s at (0, 0), for each test case on a separate line, starting wit
h ‘#x’, where x is the case number. Place a blank between two ad
jacent numbers for printing.

[Sample Input]

4                     // Total number of test cases

10                    // n = 10,Test Case #1

0 0 0 0 0 0 0 2 0 0   // 0 : empty cell, 1 : [Direction 1], 2 : [Direction 2]

0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 2 0 0 0 1

0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 0 0 1 0 0

1 0 0 0 2 0 0 2 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 2 0 0 0 0 1 0 0

0 0 0 0 0 0 0 0 0 0

5                     // Test Case #2

0 2 0 0 0

0 0 0 0 0

0 2 0 1 0

2 0 0 1 0

0 2 0 0 0

10                    // Test Case #3

0 0 0 0 0 0 2 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 2 0 0 0 0 0 0

0 0 2 1 0 0 0 2 0 0

0 0 0 0 0 1 0 1 0 0

0 0 0 0 2 0 0 0 1 0

0 2 0 0 0 0 1 0 0 1

0 0 0 0 0 0 2 0 0 0

0 0 0 0 1 0 0 0 0 0

0 0 2 0 0 0 0 0 0 1

10                    // Test Case #4

0 0 0 0 0 0 2 0 0 0

0 0 0 0 0 0 0 2 0 1

0 0 0 0 0 0 0 0 0 0

0 1 1 0 0 0 0 0 0 0

0 0 0 0 0 2 2 0 0 1

0 0 0 0 0 0 0 2 0 1

0 0 0 2 1 0 2 0 2 0

0 0 0 0 0 1 0 0 0 0

0 0 0 0 0 0 0 0 0 1

0 1 0 0 0 0 0 0 0 0

[Sample Output]

#1 7

#2 3

#3 3

#4 4

 

真情流露已经不复存在