AT_abc205_f [ABC205F] Grid and Tokens

题目描述

有一个 $H$ 行 $W$ 列的网格，用 $(r,\,c)$ 表示从上往下第 $r$ 行、从左往右第 $c$ 列的格子。

有 $N$ 个棋子，对于第 $i$ 个棋子（$1 \leq i \leq N$），你可以选择以下两种方式之一：

• 将它放在满足 $A_i \leq r \leq C_i$ 且 $B_i \leq c \leq D_i$ 的某一个格子 $(r,\,c)$ 上；
• 不放置该棋子。

这里，不能有两个棋子放在同一行或同一列。

你最多能放置多少个棋子？

输入格式

输入以如下格式从标准输入读入。

$H$ $W$ $N$ $A_1$ $B_1$ $C_1$ $D_1$ $A_2$ $B_2$ $C_2$ $D_2$ $\vdots$ $A_N$ $B_N$ $C_N$ $D_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2 3 3
1 1 2 2
1 2 2 3
1 1 1 3

输出 #1

2

输入输出样例 #2

输入 #2

5 5 3
1 1 5 5
1 1 4 4
2 2 3 3

输出 #2

3

说明/提示

限制条件

• $1 \leq H,\, W,\, N \leq 100$
• $1 \leq A_i \leq C_i \leq H$
• $1 \leq B_i \leq D_i \leq W$
• 输入均为整数。

样例解释 1

可以将第一个棋子放在格子 $(1,\,1)$，第二个棋子放在格子 $(2,\,2)$，第三个棋子不放，这样最多可以放 $2$ 个棋子。无法放置 $3$ 个棋子，因此输出 $2$。

由 ChatGPT 4.1 翻译