一亩三分地

 找回密码 注册账号

扫描二维码登录本站

微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
楼主: 逃亡~
收起左侧

uc berkeley CS 61B homework 9

  [复制链接] |只看干货 |入门|算法|数据结构, 公开课
我的人缘0
vincentli1 2018-4-12 13:58:37 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (48)
 
 
4% (2)    👎

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

回复

使用道具 举报

我的人缘0

升级   69.71%

tobeno1 2018-5-13 09:54:43 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (24)
 
 
0% (0)    👎
这个作业练习了两个地方,DisjointSet的用法,random的用法(implement很简单但很好用)。知识点了解清楚之后写代码真的快很多。



回复

使用道具 举报

我的人缘0

升级   61.71%

nyjahchill 2018-6-12 00:55:17 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (76)
 
 
3% (3)    👎

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

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
回复

使用道具 举报

我的人缘0

升级   0.43%

ff12 2018-6-20 15:29:52 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (104)
 
 
1% (2)    👎
读懂作业花了好久。。。写代码还比较顺利。使用了二维数组来存放walls, walls[][0]=i, walls[][1]=j,walls[][2]表示h or v

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
回复

使用道具 举报

我的人缘0

升级   53.29%

shendezhuti 2019-5-25 13:32:40 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (32)
 
 
3% (1)    👎
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+1; 对于Vwall我们用负数赋值 即
int vindex=0;
    for( i=numberOfHWall;i<numberOfHWall+numberOfVWall;i++){
      walls=-vindex;
      vindex=vindex+1;
    }   
之后我们将walls数组中的wall中排序打乱,打乱的方法可以参见readme,还是比较简单的。

(3)这个地方比较关键的是怎么将我们之前赋予的值转换成格子坐标,其实很简单!我们每次令w=wall,如果发现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 前面有同学回复的很好了,膜拜一下!!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
回复

使用道具 举报

我的人缘0

升级   10%

lesliere 2019-7-7 18:29:05 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   88% (15)
 
 
11% (2)    👎
交作业,也是读题花了很久,一开始没明白把vertical和horizontal walls放在array里是要干嘛,甚至还纠结用3d的array,后来意识到就是坐标和array的转换问题,难点主要在这里。我是先排horizontal的,后来再排vertical的,放进去的数字都是从0开始,只是vertical的为负数。最后实现还是很快。。。
感觉我进度太慢了,从开始cs61b到现在快5个月了= =

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
回复

使用道具 举报

我的人缘0

升级   86.67%

Alansong641 2020-2-12 18:50:39 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
附上截图:
主要思想是如何利用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

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
回复

使用道具 举报

我的人缘0

升级   64.5%

aaronchenthu 2020-10-20 19:47:53 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
好有趣的题目,终于要学完cs61b了!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

快速回复 返回顶部 返回列表