m**********2
发帖数: 6 | 1 上周面亚麻，一个犹太人，上来先是一道常规OOD，还没讲完就被打断，说时间有限，
下一道。
然后是道coding的题目。这道题目看似简单，但是感觉有不少边界条件要考虑。
题目如下：
安卓手机解锁画面，给定任意一个解锁图形，不知道起始点，输出所有可能的path。
本能的觉得应该用DFS遍历，但是花了很多时间思考何时应该backtrack返回。估计这题
应该是挂了。
有没有大神能给点思路啊 |
r*g
发帖数: 186 | 2
不是标记当前可走的, 没有了就返回吗?
还是我题意理解错了
【在 m**********2 的大作中提到】
: 上周面亚麻，一个犹太人，上来先是一道常规OOD，还没讲完就被打断，说时间有限，
: 下一道。
: 然后是道coding的题目。这道题目看似简单，但是感觉有不少边界条件要考虑。
: 题目如下：
: 安卓手机解锁画面，给定任意一个解锁图形，不知道起始点，输出所有可能的path。
: 本能的觉得应该用DFS遍历，但是花了很多时间思考何时应该backtrack返回。估计这题
: 应该是挂了。
: 有没有大神能给点思路啊
|
e*******7
发帖数: 347 | |
x********u
发帖数: 1150 | |
m**********2
发帖数: 6 | 5 其实应该是这样一个思路，标记当前可走的，如果没有就返回，但是这样并不能保证图
形是match的，因为起点可以是任意一个点，需要找个方法判断所有的边都被访问过了
。默认是undirected graph。一直到现在都没什么思路。LC上貌似graph的题不多啊。
【在 r*g 的大作中提到】
:
: 不是标记当前可走的, 没有了就返回吗?
: 还是我题意理解错了
|
y*******3
发帖数: 158 | 6 给定任意一个解锁图形，不知道起始点，输出所有可能的path。
感觉没太懂什么意思…………
如果我没理解错的话，以及以安卓解锁图案必需一笔画为前提
之前网上有过一个破解安卓开机手势的教程，方法就是9个点标号0-8，所有组合跑一边。
0 1 2
3 4 5
6 7 8
所以：
1）如果图形是闭合的，比如 0367840 这种，那就每个点都作为起点输出一个path
2）如果图形不闭合，正向反向各一种，就两种。
但隐隐感觉自己这种方法哪里不对…………就当抛砖引玉吧………… |
n******n
发帖数: 12088 | 7 欧拉回路？
【在 m**********2 的大作中提到】
: 上周面亚麻，一个犹太人，上来先是一道常规OOD，还没讲完就被打断，说时间有限，
: 下一道。
: 然后是道coding的题目。这道题目看似简单，但是感觉有不少边界条件要考虑。
: 题目如下：
: 安卓手机解锁画面，给定任意一个解锁图形，不知道起始点，输出所有可能的path。
: 本能的觉得应该用DFS遍历，但是花了很多时间思考何时应该backtrack返回。估计这题
: 应该是挂了。
: 有没有大神能给点思路啊
|
