Statistics

Problem Statement for "DrawPlanar"

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 a String[], 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.

Definition

Class:
DrawPlanar
Method:
minArea
Parameters:
String[]
Returns:
int
Method signature:
int minArea(String[] graph)
(be sure your method is public)

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

  1. {"F"}

    Returns: 0

    With just one vertex, a single point suffices to draw the graph, so the area is 0.

  2. {"FTF", "TFF", "FFF"}

    Returns: 0

    In this case, we can draw the vertices all in a line, again with area 0.

  3. {"FTT", "TFT", "TTF"}

    Returns: 1

    Here, we can select any three corners of a 1x1 square.

  4. {"FTTT", "TFTT", "TTFT", "TTTF"}

    Returns: 4

  5. {"FTTTT", "TFTTT", "TTFTT", "TTTFF", "TTTFF"}

    Returns: 6

  6. {"FTTTTT", "TFTTTT", "TTFFTT", "TTFFFF", "TTTFFF", "TTTFFF"}

    Returns: 6

  7. {"FFFFFF", "FFFFFF", "FFFFFF", "FFFFFF", "FFFFFF", "FFFFFF"}

    Returns: 0

  8. {"FTTTTT", "TFTTTT", "TTFFTT", "TTFFTF", "TTTTFF", "TTTFFF"}

    Returns: 8

  9. {"FTTTTTT", "TFTTTTF", "TTFFTTF", "TTFFTFT", "TTTTFFT", "TTTFFFF", "TFFTTFF"}

    Returns: 12

  10. { "FTTTF", "TFTTT", "TTFTT", "TTTFT", "FTTTF" }

    Returns: 6

  11. { "FTTFF", "TFTTT", "TTFTT", "FTTFT", "FTTTF" }

    Returns: 4

  12. {"FTTTTTT","TFTTTTT","TTFTTFF","TTTFFTF","TTTFFFT","TTFTFFF","TTFFTFF"}

    Returns: 10

  13. {"FTTTTTT", "TFTTTFT", "TTFFFFT", "TTFFTFF", "TTFTFTT", "TFFFTFT", "TTTFTTF"}

    Returns: 15

  14. {"FTTTTTT", "TFTTTFT", "TTFTFFF", "TTTFFTT", "TTFFFFT", "TFFTFFT", "TTFTTTF"}

    Returns: 15

  15. {"FTTTTTF","TFTTFTT","TTFTTFT","TTTFFFF","TFTFFTT","TTFFTFT","FTTFTTF"}

    Returns: 12

  16. {"FTTTTTF", "TFTTFFT", "TTFFTFT", "TTFFFTF", "TFTFFTF", "TFFTTFT", "FTTFFTF"}

    Returns: 9

  17. {"FTTTTTF","TFTTFFT","TTFFTFT","TTFFFTF","TFTFFTT","TFFTTFT","FTTFTTF"}

    Returns: 9

  18. {"FTTTTTF", "TFTTFFT", "TTFFTFT", "TTFFFTT","TFTFFTF","TFFTTFT","FTTTFTF"}

    Returns: 9

  19. {"FTTTTFF","TFTTFTF","TTFFTTF","TTFFFFT","TFTFFFT","FTTFFFT","FFFTTTF"}

    Returns: 9

  20. {"FTTTTFF","TFTFTTF","TTFTFTF","TFTFFFT","TTFFFFT","FTTFFFT","FFFTTTF"}

    Returns: 9

  21. {"FTTTTTF","TFTFTFT","TTFFFTT","TFFFTTT","TTFTFFT","TFTTFFT","FTTTTTF"}

    Returns: 12

  22. {"FTTTTTT","TFTFFTF","TTFFFFT","TFFFTFT","TFFTFTF","TTFFTFF","TFTTFFF"}

    Returns: 4

  23. { "FFFFFFF", "FFTTFFF", "FTFTFFF", "FTTFFFF", "FFFFFTT", "FFFFTFT", "FFFFTTF" }

    Returns: 3

  24. { "FTTFFTT", "TFTTFFF", "TTFTFFF", "FTTFFFF", "FFFFFTT", "TFFFTFT", "TFFFTTF" }

    Returns: 3

  25. { "FFFFFFF", "FFFFFFF", "FFFFFFF", "FFFFFFF", "FFFFFFF", "FFFFFFF", "FFFFFFF" }

    Returns: 0

  26. {"FTFFFFF", "TFTFFFF", "FTFTFFF", "FFTFTFF", "FFFTFTF", "FFFFTFT", "FFFFFTF"}

    Returns: 0

  27. {"FTFFFFF", "TFFFFFF", "FFFFFFF", "FFFFFFF", "FFFFFFF", "FFFFFFF", "FFFFFFF"}

    Returns: 0

  28. {"FTTTT", "TFTFF", "TTFFF", "TFFFF", "TFFFF"}

    Returns: 2

  29. {"FTF", "TFT", "FTF"}

    Returns: 0

  30. {"FTTTT", "TFTTT", "TTFTT", "TTTFF", "TTTFF"}

    Returns: 6

  31. {"FTTFTT", "TFTTFT", "TTFTTF", "FTTFFF", "TFTFFF", "TTFFFF"}

    Returns: 4

  32. {"FTTFTT", "TFFTFT", "TFFTTF", "FTTFFF", "TFTFFF", "TTFFFF"}

    Returns: 2

  33. {"FTTTTF", "TFTTFF", "TTFFFF", "TTFFFF", "TFFFFF", "FFFFFF"}

    Returns: 2

  34. {"FTTTTT", "TFTFFF", "TTFFFF", "TFFFFF", "TFFFFF", "TFFFFF"}

    Returns: 2

  35. {"FTTTTTT", "TFTTTFT", "TTFFFFT", "TTFFTFF", "TTFTFTT", "TFFFTFT", "TTTFTTF" }

    Returns: 15

  36. {"FTFFFTT", "TFTTFTT", "FTFTTFT", "FTTFTTF", "FFTTFTT", "TTFTTFT", "TTTFTTF" }

    Returns: 12

  37. {"FTTFFFF", "TFTFFFF", "TTFFFFF", "FFFFTTF", "FFFTFTF", "FFFTTFF", "FFFFFFF" }

    Returns: 3

  38. {"FTFFTFT", "TFTTTFF", "FTFTFTF", "FTTFTTT", "TTFTFFT", "FFTTFFT", "TFFTTTF" }

    Returns: 6

  39. {"FTTT", "TFTT", "TTFT", "TTTF" }

    Returns: 4

  40. {"FTTTTTT", "TFTTTFT", "TTFFFFT", "TTFFTFF", "TTFTFTT", "TFFFTFT", "TTTFTTF" }

    Returns: 15

  41. {"FTFFFTT", "TFTTFTT", "FTFTTFT", "FTTFTTF", "FFTTFTT", "TTFTTFT", "TTTFTTF" }

    Returns: 12

  42. {"FTTFFFF", "TFTFFFF", "TTFFFFF", "FFFFTTF", "FFFTFTF", "FFFTTFF", "FFFFFFF" }

    Returns: 3

  43. {"FTFFTFT", "TFTTTFF", "FTFTFTF", "FTTFTTT", "TTFTFFT", "FFTTFFT", "TFFTTTF" }

    Returns: 6

  44. {"FTTT", "TFTT", "TTFT", "TTTF" }

    Returns: 4

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: