@[toc] python 学习中,常会遇到一些百思不得其解的难题,但有时“灵光一现”找准方法,难题便会迎刃而解。
本专栏旨在记录本人解决问题的思考方法,及实现过程。有更好方法或对程序执行有疑问的伙伴,可在评论区留言,共同讨论。
题目要求
- 题目描述:在一串连续的迷宫(房间编号为1-11的连续数)中,玩家从第一个房间出发,每次可以走 1 格也可以走 2 格,其间有两个不连续的地雷房间。问玩家要走到第M格房间有多少种方法。(炸弹房号和终点房号通过键盘输入)
- 演示图例:以下炸弹房号为3和5,终点为7。
运行结果
- 共有2种走法。
- 方法1:[2, 1, 2, 1, 1](第1次走2格,第2次走1格,第3次走1格,第4次走1格)
- 方法2:[2, 1, 2, 2](第1次走2格,第2次走1格,第3次走2格,第4次走2格)
解决流程
- 通过递归函数,生成所有可能的方法列表;
- 在所有列表中,去除不能走到终点的列表;
- 在剩余列表中,去除重复路径;
- 去除会走到炸弹房间的路径。
实现 流程图: