Connection Status:
Competition Arena > Permatch

Permatch

TCO17 New 3B · 2017-03-31 · by subscriber

TCO17 New 3B · 2017-03-31 · by subscriber · Dynamic Programming, Graph Theory
Class Name: Permatch
Return Type: int
Method Name: complete
Arg Types: (vector<string>)
Problem Statement

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.

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
0)
{"##"}
Returns: 0
1)
{"#."}
Returns: 1
2)
{"###",
 ".#."}
Returns: 0
3)
{"###",
 "..."}
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.)

4)
{"#..##",
 "###.."}
Returns: 0
5)
{".#..##",
 "####..",
 "#....."}
Returns: 0

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

6)
{".#..##",
 "#.##..",
 "......"}
Returns: 2

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

7)
{"##",
 "##"}
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.

Submissions are judged against all 137 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Permatch with a public method int complete(vector<string> board) · 137 test cases · 2 s / 256 MB per case

Submitting as anonymous