uc berkeley CS 61B homework 9

理解题意是个大问题，光读题就读了快两小时。。。。
这个题的关键就是那个random函数吧，能够使得数组中每个数字的概率都是一样的，
Fisher–Yates shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle其实要做的就是初始化一个disjointSet，当做迷宫的cell，
然后我的做法是拿两个数组来存wall，一个存hWall，一个vWall，然后用shuffle函数打乱。
然后开始遍历这两个数组，数组这个wall两边的cell is same set，跳过，否则联通。

终于做到9了  还是这次就union（root）出了个错  得先find（root）再union。

我定义了一个wall类  里面存放着 wall的type和横纵坐标   然后再maze里面写一个wall数组  

part II
第一页有个前辈讲得挺好的 直接参考了 想了想怎么code 有点不知道肿么任意构造一个方向  继续加油

终于快要刷完61b啦！

很有意思的作业

hw9挺有意思的，发现了disjoint sets的概念可以这么应用。做的是06版的，感觉不那么简单啊，难点倒不是在disjoint sets部分，而是给wall和cell编序号，然后1维2维换来换去写起来有点麻烦。debug时把randomize之后的wall print出来，disjoint sets print出来，应该比较容易看出问题。
唉61b马上结束了，真是好课。

昨晚Hw9，再差一次Hw10就完咯~~~~
贴上Part II

1. 1. Mark all hWalls and vHalls as true (unbroken).
   
2. 2. Randomly choose a starting cell.
   
3. DFS:
   
4. 3. Mark this cell as visited.
   
5. 4. Randomly choose a direction, above, below, left, or right. Mark the wall
   
6.    as false (broken) and recursively perfrom DFS (step 3 and 4) on the cell
   
7.    across the wall.
   
8. 
   
9. (a) How would your algorithm ensure that there is a path between every pair of
   
10.     cells, but no more than one path between any pair of cells (i.e., no
    
11.     cycles)?
    
12.     Every wall represents an edge and initially it is false, meaning that every
    
13.     cell is connected, i.e., the graph is connected. Therefore, DFS is able to
    
14.     traverse the whole graph. By marking this cell as visited, there will not be
    
15.     a loop.
    
16. 
    
17. (b) How does your algorithm use random numbers to generate a different maze
    
18.     each time? Specifically, what decision should be made by random numbers
    
19.     at each recursive invocation of the depth-first search method?
    
20.     - Randomly choose a cell as the starting cell.
    
21.     - Randomly generate a number (direction) in step 4.

复制代码

第九次作业

Part I is not difficult. In order to represent the "Wall", I define a class "Wall", which contains x, y, and its type(boolean).

Part II is more interesting one. And I've realized the DFS-based implementation in Java.
              STEP 1: Initialize hWalls, vWalls to be true, meaning all walls are present.
              STEP 2: randomly choose the starting point, s.
              STEP 3: set the current point as visited.
              STEP 4: randomly call DFS on its unvisited neighbors.

The crux lies in STEP 4. And this is my realization: create a random permutation of the four directions(FROMLEFT, FROMRIGHT, FROMABOVE, FROMBELOW).  Loop through all directions, iff adjacent cells are not visited, and it will not go back to the previous cells. It is not hard to revise the given method depthFirstSearch() to meet our requirement.

Part2:
(1)如何保证每对cells直接都有一条通路，并且不形成环？
一开始把vWalls和hWalls的标志位设置成false，认为所有细胞都是联通的。
任意选择一个细胞，以他为中心，上下左右四个方向分别visit相邻的cell（排除来路的方向）。
如果相邻cell已经visited了，就在这里建一堵墙（wall的标志位设置为true）。

按这样所有方向遍历的原则，是可以每对细胞都有通路且不形成环的。

(2)如何用randInt控制每次的maze不同？
每次每个细胞不要按照 上下左右 的顺序遍历。
上下左右标记为1,2,3,4，有4!=24种排列方法，给每种排列方法做标记：
用randInt产生0-23之间的数代表这每一种排列。
然后就可以用这个数字控制遍历的顺序了。

做完了，每次读题都读特别久，写代码倒是写的不久.........