Demon King's Maze (APCS 2021-09 Intermediate)

There is an \(n\times m\) board. Its rows are numbered from \(0\) to \(n-1\), and its columns are numbered from \(0\) to \(m-1\). Initially, there are \(k\) demon kings on the board.

Demon king \(i\) starts at \((r_i,c_i)\) and has the fixed movement vector \((s_i,t_i)\). If it is currently at \((x,y)\), one move takes it to

Every round consists of the following steps, in this order:

1. Every demon king still on the board simultaneously places one bomb on its current cell.
2. Every demon king still on the board simultaneously moves once using its own movement vector.
3. Any demon king now outside the board immediately disappears.
4. Among the remaining demon kings, every one that has landed on a cell containing a bomb detonates that cell. All demon kings and all bombs on every such cell disappear simultaneously.

Step 4 is evaluated simultaneously. For example, if two demon kings land on the same bomb cell in one round, both disappear. Processing one first and removing the bomb must not allow the other one to survive. A cell containing multiple bombs still counts as only one cell with bombs in the answer.

The quadruples \((r_i,c_i,s_i,t_i)\) of all demon kings are distinct. Rounds continue until no demon king remains on the board. Determine how many cells then contain at least one bomb.

Input Format

The first line contains three integers \(n,m,k\).

Each of the next \(k\) lines contains four integers \(r_i,c_i,s_i,t_i\), giving the starting cell and fixed movement vector of demon king \(i\).

Constraints

• \(1\le n,m\le100\)
• \(1\le k\le500\)
• \(0\le r_i<n\)
• \(0\le c_i<m\)
• \(-100\le s_i,t_i\le100\)
• All \((r_i,c_i,s_i,t_i)\) are distinct.
• All input values are integers.

Output Format

Output one integer: the number of cells that contain at least one bomb after all demon kings have disappeared.

Scoring

The two samples are judged in a zero-point batch. There are exactly \(20\) scored test groups, each worth \(5\) points:

• Groups \(1\) through \(10\) (\(50\) points): \(n=1\), and every demon king satisfies \(r_i=0\) and \(s_i=0\).
• Groups \(11\) through \(20\) (\(50\) points): no additional constraints.

Sample Input 1

1 6 3
0 0 0 0
0 2 0 -1
0 4 0 2

Sample Output 1

4

Sample Explanation 1

In the first round, the first demon king places a bomb at position \(0\) and does not move. It therefore lands on its own new bomb, so both disappear.

The second demon king places bombs at positions \(2,1,0\) before leaving the board. The third one places a bomb at position \(4\) before leaving. Thus the four positions \(0,1,2,4\) contain bombs at the end.

Sample Input 2

5 5 2
0 0 3 2
0 0 2 3

Sample Output 2

3

Sample Explanation 2

In round one, both demon kings place bombs at \((0,0)\) and then move to \((3,2)\) and \((2,3)\). In round two, they place bombs on those two cells and then both leave the board.

The cells containing bombs are \((0,0)\), \((3,2)\), and \((2,3)\), for a total of three. Although two bombs were placed at \((0,0)\), it still counts as one cell.

Source

APCS September 2021, Programming Problem 2. The rules are based on ZeroJudge g276, "Demon King's Maze" and Yi-Zhe Wang's tutorial. AACPOJ reorganized the statement and made the simultaneous-round semantics and input bounds explicit.