uc berkeley CS 61B homework 9

交作业～～老师的提示写得好！

交作业了，这次很顺

交作业，字数字数
用DFS又做了一遍，
思路：
1，生成一个二维的cell数组，存cell，cell保存自己的坐标和一个是否被访问过的标记。
2，随机选一个cell作为root，然后开始DFS它的每一个邻居。
3，把没有被访问过的邻居之间的墙拆掉，然后设置这个邻居为访问过。
4，DFS邻居的关键：随机顺序DFS，用switch case 决定先DFS哪个邻居。

20X10的maze，感觉老外的行和列的第一感觉和我们不太一样……导致把矩阵存在一维数组里面没有以前那么顺……

老师给完提示以后确实好简单，但是好多地方容易出错，还是花了多时间debug。比如random完之后应该存一下，我没意识到每次都用random表示，就会每次都执行一遍。另外横纵坐标容易表示错。最后对递归更明白了一点。

也是读了很多遍作业要求才明白到底要干啥啊QAQ。。。再冲刺一把就要结束了！！加油！

忙着玩了几天感觉要废掉了，刚开始看题目时都不知道是要干嘛。。。

一开始没搞懂是什么和什么，然后发现，提示实在是非常详细....

交作业啦,好开心!还有最后一个homework 和project.
这是part2的答案:
First we create a graph of cells, in which every cell has directed edges from itself to all its neighbors.
Then we randomly choose a initial cell, eg (0,0) cell, call DFS() on that node. The DFS() here is the same as the lecture's version, except a difference: if we encounter a cell v that is visited already from current node u, then we remove the edge from u to v.
Finally, after the depth-first search finishes, the correct maze will be created successfully.
1) How would your algorithm ensure that there is a path between every pair of cells, but no more than one path between any pair of cells (i.e., no cycles)?
Always has path: In the beginnnig, all the cells are completely connected. So every cell can be visited from the initial cell.
No cycles: if we encounter a visited cell u from cell v, it means that there is already a path from u to v(order doesn't matter). But now we encounter another edge from v to u, which will make a cycle. Therefore, this is the reason why we need to remove the directed edge from v to u. If u finds its neighbor v also visited, directed edge from u to v will also be removed. Then there  will be no edges between u and v, then it means that the wall between u and v exists. By removing the directed edge from a node to an already visited neighbor node, we can make sure that there won't be cycles.

2) How does your algorithm use random numbers to generate a different maze each time? Specifically, what decision should be made by random numbers at each recursive invocation of the depth-first search method?
We can generate a random number between 0 to (# of neighbors - 1), and choose (random # + 1)th neighbor of current cell, and recursively call DFS() on that neighbor.

为什么大家觉得好简单。。。我觉得好难啊。。。。
继续努力！反复思考！