UVa 10615

From Algorithmist
Jump to navigation Jump to search

UVa 10615 - Rooks[edit]

Summary[edit]

Given is a set of rooks on a chessboard. Color the rooks using a minimal number of colors so that no two rooks in the same row/colums have the same color.

Explanation[edit]

Consider a bipartite graph, where vertices of one partition represent rows of the board, the other partition are columns, and each rook corresponds to an edge in the graph. Look at the rooks that have the same color. As no two of them share a row or a column, they correspond to a matching in our graph.

Clearly we need as many colors as the maximum degree in our graph, i.e., the largest number of rooks in some row or column. It can be shown that this number of colors is always sufficient.

One possible algorithm is to add colors one by one, always finding such maximal matching that contains all the vertices with currently maximal degree.

There is an even faster solution: Knowing the number of colors you want to use, color the rooks one by one. When coloring a rook R, look at the set of available colors in its row and at the set of available colors in its column. If their intersection is non-empty, pick any color from the intersection and continue. Otherwise, let A be any available color in the rook's row, B any available color in its column.

Use color A on R. This will violate the coloring condition for one rook in R's column. Recolor this rook to B. This will violate the coloring for at most one other rook in that rook's row, and so on. Continue recoloring the rooks along this "path". It can be proved that this process will terminate and it won't reach the rook in R's row that has the color B.

Input[edit]

2
2
*.
**
4
*.*.
*.*.
***.
..**

Output[edit]

2
2 0
1 2
4
1 0 2 0
3 0 1 0
2 1 3 0
0 0 4 1