uc berkeley CS 61B homework 9

交作业交作业。
按理说不难，但我还是在每个墙怎么表示和每个房间怎么表示卡了很久。我真是太菜了。

这个作业练习了两个地方，DisjointSet的用法，random的用法（implement很简单但很好用）。知识点了解清楚之后写代码真的快很多。

hw9打个卡

大家都说简单，我写了可能2个小时，但是debug花的时间巨久，快崩溃了，确实找不到错误。
在用一维数组存储h和v不同两个坐标系时，我先采用的时顺序先h后v按从0-(h*v-1)的方法，这样存储可以，在后来重新从一维回到二维坐标时也没问题，不过在使用find()时经常会stackoverflow，很偶尔的情况下坐标还会越界，判断了很久没有判断出来问题，因为我在debug时观察了hWalls和vWalls的两个坐标应该都没问题，
根据他们计算出来的root1,root2也对，但是find()就会经常卡住，郁闷。。
后来借鉴了其它方法，在存储过程中用正负表示h和v才解决这个问题。

读懂作业花了好久。。。写代码还比较顺利。使用了二维数组来存放walls, walls[][0]=i, walls[][1]=j,walls[][2]表示h or v

hw9前面读题就读了好久啊！！partI 要我们写code,关键就是参考readme.pdf中的(1)(2)(3)提示步骤

其中(1)我们要new 一个 DisjointSets的对象，numelements应该是我们所有的格子数，因此是horiz*vert；

       (2) 这个部分我感觉是比较让我头大的，我一开始一直没弄明白为什么要有这个步骤，后来才明白(2)是给(3)做准备工作，主要的工作就是将所有的wall放到一个int数组里面（就是说用int将wall表示）具体怎么放可以由我们自己设计，但是之后需要通过我们自己弄明白怎么将每个wall对应的index转为对应的cell。我参考了网上别的思路，具体是：对于Hwall我们就用i+1赋予。
，即walls[i]=i+1; 对于Vwall我们用负数赋值 即
int vindex=0;
    for( i=numberOfHWall;i<numberOfHWall+numberOfVWall;i++){
      walls[i]=-vindex;
      vindex=vindex+1;
    }   
之后我们将walls数组中的wall中排序打乱，打乱的方法可以参见readme，还是比较简单的。

(3)这个地方比较关键的是怎么将我们之前赋予的值转换成格子坐标，其实很简单！我们每次令w=wall[i]，如果发现w大于0，说明是Hwall，我们需要判断这个横墙的上下两个格子是否是同一个root，不是的话则union！同理如果w小于0，说明是Vwall，需要判断竖墙的左右格子是否是同一个root，不是则union。那么如何判断上下以及左右格子的坐标呢？
我们利用数学转换公式，当w大于0时
          int topX=(w-1)/(vert-1);
          int topY=(w-1)%(vert-1);
          int downX=topX;
          int downY=topY+1;
          int topCell = topX + topY * horiz;
          int downCell = downX + downY * horiz;
当w小于0时
          int leftX=(-w)%(horiz-1);
          int leftY=(-w)/(horiz-1);
          int rightX=leftX+1;
          int rightY=leftY;
          int leftCell = leftX + leftY * horiz;
          int rightCell = rightX + rightY * horiz;

partII 前面有同学回复的很好了，膜拜一下！！

交作业，也是读题花了很久，一开始没明白把vertical和horizontal walls放在array里是要干嘛，甚至还纠结用3d的array，后来意识到就是坐标和array的转换问题，难点主要在这里。我是先排horizontal的，后来再排vertical的，放进去的数字都是从0开始，只是vertical的为负数。最后实现还是很快。。。
感觉我进度太慢了，从开始cs61b到现在快5个月了= =

附上截图：
主要思想是如何利用Disjoint Set来进行应用，在这里，各个wall都是独立的item，且没有重复。所以满足并查集的要求。

1、将编好号的wall进行随机排列
2、随机地取某一个wall（vertical或者horizontal），这个wall同时表示了它上方（horiz）或左方（vert）的cell。如果两边（左右）或者上下的cell的parent不是同一个的话，说明它们不属于同一个disjointset，即没有通路，将这个wall设为false。
3、最后用DFS来看是否是一个valid 的maze。事实上走maze的过程就是DFS的过程。

注意的是wall编号的时候，如何表达不同种类的wall（竖着还是横着）用正负表示，以及如何将编号后的wall转换为它的位置（用取余和整除），见code

好有趣的题目，终于要学完cs61b了！