题目描述

爱丽丝和鲍勃经常在棋盘上玩游戏。有一天,爱丽丝画了一块尺寸为$M * N$的板。她希望鲍勃使用很多尺寸为$1 * 2$的卡片来覆盖电路板。然而,她认为$Bob$太容易了,所以她在板子上做了一些洞(如下图所示)。

我们称一个网格,它不包含一个洞,一个正常的网格。鲍勃必须遵循下面的规则:

1.任何普通网格都应该用一张卡覆盖。

2.一张卡应该覆盖两个正常的相邻网格。

下文各举例说明:

$VALID$ 解决方案。

无效的溶液,因为红色的孔被卡覆盖。

无效的解决方案,因为存在一个网格,没有覆盖。

你的任务是帮助鲍勃决定是否可以根据上述规则覆盖棋盘。

输入

第一行有3个整数:$m,n,k(0<m,n<=32,0 <=K<m*n)$,行数、列和空穴数。在接下来的$k$行中,每行中都有一对整数$(x,y)$,它表示第$y$行中的一个洞,即第$x$列。

输出：

如果可以覆盖板,输出$“YES”$。否则,输出$“NO”$。 输入数 1

4 3 2
2 1
3 3

输出数位 1

YES

提示

样品输入的可能解决方案。 来源

POJ 月刊,charlescpp