DrawPlanar
SRM 280 · 2005-12-28 · by lars2520
SRM 280 · 2005-12-28 · by lars2520 · Brute Force, Graph Theory, Recursion
Problem Statement
Problem Statement
We all know that a planar graph is one that you can draw without having any edges crossing. Perhaps less well known is that a planar graph can always be drawn with vertices on lattice points and with edges as straight lines between connected vertices.
You will be given aString[] , graph, representing a planar undirected graph, where the jth character of element i of graph indicates whether vertices i and j are connected ('T' for true, 'F' for false). Your task is to find the area of the smallest rectangular box that the vertices can be placed in so that they are located on lattice points with non-overlapping straight edges between connected vertices.
You will be given a
Notes
- Lattice points are ones with integer coordinates.
Constraints
- graph will contain between 1 and 7 elements, inclusive.
- Each element of graph will contain the same number of characters as there are elements in graph.
- Each character in graph will be 'T' or 'F'.
- Character i in element i of graph will be 'F'.
- Character i in element j of graph will be equal to character j in element i.
- The graph will be planar.
Examples
0)
{"F"}
Returns: 0
With just one vertex, a single point suffices to draw the graph, so the area is 0.
1)
{"FTF",
"TFF",
"FFF"}
Returns: 0
In this case, we can draw the vertices all in a line, again with area 0.
2)
{"FTT",
"TFT",
"TTF"}
Returns: 1
Here, we can select any three corners of a 1x1 square.
3)
{"FTTT",
"TFTT",
"TTFT",
"TTTF"}
Returns: 4
4)
{"FTTTT",
"TFTTT",
"TTFTT",
"TTTFF",
"TTTFF"}
Returns: 6
Submissions are judged against all 44 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class DrawPlanar with a public method int minArea(vector<string> graph) · 44 test cases · 2 s / 256 MB per case