问一个我去年遇到的G家设计题# JobHunting - 待字闺中
w*y
1 楼
手机里一个maze里撞球的游戏－－－迷宫有一些挡板，横的／竖的，拨一下球就一直移
动到撞墙停下来：可以横着or竖着拨球让它移动。
设计用什么data structure， 用什么算法找 start 到exit的路径
动到撞墙停下来：可以横着or竖着拨球让它移动。
设计用什么data structure， 用什么算法找 start 到exit的路径
w*y
2 楼
我自己当时没有什么头绪， 不知道遇到这种问题要怎么处理啊
n*4
3 楼
这跟找迷宫解法有什么区别
挡板移动后还归位么
挡板移动后还归位么
w*y
4 楼
遇到挡板就停下来
我想最后跟迷宫解法是没区别的， 但是这个是设计提， 最主要的是用什么样的class/
structure去组织。 当时面试官花了很多时间问我，想要用什么去表示这个迷宫－－－
传统的就是一个array； 剩下的就是用到哪些method什么的，譬如移动一下到什么位
置怎么实现之类的
【在 n**4 的大作中提到】
: 这跟找迷宫解法有什么区别
: 挡板移动后还归位么
我想最后跟迷宫解法是没区别的， 但是这个是设计提， 最主要的是用什么样的class/
structure去组织。 当时面试官花了很多时间问我，想要用什么去表示这个迷宫－－－
传统的就是一个array； 剩下的就是用到哪些method什么的，譬如移动一下到什么位
置怎么实现之类的
【在 n**4 的大作中提到】
: 这跟找迷宫解法有什么区别
: 挡板移动后还归位么
w*y
5 楼
偷偷来update一下这个题的答案
说是迷宫可以转化成一个graph －－－大意是每个挡板都可以转化成node（大家可以去
看这个就了解迷宫长什么样了 http://www.freeaddictinggames.com/static/thumbs/868.jpg）， 我还没具体想转化的方法，不过感觉就是一些rules吧。 可以移动的位置之间，对应node间的edge。
有了graph， 就是找node间是不是存在一个path了。
说是迷宫可以转化成一个graph －－－大意是每个挡板都可以转化成node（大家可以去
看这个就了解迷宫长什么样了 http://www.freeaddictinggames.com/static/thumbs/868.jpg）， 我还没具体想转化的方法，不过感觉就是一些rules吧。 可以移动的位置之间，对应node间的edge。
有了graph， 就是找node间是不是存在一个path了。
x*w
6 楼
用个matrix不就行了吗？
【在 w***y 的大作中提到】
: 偷偷来update一下这个题的答案
: 说是迷宫可以转化成一个graph －－－大意是每个挡板都可以转化成node（大家可以去
: 看这个就了解迷宫长什么样了 http://www.freeaddictinggames.com/static/thumbs/868.jpg）， 我还没具体想转化的方法，不过感觉就是一些rules吧。 可以移动的位置之间，对应node间的edge。
: 有了graph， 就是找node间是不是存在一个path了。
w*y
7 楼
我想跟这个game的规则有关系。
matrix有一个问题是， 任何一个位置(i,j)都是可以四个方向移动的
但是这个game是拨一下，就一直移动到挡板的位置。 所以如果用matrix，在移动的时
候就比较复杂。 如果把graph建好了，后面就很直接。
【在 x*********w 的大作中提到】
:
: 用个matrix不就行了吗？
matrix有一个问题是， 任何一个位置(i,j)都是可以四个方向移动的
但是这个game是拨一下，就一直移动到挡板的位置。 所以如果用matrix，在移动的时
候就比较复杂。 如果把graph建好了，后面就很直接。
【在 x*********w 的大作中提到】
:
: 用个matrix不就行了吗？
l*n
8 楼
把matrix看成graph是很多题目的解决思路。
g*e
9 楼
matrix里的cube 即可表示path 也可表示wall 也可表示挡板
不就得了
不就得了
z*3
10 楼
matrix
这个应该是做过游戏的地图比较熟悉
这个应该是做过游戏的地图比较熟悉
w*y
11 楼
能不能展开说说？ 我没做过游戏， 不知道如果用matrix表示， 移动的时候怎么处
理比较好
当时我就试图用matrix做，不过最后也没有整明白找path的算法hehe
【在 z*******3 的大作中提到】
: matrix
: 这个应该是做过游戏的地图比较熟悉
理比较好
当时我就试图用matrix做，不过最后也没有整明白找path的算法hehe
【在 z*******3 的大作中提到】
: matrix
: 这个应该是做过游戏的地图比较熟悉
s*n
12 楼
怎么可能用graph.
matrix表示地图。
一个格子可以是空地，可以是墙，可以是挡板。
球：有5个移动方向。
定时器，控制球的移动，如果球有方向就每个tick移动一格。
input:挡板，可以改变球的方向。
【在 w***y 的大作中提到】
: 偷偷来update一下这个题的答案
: 说是迷宫可以转化成一个graph －－－大意是每个挡板都可以转化成node（大家可以去
: 看这个就了解迷宫长什么样了 http://www.freeaddictinggames.com/static/thumbs/868.jpg）， 我还没具体想转化的方法，不过感觉就是一些rules吧。 可以移动的位置之间，对应node间的edge。
: 有了graph， 就是找node间是不是存在一个path了。
matrix表示地图。
一个格子可以是空地，可以是墙，可以是挡板。
球：有5个移动方向。
定时器，控制球的移动，如果球有方向就每个tick移动一格。
input:挡板，可以改变球的方向。
【在 w***y 的大作中提到】
: 偷偷来update一下这个题的答案
: 说是迷宫可以转化成一个graph －－－大意是每个挡板都可以转化成node（大家可以去
: 看这个就了解迷宫长什么样了 http://www.freeaddictinggames.com/static/thumbs/868.jpg）， 我还没具体想转化的方法，不过感觉就是一些rules吧。 可以移动的位置之间，对应node间的edge。
: 有了graph， 就是找node间是不是存在一个path了。
s*n
13 楼
找到path的算法用flooding,这是topcoder 上面直接给解答的问题。
【在 w***y 的大作中提到】
: 能不能展开说说？ 我没做过游戏， 不知道如果用matrix表示， 移动的时候怎么处
: 理比较好
: 当时我就试图用matrix做，不过最后也没有整明白找path的算法hehe
【在 w***y 的大作中提到】
: 能不能展开说说？ 我没做过游戏， 不知道如果用matrix表示， 移动的时候怎么处
: 理比较好
: 当时我就试图用matrix做，不过最后也没有整明白找path的算法hehe
相关阅读
问一个问题，关于保险Amazon里全是MS loser？ (转载)今天被加州某公司戏弄了一下面试题：GetNumber and ReleaseNumber参加 其他 学校的 career fair有问题吗？ONSITE回来后两周，收到HM回复。看不懂。。。求解释版上有没有statistical consultant要是公司给办h1，还需要办opt吗？寻找北卡地区CS相关volunteer jobH1b被layoff，急问各位转身份的问题 (转载)急求！！！关于微软的面试机会招聘公司会不会将一个位置分给几个猎头公司去竞争？最近股市低迷对找工形势有影响吗？问个google面试题有人知道automomy这个公司么7月申OPT的，有人还没收到吗？NSC一个电面100%挂了Amazon第二轮电面不能自己定时间么？~Irvine software engineer salary 80K 怎么样?72k in Chicago vs 92k in LA