Statistics

Problem Statement for "Permatch"

Problem Statement

We have a rectangular chessboard. Some rooks are already placed onto the chessboard. A pair of rooks is called friendly if the rooks share the same row or column. (Note that there can be other rooks between them in the same row/column.)

A chessboard is called pretty if it is possible to divide all rooks on the chessboard into disjoint friendly pairs. A chessboard is called uniquely pretty if it is pretty and there is exactly one way to form those disjoint friendly pairs.

You are given a String[] board that describes the current state of the chessboard: '#' is a cell with a rook, '.' is an empty cell. You may add new rooks onto this chessboard. (Each cell may only contain one rook.) What is the smallest number of rooks you need to add in order to make the given chessboard uniquely pretty? Return that number, or -1 if making the given chessboard uniquely pretty isn't possible.

Definition

Class:
Permatch
Method:
complete
Parameters:
String[]
Returns:
int
Method signature:
int complete(String[] board)
(be sure your method is public)

Constraints

  • n and m will be between 1 and 10, inclusive.
  • board will contain exactly n elements.
  • Each elements in board will contain exactly m characters.
  • Each character in board will be either '#' or '.'.

Examples

  1. {"##"}

    Returns: 0

  2. {"#."}

    Returns: 1

  3. {"###", ".#."}

    Returns: 0

  4. {"###", "..."}

    Returns: 1

    We can add one rook onto any of the empty cells. The resulting chessboard will always be uniquely pretty. (The new rook has to form a pair with the one above it, and then the remaining two rooks have to form the other pair.)

  5. {"#..##", "###.."}

    Returns: 0

  6. {".#..##", "####..", "#....."}

    Returns: 0

    Here is the only way of dividing these rooks into friendly pairs: . C . . AA DCBB . . D . . . . .

  7. {".#..##", "#.##..", "......"}

    Returns: 2

    One optimal solution is to create the uniquely pretty chessboard shown in the previous example.

  8. {"##", "##"}

    Returns: -1

    This chessboard is pretty, but it is not uniquely pretty: there are two ways to partition the rooks. As there are no empty cells, there is no way to add any more rooks.

  9. {"##########", "..........", "..........", "..........", "..........", "..........", "..........", "..........", "..........", ".........."}

    Returns: 8

  10. {"#........","........#",".........","..#......",".....#...",".........",".#.......",".......#.",".........","...#....."}

    Returns: 7

  11. {".........","...#.....","..#......",".#..#.#..",".....#...","........#",".........",".......#.","#........"}

    Returns: 7

  12. {"......#...",".....#....","..........","#.....#...","........##","...#......",".......#..",".........#","....#.....",".#........"}

    Returns: 7

  13. {"..........",".......#..","..#.......",".#........","....#.....",".......#..",".......#..","#.........",".......#..",".........#"}

    Returns: 7

  14. {".#......","..#.....","......#.","........","#.......","...#....","....#...",".....#..","........","........"}

    Returns: 7

  15. {".........",".......#.","....#....",".....#...","......#..","........#",".........","...#.....","#........",".##......"}

    Returns: 7

  16. {"..........",".......#..",".#.....#..","..#.......","...#...#..","#.........","........#.",".........#","......#...",".....#...."}

    Returns: 7

  17. {"....#.....",".#.......#","#.........","..#.......","..........","........#.",".....#....",".#.....#..","......#...","...#......"}

    Returns: 7

  18. {".......#","......#.","..#.....","....#...",".#......","........","...#....",".....#..","........"}

    Returns: 7

  19. {"..#.....","......#.","...#....",".....#..","....#...",".......#","#.......","........"}

    Returns: 7

  20. {"..#.......","........#.","......#...",".......#..",".........#",".#....#...","#.........","...#......"}

    Returns: 7

  21. {"#......","......#","....#..","....#..","....#..","....#..",".#.....",".......","...#...","....#.."}

    Returns: 7

  22. {"....#....",".....#..#",".........",".....#...",".......#.","#........","...#.....","......#..",".#......."}

    Returns: 7

  23. {"....#.....","........#.","...#......","..........",".......#..","..........",".....#....","#.........","......#...",".........."}

    Returns: 7

  24. {"..........","#.........","...#......",".......#..",".........#","......#...","....#.....",".#........",".........."}

    Returns: 7

  25. {"........#",".#.......","......#..","#........","...#.....","....#.#..",".......#.",".........",".........","..#......"}

    Returns: 7

  26. {"........#",".#.......","...#.....","#........",".........",".....#...","..#......",".........",".........",".......#."}

    Returns: 7

  27. {".#.....",".....#.","#......","......#","....#..",".......",".......","..#....","...#..."}

    Returns: 7

  28. {"..#.......","#.........",".......#..","..........","..........","....#.....","...#.#....",".........#",".#........","...#......"}

    Returns: 7

  29. {"...#......",".........#",".......#..","...#....#.",".....#....","..........","#.........","..#.......","..........","......#..."}

    Returns: 7

  30. {"....#....","..#......",".#.......","........#",".......#.",".........","...#.....","......#..","........."}

    Returns: 7

  31. {"....#.....",".#........","......#...",".........#",".....#....","#.......#.",".......#..","..#......."}

    Returns: 7

  32. {"#........",".....#...","..#......","....#....",".........",".#.......","......#..",".........","...#....."}

    Returns: 7

  33. {".....##.","..#.....",".......#",".......#","...#.#..","....#...","..#.....","....#..."}

    Returns: 0

  34. {"....##..","....#...","##.....#","..#..#..",".......#","#.....#.","......#.",".....#.#"}

    Returns: 0

  35. {".#..##..","........","..#.....","..##.#..","#...#...","#.......","........","........"}

    Returns: 0

  36. {"......##",".#...#..",".#....#.",".......#","........","......#.","#......#",".#.#...."}

    Returns: 0

  37. {".#........",".###....#.","#.........","........#.","..........","....#....#","#.#.......","...##.....","#........."}

    Returns: 0

  38. {"......#.",".#......","....#...","....#..#","#.......","........","##.....#","..#.#.#."}

    Returns: 0

  39. {"#..##...","........","##......",".......#","......#.","..#..#..","#.#...##","....#..."}

    Returns: 0

  40. {"#..#.###",".#......",".....#..","##......","......#.","...#....",".#......","....#.#."}

    Returns: 0

  41. {".......#","........","##......","........",".#..#...","#.#....#",".......#","....#..."}

    Returns: 0

  42. {"#.##.....",".#..#....","...#..#..","#.......#",".........","....##.#.",".#.......","........#","..#.#...."}

    Returns: 0

  43. {".....###","..#.....",".....#..",".#.....#",".#..#...","#..#....","......#.","..#..#.."}

    Returns: 0

  44. {"..#....#.",".........",".#..#..#.",".#.#.#...","..#......",".#.......","....#...#","......#.#"}

    Returns: 0

  45. {".....#..","....##.#","..#...#.","###.#...","....#...","........","......#.","........"}

    Returns: 0

  46. {"..#.....","......#.",".....##.","###..#..","..#.#...","#.......","...#.#.#","....#...",".#......"}

    Returns: 0

  47. {"......##","#.....#.",".......#",".....#..","..#.##..",".#.#..#.",".#......",".......#"}

    Returns: 0

  48. {"..........",".....#..#.","....#...#.","..#...#...","#.#..#....",".#.....##.","....#....#",".........#",".......#.."}

    Returns: 0

  49. {"..#......","...#.....","#......#.","#..#.....","#....#...","..#.....#",".#.#....#","#........"}

    Returns: 0

  50. {"##......","#....#..","....##..","..#.....",".#......","........","..##....","........",".#.#...."}

    Returns: 0

  51. {"....##....",".#......##","#..#...#..","...##.....",".#....#...","#.........","..........","........#."}

    Returns: 0

  52. {"...#......",".........#","..........",".........#","..#....#..","....#.....",".......##.","...##..#..",".#.#.....#"}

    Returns: 0

  53. {".....#.#.#","#...#.....","...#......","#.#...#...","#.........","......#..#","#..#....#.",".......#.."}

    Returns: 0

  54. {"#...#.....","#........#","...###....",".....#....",".#.#......",".....##...","....#...#.","#.#......."}

    Returns: 0

  55. {"##....#..",".......#.",".#......#","..#..#...","..#......",".....#.#.",".#..#..#.",".....#...","........#"}

    Returns: 0

  56. {"#.......",".....#..","....##..","#..#...#","..##....","........","........","....#..."}

    Returns: 0

  57. {".#......","..#.....","..#...#.","#....#..",".#......",".#.....#","#......#","......##","...###.."}

    Returns: 0

  58. {"..#......",".....#...","........#","...#.....",".......#.","#..#....#","..#.....#","#........","..#...##.",".....##.."}

    Returns: 0

  59. {"........",".##.....","#.....#.","#...##..","........",".#..#...","........","..##...#"}

    Returns: 0

  60. {"..#.#...","#.#.....","..#....#","........","....#...","...##...",".#..#...",".#......"}

    Returns: 0

  61. {".....#..#","..#...#..","#........","...##....",".#...##..","..#.#....","#.......#","........."}

    Returns: 0

  62. {"##.......","..#...#..","#...#....","..#......","........#",".#.....#.",".#.......","..#....##","........#","#........"}

    Returns: 0

  63. {"#..#....","........","#...#...","......##",".###....",".......#","....#...","....#...","........",".#....#."}

    Returns: 0

  64. {"##....#.","....#...","....#...","..#..#.#","#.......","....#..#",".....#..","#..#...#","...#...."}

    Returns: 0

  65. {"...#.#...","....#....","#........","..#.....#","#........","......##.","...#..#..","#...#...#"}

    Returns: 0

  66. {"#....#.#",".#......",".......#","..#...#.",".#.....#","....#.#.","...#....","..##.#..","......#."}

    Returns: 0

  67. {".......#.","........#","..#..#...","##.......",".....#...","...#..#..",".....#.##","...##...."}

    Returns: 0

  68. {"......#.",".##.....","..#....#",".#......","...#.#.#",".......#","#.....#.","......#.","#.#.#..."}

    Returns: 0

  69. {"...#..##","........","..#.#...","#.......",".##..#..","........","#...#...",".......#"}

    Returns: 0

  70. {".#.....#","...#.#..",".....#..","#.#....#","#...#...","..##....",".....#..","#......."}

    Returns: 0

  71. {"........","...#...#","...#..#.",".....##.",".......#",".#.##...","..#.....","..#....."}

    Returns: 0

  72. {".....#..","........","#...#.#.","..##....",".#..#...",".....#..",".#......","..#...#.","..#....#"}

    Returns: 0

  73. {".....#....","..#.......",".#........",".#....#...","..........","...#......","#.........","....#.....","..........",".......#.."}

    Returns: 7

  74. {"........#.","#.........","........#.","......#...","..#.......",".......#..","..........","...#......","....#.....","........#."}

    Returns: 7

  75. {"...#......","......#...","#.........",".......#..","..........",".....#....","....#.....",".........#"}

    Returns: 7

  76. {".......#..","..........",".....#....","....#.....","#.........","........#.","......#...","...#......"}

    Returns: 7

  77. {".....#...","#........",".....#...","....#....",".#.......",".....#...","........#","......#..","...#....."}

    Returns: 7

  78. {".......#..","..........",".#........","......#...","..........",".........#","..#.......","........#.",".....#..#.","#........."}

    Returns: 7

  79. {"#.........",".........#","......#...","..........","..........","...#......",".#........",".....#....","..#......."}

    Returns: 7

  80. {"...#......",".....#....","..#.......",".#........",".......#..","......#...","..........","........#.",".........."}

    Returns: 7

  81. {"....#.....",".....#....","......#...","..#.......","...#......","#....#....","..........",".#........",".......#.."}

    Returns: 7

  82. {"...#......","........#.","......#...",".........#",".#........",".....#....","....#.....",".......#.."}

    Returns: 8

  83. {"..........","..........","...#..#...","..........","........#.","........#.","#.......#."}

    Returns: 0

  84. {"..........","..........","...##.....","..........","..........","..........","..#.......","..........",".....#...."}

    Returns: 2

  85. {"......","......","......","......","......","......",".....#"}

    Returns: 1

  86. {"........","#.......","........","........","........","........"}

    Returns: 1

  87. {"...#....","....#...","........","#..#.#..","......##","....#.#.","#.#....."}

    Returns: 1

  88. {"......#.","..#....#",".#.#....","#..#.#..","#.......","........","......#.","........","........"}

    Returns: 0

  89. {"......","....#.","...#..","......","...#..","......","......","......","......"}

    Returns: 1

  90. {"......",".#.#..","..#...","..#.#.",".#....",".....#","......","#.#...","......"}

    Returns: 3

  91. {".....#....",".........#","#....#....","..........","..........",".#..#.....",".#.......#","..#.......",".........."}

    Returns: 3

  92. {"..#..###.","#........",".........",".........",".........",".........",".........","..#......"}

    Returns: 2

  93. {"........","........","..#...#.",".#......","........","........","........","........"}

    Returns: 1

  94. {".#.#.#..",".......#","#....#..","........","...#....","........"}

    Returns: 1

  95. {"......##","....#...","........",".....#..","........",".#......"}

    Returns: 3

  96. {".......",".......",".......",".......",".......","......."}

    Returns: 0

  97. {"........","......#.","...##...","....#...","........","..##....","........"}

    Returns: 2

  98. {".......#..","..........",".....#....","..........",".#........",".........#","..........","....#.....",".........."}

    Returns: 5

  99. {"......","......","......","......","......","......","......"}

    Returns: 0

  100. {"...#..","......","......","..#..#","......","......","......","..##..","......","......"}

    Returns: 1

  101. {"..#...","......","#.....","......","......","...#..","......"}

    Returns: 3

  102. {"#......","....##.",".#....#","....#..","#......",".....#.","#.....#",".......",".......",".#...#."}

    Returns: 0

  103. {"..........",".##.......","..........",".#..#.....","........#.","#.........","..#....#.."}

    Returns: 2

  104. {"........","........","......#.","........","....#.#.","..#.....","........",".....#.#",".......#","........"}

    Returns: 3

  105. {".......#","....#...",".#......","........","........","..#....."}

    Returns: 4

  106. {"..#.#.....",".........#","........#.","...#..##..","..........","....###.#.","#.........",".........."}

    Returns: 2

  107. {"..........","..........","..........","#.........",".......#..","......#...","....#.....","....#...#.","..........",".........."}

    Returns: 4

  108. {"......#...","..........","..........","........#.","...#......",".......#..","..........","..........","..........","#......#.."}

    Returns: 4

  109. {"..........","..........","..........","..........",".......#..","..........",".........#",".........#","..........",".........."}

    Returns: 1

  110. {"...#......","..........",".......##.","..........","#.....#...","#.........",".#........"}

    Returns: 3

  111. {"......","....#.","......","......","......","......"}

    Returns: 1

  112. {".........",".........",".........","........#",".........","..#.....#",".........","....#...."}

    Returns: 2

  113. {"##","##","##","##"}

    Returns: -1

  114. {".#.#.",".#..#",".##.#","##..#",".###."}

    Returns: -1

  115. {"........#.",".###..#.##","...#.#....",".##..#####",".#....#..#","..#..#.#.#"}

    Returns: -1

  116. {"..#..#.#",".##..#.#","#..##.#.","#.###...","########","#######."}

    Returns: -1

  117. {"..","..","#.","#.","##","##"}

    Returns: -1

  118. {"....","..##","..#.","....","..##","#..."}

    Returns: -1

  119. {"#"}

    Returns: -1

  120. {".#.#.#.#","#...#.#.",".###....","..##..#.","###.###."}

    Returns: -1

  121. {"#","#","#","#","#","#","#","#","#","#"}

    Returns: -1

  122. {"##########","..########","###.######","##########","###.#####."}

    Returns: -1

  123. {"#..#####","########","########","########","#..#####","#######.","########","#######.",".####.##"}

    Returns: -1

  124. {"###.####","#.#...##",".##....#","##.##.##","####.#..","######.#","##.####.","##.#####"}

    Returns: -1

  125. {"###.....","#..###..",".#.##.##","#.#.....","..###.#."}

    Returns: -1

  126. {"######","######",".#####","##.##."}

    Returns: -1

  127. {"#..#....##","###......#","#...#...##"}

    Returns: -1

  128. {"."}

    Returns: 0

  129. {"###", "###", "###"}

    Returns: -1

  130. {"#","#","#","."}

    Returns: -1

  131. {"#"}

    Returns: -1

  132. {"####.", "#...."}

    Returns: -1

  133. {"#####", "....."}

    Returns: -1

  134. {"#.","##","#.","#.",".."}

    Returns: -1

  135. {".#.","..#",".#.","###",".#.","..."}

    Returns: -1

  136. {"##...","....#",".....",".....","....#","..##.","#.#.#","....#"}

    Returns: -1

  137. {"##########", "..........", "..........", "..........", "..........", "..........", "..........", "..........", "..........", ".........." }

    Returns: 8

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: