提供一个计算机能理解的思路吧。
抓猫的时候，和这个猫之前的生活毫无关系，只和这只猫现在有可能在哪儿有关。开哪个门，决定了这只猫明天可能在哪儿。只要你可以不断压缩这个可能性，最后压缩到一个门里，这问题就解决了。
最开始的时候，这只猫的可能性是1 2 3 4 5 6 7。
如果抓1号门，确定了它不在1，那接下来一天它的可能性还是1 2 3 4 5 6 7。所以这一下是没意义的。因为猫可以从3到2。
如果抓2号门，确定了它不在2，那接下来一天它的可能性就变成了2 3 4 5 6 7。因为它不在2，所以没办法跑到1去。这就压缩了可能性。
第二天如果抓2，那结果还是2 3 4 5 6 7，毫无进展，所以没意义。
抓3，结果会变成1 3 4 5 6 7，变个形式，给接下来的一天提供方便。
第三天，抓4，可以确保接下来一天没有3，然后可能性变成2 4 5 6 7。以此类推，最后就能把门数减少到1个。核心技巧就是如果有一个门，它左边不可能右边可能，抓右边，这样这个门下次就不可能了。
当然怎么抓更快这是人类的思路，这个算法有个好处就是对于计算机来说足够暴力。你并不需要去教计算机应该抓哪个门，你让它全抓了然后剪枝加BFS即可。由于结果只和当前状态有关，所以最多出现
2^n
种可能性，可以有效地剪枝，避免无限深度。配合BFS，总可以最快速度地找到最优解。
import
queue
class
Solution
:
def
__init__
(
self
,
doors
,
path
=
[],
possible
=
set
()):
self
.
path
=
path
self
.
possible
=
possible
self
.
doors
=
doors
def
generate_next_steps
(
self
):
if
not
self
.
possible
:
return
None
next_steps
=
[]
for
i
in
self
.
possible
:
path
=
self
.
path
+
[
i
]
possible
=
set
()
for
elem
in
self
.
possible
:
if
elem
!=
i
:
if
elem
-
1
>=
1
:
possible
.
add
(
elem
-
1
)
if
elem
+
1
<=
self
.
doors
:
possible
.
add
(
elem
+
1
)
s
=
Solution
(
doors
=
self
.
doors
,
path
=
path
,
possible
=
possible
)
next_steps
.
append
(
s
)
return
next_steps
def
find_cat
(
n
):
checked_combination
=
set
()
solutions_queue
=
queue
.
Queue
()
solutions_queue
.
put
(
Solution
(
doors
=
n
,
path
=
[],
possible
=
set
(
i
for
i
in
range
(
1
,
n
+
1
))))
while
True
:
s
=
solutions_queue
.
get
()
next_steps
=
s
.
generate_next_steps
()
if
next_steps
is
None
:
return
s
.
path
for
n
in
next_steps
:
if
tuple
(
n
.
possible
)
not
in
checked_combination
:
checked_combination
.
add
(
tuple
(
n
.
possible
))
solutions_queue
.
put
(
n
)
print
(
find_cat
(
7
))
这里提供一个随手写的代码，核心思路就是上面说的，对于每种可能性，分别测试开其中某扇门之后的结果，然后剪去已经试过的状态，BFS。
python find_cat.py
[2, 3, 4, 5, 6, 2, 3, 4, 5, 6]
