Unattacked Cells on a Chessboard

Given an \(n \times m\) chessboard with rows and columns numbered starting from 1, you are to place \(K\) queens on the board. A queen attacks all cells in the same row, the same column, and along the two diagonals (both the main diagonal and the anti-diagonal) passing through it. After placing all queens, determine the number of cells that are not attacked by any queen.

Note: A queen at position \((r, c)\) attacks any cell \((i, j)\) if either \(i=r\), \(j=c\), \(|i-r| = |j-c|\) (i.e. they lie on the same diagonal) holds.

The problem can be solved by first noting that any cell that lies in a row or column containing a queen is automatically attacked. Let the set of safe rows (not containing any queen) and safe columns (not containing any queen) be determined. Then among the cells in the safe region, a cell \((i, j)\) is attacked diagonally if \(i-j = d\) for some queen (where \(d=r-c\)) or \(i+j = s\) for some queen (where \(s=r+c\)).

Thus, if we define:

• \(R\): the set of rows containing a queen
• \(C\): the set of columns containing a queen
• Safe rows: those \(i\) with \(1 \le i \le n\) and \(i \notin R\)
• Safe columns: those \(j\) with \(1 \le j \le m\) and \(j \notin C\)
• \(D_1\): the set of values \(d = r-c\) for each queen
• \(D_2\): the set of values \(s = r+c\) for each queen

The total number of cells not attacked by any queen is then given by:

[ \text{answer} = (#safe\ rows \times #safe\ columns) - (\text{# of safe cells attacked diagonally}) ]

To count the number of safe cells attacked diagonally, we do the following:

1. For each \(d \in D_1\), for every safe row \(i\), check if \(j=i-d\) is a safe column. Sum these up as \(A\).
2. For each \(s \in D_2\), for every safe row \(i\), check if \(j=s-i\) is a safe column. Sum these up as \(B\).
3. A safe cell that satisfies both conditions (belongs to some attacked main diagonal and some attacked anti-diagonal) is counted twice in \(A+B\). For each pair \((d, s)\) with \(d \in D_1, s \in D_2\) such that \(d+s\) is even, let \(i=(d+s)/2\) and \(j=(s-d)/2\); if \(i\) is a safe row and \(j\) a safe column then count it once. Let the sum of these be \(C\).
4. Then the number of safe cells attacked diagonally is \(A+B-C\) and the final answer is \((\#safe\ rows\times\#safe\ columns) - (A+B-C)\).

Below are the detailed input and output specifications along with sample test cases and five solutions in different programming languages.

inputFormat

The first line contains three integers \(n\), \(m\), and \(K\) (\(1 \le n, m\); \(0 \le K \le n \times m\)). Each of the next \(K\) lines contains two integers \(r\) and \(c\) representing the row and column position of a queen.

outputFormat

Output a single integer representing the number of cells that are not attacked by any queen.

sample

3 3 1
2 2

0