P10939 Knight Placement

Given an $N \times M$ chessboard, some cells are forbidden for placing pieces. Find the maximum number of knights (the “knight” in international chess, similar to the “horse” in Chinese chess, which attacks in an L-shape, but without the “blocked leg” rule in Chinese chess) that can be placed on the board so that no two knights attack each other.

The first line contains three integers $N, M, T$, where $T$ is the number of forbidden cells. The next $T$ lines each contain two integers $x$ and $y$, indicating that the cell at row $x$, column $y$ is forbidden for placement. Rows and columns are numbered starting from $1$.

Output one integer representing the result.

$1 \le N, M \le 100$ Translated by ChatGPT 5