Count all triangles formed by drawn horizontal and diagonal edges in an ASCII picture of a triangular grid up to 3000 by 6000 vertices.
Medium7GeometryBrute forceDynamic programmingNo attempts yetTime limit6sMemory limit1024 MBYou packed plenty of puzzle books for the trip to Beijing, and many of them ask questions like this one: how many triangles can you find in Figure 1?

Figure 1: the picture drawn by the second example input.
After a few of them you get bored and start working out how to solve the puzzle with a program instead. Today that program is exactly what you need.
The first line contains two integers r and c (1≤r≤3000, 1≤c≤6000), the size of the picture, where r is the number of rows of vertices and c is the number of columns of vertices.
The next 2r−1 lines hold the picture, each with at most 2c−1 characters. Odd lines contain grid vertices, written as the lowercase letter x, together with zero or more horizontal edges. Even lines contain zero or more diagonal edges. Picture lines numbered 4k+1 have vertices in positions 1, 5, 9, 13, and so on, while lines numbered 4k+3 have vertices in positions 3, 7, 11, 15, and so on. A vertex can therefore sit only in one of the c positions 1, 3, 5, ..., 2c−1. Every possible vertex appears in the input.
A horizontal edge between two neighboring vertices is drawn as three hyphens ---. A diagonal edge is drawn as a single forward slash / or a single backslash \. An edge character sits exactly between the two vertices it joins. Every other position holds a space. Trailing whitespace on a line may be omitted.
Print the number of triangles of any size formed by the drawn edges. All three sides of a triangle must lie on drawn edges, and one side is a run of consecutive edges in the same direction.