uc berkeley CS 61B homework 9

非常有意思的作业

union也有错误，盯着maze很快写好了却总是不对。。。

感觉到了后期作业难度在逐渐下降，这次的话如何随机的部分也被作业很详细地描述出来了，所以只剩下如何把hWalls和vWalls给放进一个array里，我用的方法是加一个walls class 三个files：boolean HorV（true for H and  false for V）, int x, int y，然后用array of walls即可。
另外关于part2：如何知道是否有cycle的方法其实已经被作业描述过了，开始把所有的cells设为false，每遍历一次就变为true，因为用的是dfs，所以如果是tree的话，每个cell只能遍历一次，遍历到一个是true的cell就是有cycle了，然后把walls的boolean转换一下就可以了；第二个问题如何每次random一个不一样的maze，也是用随机数呈现，即每次dfs的时候随机数生成上下左右的顺序，所以每次先遍历的点不一样，因而也就有了不同的maze。
最后上一下结果：

done hw9

做完了还是非常懵比。。。
照着说明 做出来了，但原理还不是特别懂

*******************************************************************************
* *     *       *       *         * * *   *             *       * *       *   *
* * * ********* ***** ***** * * *** * * ***** *** *** ******* *** *** *** *** *
*   * *         *     *     * * *   *     *   * * *   *         * *   * *     *
***** *** *** * ***** ***** *** *** * * *** *** * * * *** ***** * * *** * * ***
*   *   *   * *         * * *   *   * *   *     * * * *     * * *       * * * *
* ***** *** *** ********* * *** * ***** ***** ***** * * *** * *** * ***** *** *
*   *   * *   * * *       *   *     * *     *     * *   *         *     *     *
* ***** * * ***** * * *** * * * *** * *** ***** ******* * *** *** *********** *
*   * * *           * *   * * * * *         *     *   * * *     * *   * *     *
* *** * * ******* * *** ********* * ***** ***** *** * * ***** *** * *** * *****
*       *   *     * *       *     *     *           * * * *   * * *           *
***** * ******* ******* * *** ***** * * ***** ***** ***** *** * * ******* *****
*     * *   * *   * *   *   *   *   * *   *     *         *   * * * * *   *   *
* ******* * * * * * *** * *** * *** ********* * ************* * *** * ***** * *
* *     * * * * *     * *     * *       * * * *   *   *   *   *     * *     * *
* *** ***** * *** ***** * * * *** * *** * * * ***** *** ***** ***** * *** * ***
* * *   *           *   * * *     * *   *   * *           *         *     *   *
* * * * *** ********* * * *** *** * *** * ***** ***** ***** * * * * ***** *****
*     * * * *       * * * * * *   * *   *         *     * * * * * *     *     *
***** * * * ******* ***** * *************** * * ********* *** ********* * *****
* *   * * * *   * *     *       *           * * *         * * * *   *         *
* *** *** * * *** * * * * *************** ******* * ***** * *** *** * *********
*     * * *       * * * *   *     *         * *   *   *     *     *           *
*** * * * * ***** * ***** ******* ***** *** * *** ******* * *** * * * * * *** *
*   *       * * * *   *         *     * * *     *     *   *     *   * * * *   *
* ***** ***** * * * *** * *** *** ***** * *** * * ***************** ***** * * *
*   *   * * *   * *     *   * *         *     *     * *       *   * *   * * * *
* * *** * * * *** * * * ***** *** *** * *** *** * *** ***** *** * * * ***** ***
* * *     *       * * *   *   *     * *   * *   * *             *       *     *
*******************************************************************************
What a fine maze you've created!

在（2）的时候，counter w 已经减到1了，但是（3）的时候，我把控制条件还写成<w，搞得我多花一个小时才发现。。。。。ps. dfs那个method还没看。。等下看看他怎么写的 先贴图吧

我去，理解题目的意思花了半下午的时间，然后思考怎么把所有wall和所有cell分别放进一个array里，又花了一下午。。。真正理解了之后又在array的index那卡住了，一开始我用了walls[index] = i * 10 + j， 然后一直报错array index out of bound，debug了几个小时，后来发现我只考虑了横纵cell为一位数，如果上了10，我的方法就不行了。终于做出来… 自己学的还是不够好

关于用一个数组保存hWalls（h个元素）和vWalls（v个元素），建立一个h+v的int数组，先存入hWalls再存入vWalls。那么hWalls的index为0~h-1，依次用0,1,2,3,4...依次表示。同理，vWalls的index为h~v-1，用负数-1,-2,-3,-4...表示
在解码时，可以简单的取商，取余解码。
编码：
for(i = 0; i < horiz * (vert - 1); i++) {
            randomWalls[i] = i;
    }
    for(; i < horiz * (vert - 1) + vert * (horiz - 1); i++) {
            randomWalls[i] = -i + horiz * (vert - 1) - 1;
    }

解码：
    temp = randomWalls[i]
    wallIndexH =temp  / (vert - 1);
    wallIndexV = temp  % (vert - 1);  %hWalls, if(randomWalls[i] >= 0)



    temp = -randomWalls[i] - 1;
    wallIndexH = temp / vert;
    wallIndexV = temp % vert;  %vWalls, if(randomWalls[i] < 0)


关于PartII： 一种思路就是像首页讲得，先让所有wall = true，然后一个个拆墙；
也可以先让所有wall = false，然后发现一个circle就把那堵墙= true。个人感觉实现起来应该和第一种差不多