776. Slash Regions
A courtyard is paved with square tiles laid out in rows. grid[r] describes row r, and its character at position c is one of three kinds. A space means a clear tile. A / means a metal strip runs from the tile's bottom-left corner to its top-right corner. A backslash \ means a strip runs from the top-left corner to the bottom-right corner.
Water cannot cross a strip and cannot leave the courtyard, but it flows freely between the parts of a tile that no strip separates and across the edge between two neighbouring tiles. Return the number of separate regions the water is divided into. All rows have the same length.
Example 1
- Input:
- grid = ["//","//"]
- Output:
- 4
- Explanation:
Three parallel diagonal strips cut the square into four regions: two corner triangles and two bands.
Example 2
- Input:
- grid = ["\\ "," /"]
- Output:
- 2
- Explanation:
The blank cells let water go around the backslash, so only the small triangle below the slash in the last cell is split off: 2 regions.
Example 3
- Input:
- grid = [" "," /\\ "," \\/ "," "]
- Output:
- 2
- Explanation:
The small diamond in the middle is enclosed by four strips, and everything around it is one connected outer region: 2 regions.
Constraints
- 1 ≤ grid.length ≤ 300
- All rows have the same length, between 1 and 300
- Each character is a space,
/or a backslash
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,000 msC++ 250 msJava 500 msJavaScript 500 msTypeScript 500 ms
Expected complexity
- Time
- O(R * C * alpha(R * C))
- Space
- O(R * C)