Indian Computing Olympiad

Training Material


Advanced Graph Algorithms→Placing Rooks

Given a chess board in which some squares are obstacles (#) and other are holes (O). You have to place the maximum number of rooks on this chess board such that no pair of rooks attack each other.

  1. A rook cannot be placed on a hole.
  2. A rook attacks the row and column on which it is placed. The attacking range of a rook can span a hole, but is blocked by an obstacle.

Here is an example (not maximum!)

            -------------------------------
           |   |   |   |   |   |   | R |   |
            -------------------------------
           |   | R |   |   |   |   |   |   |
            -------------------------------
           | R | # | R |   |   |   |   |   |
            -------------------------------
           |   |   |   |   |   |   | O |   |
            -------------------------------
           |   |   |   |   | # |   |   |   |
            -------------------------------
           |   |   |   |   | R |   |   |   |
            -------------------------------
           |   |   |   |   |   |   |   |   |
            -------------------------------
      

Solution