@[Edward_Tsui](/space/show?uid=23314) 可以艾特管理哟
by YZHX @ 2018-10-14 14:48:25
@[Edward_Tsui](/space/show?uid=23314)
本题出自《算法导论》第26章思考题 26-1 Escape problem。
《算法导论》的中译本里面，译文确实长这个样。不过我重新翻译一下好了。
by Planet6174 @ 2018-10-14 15:10:26
图：
by Planet6174 @ 2018-10-14 15:11:49
```
```
by Planet6174 @ 2018-10-14 15:19:10
**译自 CLRS Problem 26-1 Escape problem**
在一个 $n\times n$ 的网格中有 $m$ 个起始点 $(x_1, y_1),$ $(x_2, y_2),$ $\dots,$ $(x_m, y_m)$，试问：能否为这些结点分别找一条到边界的路径，且这 $m$ 条路径互不相交（即任意两条路径上没有一个相同的结点）。
黑点表示起始点，其他点用白点表示。找出的路径用加粗的线表示。图 (a) 存在符合条件的 $m$ 条路径，图 (b) 则不存在。
### 输入格式
第一行是一个整数，为 $n$ $(1\le n≤35)$。
第二行还是一个整数，为 $m(1\le m\le n^2)$。
以下 $m$ 行，第 $(i+2)$ 行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 行第 $j$ 列的点是起始点。保证起始点坐标互不相同。
### 输出格式
只包括一行。若存在逃脱输出 `YES`，不存在逃脱输出 `NO`。
```plain
**译自 CLRS Problem 26-1 Escape problem**
在一个 $n\times n$ 的网格中有 $m$ 个起始点 $(x_1, y_1),$ $(x_2, y_2),$ $\dots,$ $(x_m, y_m)$，试问：能否为这些结点分别找一条到边界的路径，且这 $m$ 条路径互不相交（即任意两条路径上没有一个相同的结点）。
黑点表示起始点，其他点用白点表示。找出的路径用加粗的线表示。图 (a) 存在符合条件的 $m$ 条路径，图 (b) 则不存在。
### 输入格式
第一行是一个整数，为 $n$ $(1\le n≤35)$。
第二行还是一个整数，为 $m(1\le m\le n^2)$。
以下 $m$ 行，第 $(i+2)$ 行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 行第 $j$ 列的点是起始点。保证起始点坐标互不相同。
### 输出格式
只包括一行。若存在逃脱输出 `YES`，不存在逃脱输出 `NO`。
```
by Planet6174 @ 2018-10-14 15:45:10
@[chen_zhe](/space/show?uid=8457)
by Planet6174 @ 2018-10-14 20:43:08
谢谢~~
by Edward_Tsui @ 2018-10-16 06:34:55