uc berkeley CS 61B homework 9

hypsm 发表于 2016-2-4 02:18
搞完了，犯了一个超级超级傻逼的错误！
写出了这样一个判断:
   if(set.find(s1) != set.find(s2)) ...

我在if里用到递归了，可以成功运行啊

不难
还是按照老师的一步步走
个人觉得最难在于如何简洁表示wallArray数组。。。。= =

看了好几遍才看懂题目。。。实现起来确实很简单。。。

还有最后一次作业了，比上劼慢了整整两个多月。。。这进度真是醉了。。。 来领学分，版主好久没有发学分了

能出错的地方实在太多，建议可以先用较小的maze进行debug。
union注意要用root。仔细读题 一步一步来。
这次作业做下来很受鼓舞 加油~！！

(a)  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)?
Because the disjointed sets are utilized, each cell can only be reached through only one path, the DFS is a wise choice then.
(PS: Disjointed sets can use one array to generate multiple trees, and utilize "union" to combine them by considering root, in this case, no duplicate item will be shown in different trees)

(b)  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?
Random number is utilized to choose next wall into consideration randomly, and mark the wall as true (closed) or false (open),so that the maze can be presented randomly. Furthermore, the direction and status of room will be made.

看懂题目花了很多时间。。最后根据一个墙的序号判断周围2个cell的时候一开始写错了，没注意vertical的顺序是按column排序的

代码里面vertical和horizon混淆得厉害，写了5段调试代码才调好。。

倒数第二个啦，对union find的实现有了进一步认识，用array实现确实非常方便。
要注意的是如何根据wallArray的序号倒推cell的序号。这里horizontal wall的横向range有h，vertical wall的横向range为h-1，在取模的时候需要注意。

debug了一晚上，结果就是做个乘法时写错位了。。。。

还差一次作业了，不过学完后还是要系统的看一下。