b***e
发帖数: 1419 | 1 好，就送佛送到西吧。
贼的位置可以分为两种情况：
1. 第一天贼在奇数号房子。在这种情况下，贼在奇数天必在奇数号房子，偶数天必在
偶数号房子。我们称这种贼为顺贼。
2. 第一天贼在偶数号房子。在这种情况下，贼在奇数天必在偶数号房子，偶数天必在
奇数号房子。我们称这种贼为逆贼。
显然，这两种情况是完全不相交的，即顺贼永远不可能变成逆贼，逆贼也永远不可能变
成顺贼。
一个抓捕的序列，如果能抓住这个贼，那么只能是从一头向另外一头把他逼到死角。这
一共就四种可能性：
1. 从左向右抓顺贼
2. 从左向右抓逆贼
3. 从右向左抓顺贼
4. 从右向左抓逆贼
所以判断抓捕序列的有效性等同于判断(1 or 3) and (2 or 4)，即顺贼逆贼都会落网
。这四种情况是完全对称的。所以以下仅说明情况1的做法，即判断一个抓捕序列是否
可以从左向右抓住顺贼。
这个抓捕的顺序必须包含一个顺捕序列，其开始必然是在某一奇数天在一号房进行抓捕
。然后每一天向右挪一，以做到每次控制抓捕房子以左的地盘，把贼限制在右侧。如果
有一天没有按照计划向右挪一，那就会丢失一座房子的地盘。所以最后有效的抓捕序列
必然控制了所有... 阅读全帖 |
|
