Problem AC

In the game of Rhombinoes, you have a board made up entirely of equilateral trianges (see the image), some of which are “live” and some are “dead”. Your goal is to place down as many rhombinoes (“rhombus”-shaped pieces) as possible on the board. Each rhombino should exactly cover two “adjacent” live triangles that have a common side, and no two rhombinoes can use the same triangle.

Given the description of the live and dead triangles of a Rhombino board, what is the maximum number of rhombinoes you can simultaneously place down on the board?

Each triangle in the board has a pair of coordinates $(x, y)$. The bottom-left triangle has coordinates $(0, 0)$ and will always be a triangle with its tip pointed upward. For any given triangle with coordinates $(x, y)$, the triangle adjacent to it on its right-side (if any) has coordinates $(x+1, y)$, and the triangle adjacent to it on its top-side (if any) has coordinates $(x, y+1)$. Left-side and bottom-side adjacency are defined similarly.

Each board has a width $W$ and a height $H$. A board with width $W$ and height $H$ is the board which consists of all triangles with coordinates $(x, y)$ such that $0 \leq x < W$ and $0 \leq y < H$. For example, the game board in the image has width $6$ and height $3$.

(See Figure 1 for clarification.)

\includegraphics[width=0.3\textwidth ]{rhombus.pdf}
Figure 1: Sample input, with cells $(1,1)$, $(2,2)$, $(4,1)$, and $(3,0)$ dead.


The first line of input contains three space-separated integers $W$, $H$, and $K$.

$W$ is the width of the board, $H$ is the height, and $K$ is the number of dead triangles on the board ($1 \leq W \leq 100$, $1 \leq H \leq 100$, $1 \leq K \leq W\cdot H \leq 1000$).

Exactly $K$ lines will follow. Each such line will contain a pair of space-separated integers $x$ and $y$ ($0 \leq x < W$, $0 \leq y < H$), indicating that the triangle with coordinates $(x,y)$ is a dead triangle. All other triangles are live.


Output a line containing a single integer, the maximum number of rhombinoes you can simultaneously place down on the board.

Sample Input 1 Sample Output 1
6 3 4
1 1
2 2
4 1
3 0

Please log in to submit a solution to this problem

Log in