Rooks
Time limit0.4sMemory limit1024 MB
Place the maximum number of non-attacking rooks on an N by N board where obstacles block lines of sight along ranks and files, and output one optimal placement.
- Level
Hard8 of 10
- Topics
- Graph, Greedy, Binary search, Union-find
- Solved
- No attempts yet
Problem
Consider a square board with N rows (called ranks) and N columns (called files). K of the squares are blocked by obstacles. Pieces similar to the rooks in chess are placed on this board. Two rooks are said to be attacking each other if they are on the same rank or file and there are no obstacles between them.
Given a positive integer N and the positions of the K obstacles, place as many rooks as possible on the board so that no two rooks attack each other.
Input
The first line of the input contains N and K, separated by a space. Each of the following K lines contain a pair of numbers r and f, separated by a space describing the rank and file of an obstacle. All the obstacles are distinct.
Output
The first line of the output must contain a single number S, the highest number of non-attacking rooks that the table can accommodate. Each of the following S lines must contain a pair of numbers r and f, separated by a space, showing the rank and file of a rook. Any correct placement of S rooks will be accepted.
Constraints
- 1 ≤ N ≤ 1,000
- 1 ≤ K ≤ min(N2, 2,000)
- Ranks and files are numbered from 1 to N.