uc berkeley CS 61B homework 9

迷宫连通是并查集的经典应用了。。

写完了~  一定要看清楚hwall和vwall是咋表示的。。不要搞反了

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

Homework9 done

先贴作业:

以上是作业的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也丑, 又容易出错吧....

交作业