A floor is made of square tiles described by grid, a list of equal-length strings. Each character is one tile:
/: a wall along the diagonal from the tile's bottom-left corner to its top-right corner\: a wall along the diagonal from the tile's top-left corner to its bottom-right corner.: an empty tile with no wall
Walls are infinitely thin and the outer edge of the floor is not a wall. Return the number of separate regions the walls cut the floor into.
In Python source a backslash inside a string literal is written as two characters, so "/\\" is the two-tile row /\.
Examples
Input: grid = ["./", "/."]
Output: 2
Explanation: the two walls line up into one diagonal across the whole floor.
Input: grid = ["/\\", "\\/"]
Output: 5
Explanation: the rows are /\ and \/ : a diamond in the middle plus four corner triangles.
Input: grid = ["..", ".."]
Output: 1
Constraints
1 <= len(grid) <= 100,1 <= len(grid[0]) <= 100, characters are/,\or.- Target: O(R * C * alpha(R * C)) time.
Goals
- Model each tile as four triangles so diagonals become union rules
- Glue triangles across tile borders to count regions
- Choose an indexing scheme that keeps the bookkeeping simple