Time Dragging
Time limit1sMemory limit512 MB
Given an N by M board with marked cells, find the longest sequence of row and column picks such that no pick creates a marked intersection among chosen lines.
- Level
Hard8 of 10
- Topics
- Greedy, Graph, Dynamic programming, Combinatorics
- Solved
- No attempts yet
Problem
Younghee and Chulsoo are playing a game before they start studying. The game takes place on an N × M board, and some cells are marked with an X.
The two play in turns, following these rules.
- A player picks a row or column that has not been picked yet, and the intersections of that row or column with all previously picked rows and columns must not contain an X.
- After the pick, it is the opponent's turn.
- If no row or column satisfies the condition (or all rows and columns have already been picked), that player loses and the game ends.
For example, consider the following board.
Suppose the second row, the fourth row, and the second column have been picked so far. In that case, any pick other than the first row or the fourth column would put an X at an intersection of picked rows and columns. So the next pick must be the first row or the first column, and after that any row or column picked would put an X at an intersection, so the total number of picks is 4, and no strategy can make more picks than this.
Chulsoo and Younghee hate studying so much that, regardless of who wins, they make the choices that keep the game going longest. Find the maximum total number of picks the two of them can make.
Input
The first line gives the board dimensions N and M and the number of cells marked with an X, K, separated by spaces. (1 ≤ N, M ≤ 200, 1 ≤ K ≤ NM)
Each of the next K lines gives two positive integers x and y, separated by a space. (1 ≤ x ≤ N, 1 ≤ y ≤ M) This means the cell in row x, column y is marked with an X.
No cell marked with an X is given more than once.
Output
Print the total number of picks Chulsoo and Younghee make together on the first line.