← 返回题目列表

AtCoder · abc413_g

G. 大禁格

中文机器翻译题面 查看原题

分数: 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