w***y
发帖数: 6251 | 1 手机里一个maze里撞球的游戏－－－迷宫有一些挡板，横的／竖的，拨一下球就一直移
动到撞墙停下来：可以横着or竖着拨球让它移动。
设计用什么data structure， 用什么算法找 start 到exit的路径 |
w***y
发帖数: 6251 | 2 我自己当时没有什么头绪， 不知道遇到这种问题要怎么处理啊 |
n**4
发帖数: 719 | |
w***y
发帖数: 6251 | 4 遇到挡板就停下来
我想最后跟迷宫解法是没区别的， 但是这个是设计提， 最主要的是用什么样的class/
structure去组织。 当时面试官花了很多时间问我，想要用什么去表示这个迷宫－－－
传统的就是一个array； 剩下的就是用到哪些method什么的，譬如移动一下到什么位
置怎么实现之类的
【在 n**4 的大作中提到】
: 这跟找迷宫解法有什么区别
: 挡板移动后还归位么
|
w***y
发帖数: 6251 | 5 偷偷来update一下这个题的答案
说是迷宫可以转化成一个graph －－－大意是每个挡板都可以转化成node（大家可以去
看这个就了解迷宫长什么样了 http://www.freeaddictinggames.com/static/thumbs/868.jpg）， 我还没具体想转化的方法，不过感觉就是一些rules吧。 可以移动的位置之间，对应node间的edge。
有了graph， 就是找node间是不是存在一个path了。 |
x*********w
发帖数: 533 | 6
用个matrix不就行了吗？
【在 w***y 的大作中提到】
: 偷偷来update一下这个题的答案
: 说是迷宫可以转化成一个graph －－－大意是每个挡板都可以转化成node（大家可以去
: 看这个就了解迷宫长什么样了 http://www.freeaddictinggames.com/static/thumbs/868.jpg）， 我还没具体想转化的方法，不过感觉就是一些rules吧。 可以移动的位置之间，对应node间的edge。
: 有了graph， 就是找node间是不是存在一个path了。
|
w***y
发帖数: 6251 | 7 我想跟这个game的规则有关系。
matrix有一个问题是， 任何一个位置(i,j)都是可以四个方向移动的
但是这个game是拨一下，就一直移动到挡板的位置。 所以如果用matrix，在移动的时
候就比较复杂。 如果把graph建好了，后面就很直接。
【在 x*********w 的大作中提到】
:
: 用个matrix不就行了吗？
|
l*n
发帖数: 529 | 8 把matrix看成graph是很多题目的解决思路。 |
g*********e
发帖数: 14401 | 9 matrix里的cube 即可表示path 也可表示wall 也可表示挡板
不就得了 |
z*******3
发帖数: 13709 | 10 matrix
这个应该是做过游戏的地图比较熟悉 |
w***y
发帖数: 6251 | 11 能不能展开说说？ 我没做过游戏， 不知道如果用matrix表示， 移动的时候怎么处
理比较好
当时我就试图用matrix做，不过最后也没有整明白找path的算法hehe
【在 z*******3 的大作中提到】
: matrix
: 这个应该是做过游戏的地图比较熟悉
|
s*****n
发帖数: 5488 | 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了。
|
s*****n
发帖数: 5488 | 13 找到path的算法用flooding,这是topcoder 上面直接给解答的问题。
【在 w***y 的大作中提到】
: 能不能展开说说？ 我没做过游戏， 不知道如果用matrix表示， 移动的时候怎么处
: 理比较好
: 当时我就试图用matrix做，不过最后也没有整明白找path的算法hehe
|
