PEG Judge - WC15 #2 - The Force Awakens (Junior)

Woburn Challenge 2015-16 Round 2 - Junior Division

Problem VII: The Force Awakens

“Meesa gonna finish… what yousa started.”

After the destruction of the Death Star and death of Darth Sidious, victory for the rebel forces seemed apparent. However, that proved to be far from the truth, as the true puppeteer behind the Galactic Empire finally revealed himself – Sith lord Jar Jar Binks. His vengeance was swift, as he all but eradicated the rebels' resistance and the Jedi presence.

Fortunately, Han Solo was able to survive Jar Jar's wrath, and has a plan to destroy him and topple the Empire. Jar Jar has been tricked into entering an abandoned mirror factory, where he will hopefully bring about his own doom.

Viewed from above, the factory can be divided into a regular grid of cells, with N rows and M columns (1 ≤ N, M ≤ 2000). The nature of the j-th cell in the i-th row is given by the character G_i,j, with the following possibilities:

. The cell is empty.
# The cell contains a non-reflective barrier.
/ The cell contains a diagonal mirror running from the top-right to the bottom-left, which reflects any incoming laser at a 90-degree angle (for example, a laser entering from the top would leave through the left).
\ The cell contains a diagonal mirror running from the top-left to the bottom-right, which reflects any incoming laser at a 90-degree angle (for example, a laser entering from the left would leave through the bottom).
X The cell contains a set of mirrors which reflect any incoming laser back the way it came (for example, a laser entering from the top would leave back through the top).

As Jar Jar walks through the factory, Han will goad him into firing a blaster shot in some cardinal direction (directly up, down, left, or right) from some empty cell. He hopes that the laser will happen to reflect off some mirrors and end up re-entering that same cell, thus killing Jar Jar! That might sound like an unlikely plan to work… but never tell him the odds.

That being said, enquiring minds might like to know what kind of a chance it does have. An empty cell is considered to be "deadly" if, for at least one of the four cardinal directions, Jar Jar would shoot himself if he were to fire a shot from that cell in that direction. How many of the empty cells are deadly?

Note: In test cases worth 80% of the points, N ≤ 50 and M ≤ 50.

Input Format

The first line of input consists of two space-separated integers N and M.
The next N lines each consist of M characters G_{i, 1..M}, for i = 1..N.