uc berkeley CS 61B homework 9

这个作业还是比较简单的，但是非常难以理解+_+ 可能我英语不太好的缘故，读了好多遍才知道要干啥。。。。

其实这个作业就是让大家消去一部分walls，是得每两个cell之间有且仅有一条path。


距离修完cs61b仅有一步之遥了！！
https://www.1point3acres.com/bbs/forum.php?mod=attachment&aid=MjYyODQwfDE0N2UzNjRmZjdmYzlmMzQ2OGRjYWQ4MzM2ZGY3MDNifDE3ODQ2MTQ5NzI%3D&request=yes&_f=.png

这次的作业十分有趣！
我感觉重点是随机选取Maze中的wall所使用到的方法：
将Maze中所有水平和垂直方向的wall编号，放入一个数组中，首先设定数值w等于数组长度。随机取数randInt(w)，取数组中随机数序号上wall的编号，对这只wall
进行处理(决定是打开wall还是保持原状)。最后将用到的wall编号与数组最后一位(w - 1)进行互换，w--，循环。这样再也不会重复处理已经处理过的wall了。

先贴作业:

以上是作业的partI

partII要口头设计一个DFS生成迷宫的算法,有两个要求:
1. 最后生成的是树, 没有circle; 且要能遍历
2. 每一次的生成要足够random

以下是partII
1. Mark all walls true (unbroken)
2. Randomly choose a starting cell
3. Marked this cell visited
4. Loop (every direction that has an unbroken (true) wall && through which you find an unvisited cell)
-----4.1 Randomly choose one direction
-----4.2 Go through that wall to another cell, mark the wall brokedn (false)
-----4.2 Recursive DFS call on that cell

i. 显然通过marked visited可以保证生成的是树,没有circle; 这是DFS本身的特性;
ii. 每个wall不管是true or false, 都代表一条edge, 所以这是个connected的图, 则DFS一定能遍历, 这也是DFS本身的特性;
iii. 因为起点是randomly chosen, 每一步的方向也是randomly chosen, 所以应该就保证random的树生成了

i和ii保证了要求1
iii I assume保证了要求2吧......
_______________________________________________________________________________________________
到了hw9, 终于有一种自己的code style美如画的错觉了......
终于第一次不怎么debug就跑出来结果了.....
可能因为前面tree的部分各种分情况讨论, 弄得code也丑, 又容易出错吧....

题目是按照column存的而不是按照row来存的。注意。
index的转换要注意。wall的一维index--wall的二维index--cell的二维index--cell的一维index。由wall到cell多对一。

太厉害了，坚持下来真不容易啊，我还在tree这一部分纠结。

voiding 发表于 2014-10-14 05:54
太厉害了，坚持下来真不容易啊，我还在tree这一部分纠结。

一起加油！

作业入口：http://www.cs.berkeley.edu/~jrs/61b/hw/hw9/要求掌握 Disjoint Sets  不相交集的知识。

绘制迷宫图，使任意两个像素点(cell)之间仅有一条通路。示意图如下。

按照提示完成即可，不是很难，注意union函数的参数要保证是root！

最后冲刺，cs61b, 加油！！！！！！

交作业，拿学分， 坚持住，争取今天把hw10也做了

交作业

hw9 done.

交作业咯

这次作业不难，别把vertical和horizontal的cell搞反了就行！还差一次作业就搞定cs61b了，想想就有点小激动啊！