一 题目：
Quiz 7
Randomly fills a grid with True and False, with width, height and density controlled by user input, and computes the number of all "good paths" that link a point of coordinates (x1, y1) to a point of coordinates (x2, y2) (x1 and x2 are horizontal coordinates, increasing from left to right, y1 and y2 are vertical coordinates, increasing from top to bottom, both starting from 0), that is:
paths that go through nothing but True values in the grid;
paths that never go through a given point in the grid more than once;
paths that never keep the same direction (North, South, East, West) over a distance greater than 2.
二 解析：
首先输入 4个参数 分别为表示 输入的随机种子，密度，待生成的数组高度，待生成的数组宽度。
总之，4个参数决定了grid中的内容。
例如 输入 0 4 6 5 生成的grid 为：
接下来需要在输入4个参数，两两组合为路径的起点和终点
例如输入0 0 3 5 代表起点为（0，0） 终点为（3，5）
此处有需要注意 （3，5）对应上面生成的grid 中的 grid[5][3]
想求从（0，0）到（3，5）有多少条路径
其中对于路径的选择有一些限制条件
1.移动的方向为 东南西北 4个方向，即当前点的坐标（x，y）可以移动到 [(x-1, y+0), (x+1, y+0), (x+0, y+1), (x+0, y-1)]
2.已经在路径中的点，不可再走
3.同一个方向移动，最多只可连续移动2次，如果已经连续向东移动了两次，那么下一步不可以向东继续移动。
针对于以上的要求，上面案例，可得到5条可选路径
(0,0) (1,0) (1,1) (0,1) (0,2) (1,2) (1,3) (0,3) (0,4) (0,5) (1,5) (2,5) (2,4) (3,4) (3,5)
(0,0) (1,0) (1,1) (2,1) (2,2) (1,2) (1,3) (0,3) (0,4) (0,5) (1,5) (2,5) (2,4) (3,4) (3,5)
(0,0) (0,1) (1,1) (2,1) (2,2) (1,2) (1,3) (0,3) (0,4) (0,5) (1,5) (2,5) (2,4) (3,4) (3,5)
(0,0) (0,1) (1,1) (1,2) (1,3) (0,3) (0,4) (0,5) (1,5) (2,5) (2,4) (3,4) (3,5)
(0,0) (0,1) (0,2) (1,2) (1,3) (0,3) (0,4) (0,5) (1,5) (2,5) (2,4) (3,4) (3,5)
注意 上面的点坐标对应到grid x,y 都是互换的。
以上题目解析完毕
下面开始代码实现，这是一道典型的栈的运用。栈的性质，先进后出。此题为路径的寻找，用回溯的方式找到所有可实现的路径。
path_stack 存放当前的走过的点，可以在用一个direction_stack存放对应移动方向的信息。
方向从0-3依次对应 [(-1, 0), (1, 0), (0, 1), (0, -1)]4个方向
初始化，起点入栈path_stack，方向0作为起始方向
当path_stack不为空，那么就一直继续探寻下去，取出path_stack中最后的一个点，以及从direction_stack拿到方向，依此查看下一方向的点是否满足要求，即是否在grid的范围，是否超同一个方向连续移动超过2次，是否grid对用的值为1。
如果没有可移动的点，那么将此点从path_stack移除，即出栈。
如果探寻到下一个可移动的点，那么将这个点入栈到path_stack中，同时也将方向入栈到direction_stack。
如果探寻的下一个可移动的点为要求的终点，那么满足要求的路径数量+1。将终点出栈，继续回溯。
当栈path_stack为空时，即说明已经遍历所有的可能路径。
三 总结
考察点：路径搜索，栈的应用
python 中的list 就支持栈的方法，pop() append()等
四 思考
1. 数据结构，栈的特性是什么，它可以应用到哪些场景，对于此场景栈对比于其他的数据结构有哪些优势？
数据结构的学习，安利下清华大学 邓俊辉的数据结构，此教材中使用的编程语言是c/c++，对于数据结构的学习以及后续9024的课程都有很大的帮助。
2. python中常用的模块
比如此quiz中的collections，random，Numpy
五 代码实现
稍后发布。
有问题，想讨论的都可以联系我，下面是我的微信。
