DWITE '10 R5 #2 - Safe from Rooks

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type
DWITE Online Computer Programming Contest, February 2011, Problem 2

In chess, a rook is a piece that can move to any other square on the row or column it is on. So, we say that it threatens all the squares on the row and column it is on (because it can threaten to capture any of the opponent's piece on these squares; if there are multiple pieces in a row, the threat upon the further piece is known as skewer or an x-ray attack /chess-trivia). Given the positions of rooks on a chess board, whose dimensions aren't necessarily 8 by 8, determine the number of squares that are not threatened by rooks.

The input will contain 5 test cases. The first line of each test case contains three numbers, R, C and Ro (1 \le R, C \le 31\,000, 1 \le Ro \le 20) representing the number of rows and the number of columns on our chess board (where the rows are numbered bottom up, and the columns are numbered left to right) and the number of rooks on the board respectively. The next Ro lines each contain two numbers X and Y (1 \le X \le R, 1 \le Y \le C) representing the position of a rook on the board.

The output should contain 5 lines, where each line represents the number of squares on the chessboard that are not being threatened by rooks.

Sample Input

3 3 1
2 2
8 8 3
1 1
5 5
8 8

Sample Output


Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


There are no comments at the moment.