分数: 575 点
问题陈述
有一个 H \times W 网格。 让 (i,j) 表示位于 i第行 (1\le i\le H) 从顶部和 j第列 (1\le j\le W) 从左边开始。
网格中的每个单元格要么上面放置了障碍物,要么上面没有放置任何东西。有 K 有障碍的细胞:细胞 (r_1,c_1),(r_2,c_2),\ldots,(r_K,c_K).
高桥最初在牢房 (1,1) 想要到达小区 (H,W) 通过重复移动到没有放置任何内容的相邻单元格(上、下、左、右)。
更准确地说,他可以根据需要多次重复以下操作:
- 选择以下四种操作之一并执行所选操作:
- If 1\lt i 和细胞 (i-1,j) 上没有放置任何内容,移至单元格 (i-1,j)。否则,请勿移动。
- If 1\lt j 和细胞 (i,j-1) 上没有放置任何内容,移至单元格 (i,j-1)。否则,请勿移动。
- If i\lt H 和细胞 (i+1,j) 上没有放置任何内容,移至单元格 (i+1,j)。否则,请勿移动。
- If j\lt W 和细胞 (i,j+1) 上没有放置任何内容,移至单元格 (i,j+1)。否则,请勿移动。
确定他是否可以移出单元格 (1,1) 到单元格 (H,W).
约束
- 1\le H\le2\times10^5
- 1\le W\le2\times10^5
- 0\le K\le2\times10^5
- 1\le r_i\le H\ (1\le i\le K)
- 1\le c_i\le W\ (1\le i\le K)
- (r_i,c_i)\ne(1,1)\ (1\le i\le K)
- (r_i,c_i)\ne(H,W)\ (1\le i\le K)
- (r_i,c_i)\ne(r_j,c_j)\ (1\le i\lt j\le K)
- 所有输入值均为整数。
输入
输入由标准输入给出,格式如下:
H W K r_1 c_1 r_2 c_2 \vdots r_K c_K
输出
如果高桥可以从牢房中移动 (1,1) 到单元格 (H,W) 通过重复问题中描述的操作,打印 Yes;否则,打印 No.
示例输入 1
4 5 5 1 4 2 3 3 2 3 4 4 2
示例输出 1
No
网格如下所示:

高桥无法从牢房中移动 (1,1) 到单元格 (4,5).
示例输入 2
2 7 3 1 2 2 4 1 6
示例输出 2
Yes
网格如下所示:

他可以离开牢房 如图所示移动 (1,1) 到单元格 (2,7) 。
示例输入 3
1 1 0
示例输出 3
Yes
请注意,可能存在不需要移动或没有放置障碍物的情况。
示例输入 4
10 12 20 8 3 1 11 6 4 3 7 10 4 5 7 4 7 5 5 4 3 6 1 1 6 2 7 6 7 1 3 6 3 2 12 9 6 7 3 3 11 9 7
示例输出 4
Yes