This is the last and most interesting problem of the junior contest, since it's the only problem which actually forces us to think about cutting down on the time complexity of our program. We are given a grid of empty cells, mirrors, and blocked cells. We must count the number of empty cells such that if we were to shoot a laser beam into at least one direction from that cell, the beam would eventually bounce back to the same cell.

Let's first consider some simple, yet inefficient solutions. The most straightforward solution is simulation. In other words, loop through all of the ~N \times M~ cells in the grid. For each cell, try to fire a shot into each of the four cardinal directions – left, right, up, and down, one after the other. For each shot fired, we will simply follow its path through the grid until either it reaches a wall/non-reflective barrier (in which case the original cell isn't deadly) or it returns to the starting position (in which case the cell is deadly). In each state of this simulation, we will need to keep track of the following pieces of information:

• the row that the laser beam is current at,
• the column that the laser beam is current at, and
• the direction that the laser beam is currently travelling in.

The row and column can simply be stored as a pair of integers ~(r, c)~. The direction is the trickier part. Some may decide to store it as a single number/letters (i.e. arbitrarily assign directions to the numbers from ~0~ to ~3~, or perhaps the letters L, R, U and D) and check these values each time to make changes to the current position. However, a popular, more elegant method is just to keep a pair ~(dr, dc)~ – the change in the row and column, respectively, per unit of time. Left is ~(0, -1)~, right is ~(0, 1)~, up is ~(-1, 0)~, and down is ~(1, 0)~. This is much cleaner, because all we have to do is add the values of ~dr~ and ~dc~ to the current coordinates to get the new coordinates.

Every time we encounter a mirror, we must change ~dr~ and ~dc~ accordingly. As it turns out, there exists an elegant way to do so which avoids painstakingly long if-statement chains. Observe that whenever the laser hits a / or \ mirror, the axis of the laser changes – i.e. horizontal beams become vertical, and vice versa. That means, we can simply swap whichever of ~dr~ and ~dc~ is currently equal to ~0~ when encountering these mirrors. However, by simply swapping the two numbers, the sign of the non-zero directional component may be wrong. When is it wrong? A quick check in our head shows that only for the / mirror, we have to negate the non-zero value – rightward ~(0, 1)~ beams will be reflected upward ~(-1, 0)~, downward ~(1, 0)~ beams will be reflected leftward ~(0, -1)~, etc. Which of ~dr~ or ~dc~ to negate? Since negating ~0~ does nothing to it and exactly one of them is always going to be zero, we might as well skip the check and negate both. Finally, observe that the X mirror will just reverse both components, so it's the exact same case as the check for the / mirror and we can combine them into one. Altogether, the handling of changing directions can be done in two harmless-looking if-conditions:

if (g[r][c] == '/' || g[r][c] == '\\')
  swap(dr, dc);
if (g[r][c] == '/' || g[r][c] == 'X') {
  dr = -dr;
  dc = -dc;
}

Note that in many programming languages, the backslash character \ is an escape character. To represent a single backslash, we'll need to escape it using yet another backslash. Finally, we may want to simplify checking of walls and barriers. If we completely pad our 2D character array with blocks (# characters) before reading in the grid, and also read the grid into ~1~-based indices (from ~(1, 1)~ to ~(N, M)~ rather than from ~(0, 0)~ to ~(N-1, M-1)~) we've effectively created a literal "wall" of blocks around the grid for the laser beams to run into. This is not necessary, but removes the need for range checks. With these implementation details out of the way, the rest of the simulation should be very straightforward.

Why is this solution not enough? Let's study its running time. If we have to simulate a laser beam from each of the ~N \times M~ cells, then the running time should be proportional to ~4NM~ multiplied by the largest possible number of steps taken by a laser beam. With a little thinking, we should be able to come up with a test case like the one depicted below.

/\/\/\X
.......
.......
.\/\/\/

If we project the laser beam upwards from the bottom-left corner, it will travel to every other cell twice before returning to the original cell. This tells us that each simulation of a single laser also has the worst-case running time proportional to ~N \times M~, the size of the grid. Putting it together, our straight-simulation solution takes ~4N^2 M^2~ steps. In the worst case when the grid is ~2000~ by ~2000~, our algorithm will have to take ~4 \times 2000^2 \times 2000^2 = 64\,000\,000\,000\,000~ (~64~ quadrillion) steps. This is clearly going to exceed the time limit by our ~60~ million steps/second rule, but a correct implementation is given ~80\%~ of the points as guaranteed by the problem statement (~4 \times 50^2 \times 50^2 = 25~ million).

The next step that one might consider is some optimization. As it turns out, there are a few ways we can go about optimizing the straight-simulation.

One way is by noticing that in the worst-case example we provided above, there exist many empty cells we pass through. It's not hard to see that we would be able to make our program much faster by simply "skipping over" those cells. In other words, we would like to make each "reflection" have ~\mathcal O(1)~ time complexity by moving directly to the opposing mirror, rather than ~\mathcal O(\max(N, M))~ through a bunch of empty cells. This is doable with precomputation.

We can store a 3D array ~next[r][c][d]~ of coordinates. This array shall store the coordinates of the next mirror that a beam at ~(r, c)~ should hit if it was travelling in direction ~d~. To precompute ~next~ for empty cells where ~d = (0, -1)~ or ~(-1, 0)~, we can loop upwards from ~(1, 1)~ to ~(N, M)~ and take the ~next~ value of the cells left and above of it not on the left or top borders. For cells on the left or top border, ~next~ can simply point to the wall block. For non-empty cells (cells will a mirror or block), ~next~ will point to its own coordinates so that other ~next~ values to the right and top of it can propagate through. Then to get ~next~ values for ~d = (0, 1)~ or ~(1, 0)~, we do the same thing but in reverse – i.e. loop downwards from ~(N, M)~ to ~(1, 1)~. During our simulation, we simply set our current coordinates to the ~next~ coordinates after each step to "skip" to the next non-empty cell, making sure to check for blocks both before and after the skip.

While this is a good optimization, the solution is still not good enough. Consider the case below.

/......\
./....\.
../..\..
.../\...
...\./..
..\.../.
.\...../
\.../...

In a test case like this, a laser travelling leftwards from the ~4^\text{th}~ column of the bottom-most row will hit all of the mirrors before returning to the same cell. In fact, a single laser beam shot anywhere on the cycle will always encounter ~2N~ mirrors. For such a case, we've shown the time complexity to be at least ~\mathcal O(N^3)~, which requires roughly ~2000^3 = 8~ billion steps. This is still too slow. However, if implemented efficiently, it is awarded an extra ~10\%~ of points.

There are other optimizations we can do, such as noticing whenever a cycle has been reached, all cells in the cycle (going in the correct direction) must also be deadly. However, as long as we refuse to abandon the idea of projecting lasers outwards of each empty square, it all seems futile. Unless we can optimize the time of each simulation to a whole order of complexity less than ~\mathcal O(N)~ (like ~\mathcal O(1)~ or ~\mathcal O(\log N)~), this problem just seems impossible. As it turns out, we must altogether abandon the idea of simulating from all the empty squares.

So here's a crazy idea. How about we simulate from the blocked squares instead?

Turns out, it's not so crazy at all. Consider this "obvious" observation – every possible laser beam in the grid (at some coordinate of an empty cell, travelling in some direction) has exactly two possible fates:

1. It will end up back in the same coordinates, travelling in the same direction. We've already established that this means every cell in the cycle is considered deadly.
2. It will hit a wall or blocked square.

We know that any laser beam's path is "deterministic," in the sense that if we were to shoot a laser-beam from a given cell which eventually ends up hitting a wall/block in a particular direction, then shooting the beam in reverse from the coordinates of that wall/block will eventually pass through the original cell.

Much more importantly, it is guaranteed that a laser beam coming out of a wall/block will never be able to enter into an infinite cycle. In other words, the laser beam will always end up at yet another wall/block. Convince yourself that this is true by trying to come up with counterexamples (you won't be able to). This presents the following approach:

First consider each neighbouring cell of a wall/block which is not blocked (either an empty cell or a mirror). We will simulate a laser coming out of that wall/block in the direction of the non-blocked cell. For each of the simulations, we keep track of which cells in the grid we've encountered in that particular simulation only. If we notice that a cell has already been visited in the same simulation, then it must be deadly.

How? We could keep a 2D boolean array of all the cells visited in the current simulation, but resetting it each time is too slow and will still make the running time quadratic. Instead, we can number each simulation (just count upwards from ~1~) and keep an array called ~last[r][c]~, which stores the number of the last simulation where we encountered cell ~(r, c)~. If ~last~ is equal to the current simulation number, then we must have encountered it twice and the cell is deadly. Otherwise, just make sure to update ~last[r][c]~ to the current simulation number.

However, we may still not be counting the deadly cells which are infinitely involved in a cycle (and never hits a wall). Let's consider each of the ~4~ directions of each empty cell. If after the previous simulations, a wall laser beam has never travelled in that direction at that cell, then that cell must be part of a cyclic path (we've shown that there are only these 2 cases).

So, we can keep yet another boolean array ~done[r][c][d]~, storing whether a beam has previously moved through that cell, in that direction. For each cell ~(r, c)~ that is empty, if even one of the ~4~ directions has not been previously visited by a wall/block-originated laser beam, then it must be deadly.

Note that since wall/block laser beams are deterministic, it is unnecessary to follow a beam going in the same direction at a given cell more than once. Therefore, we notice that if ~done[r][c][d]~ is already true while we're following a laser beam, we might as well stop the simulation right there. We never reset ~done~ across any of the simulations, so ~done~ guarantees that every possible laser beam is examined at most once in the entire program. Magically, this ensures that our entire solution only takes at most ~4NM~ steps, yielding an ~\mathcal O(NM)~ running time.