h*****3
发帖数: 1391 | 1 m x n integer array, 0 or 1, given a src and dest cell, find the number of
all paths from src to dst with all '0' cell visited once, the cell with
value '1' can not be visited.
you can move up, down, left, right
s 0 0
0 0 0
0 0 d |
k*p
发帖数: 1526 | 2 怎么看着像travelling salesman problem
NP-hard
【在 h*****3 的大作中提到】
: m x n integer array, 0 or 1, given a src and dest cell, find the number of
: all paths from src to dst with all '0' cell visited once, the cell with
: value '1' can not be visited.
: you can move up, down, left, right
: s 0 0
: 0 0 0
: 0 0 d
|
i**********e
发帖数: 1145 | 3 No this is not TSP.
Straightforward way is to use recursive depth-first traversal, but is
exponential in complexity.
It's the exact same problem as here:
http://www.quora.com/challenges
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
k*p
发帖数: 1526 | 4 how does DFS work? how to make sure each node only touched once?
【在 i**********e 的大作中提到】
: No this is not TSP.
: Straightforward way is to use recursive depth-first traversal, but is
: exponential in complexity.
: It's the exact same problem as here:
: http://www.quora.com/challenges
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
i**********e
发帖数: 1145 | 5 count the number of visited cells and compare with totalEmptyCells+1.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 k*p 的大作中提到】
: how does DFS work? how to make sure each node only touched once?
|
d*******l
发帖数: 338 | 6 这题似乎应该转化为图，然后找哈密顿路径。。。有低于指数复杂度的方法吗？要说有
什么特点，就是每个顶点的度最多是4，但这个也很难利用。 |
i**********e
发帖数: 1145 | 7 在 quora 网站他们说以下这情况可以优化到 5 秒内：
7 8
2 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
3 0 0 0 0 1 1
这题要优化貌似一点都不简单。
我能想到的是在某些情况能进行剪枝，但是要考虑多种复杂情况，而怎么把这些复杂情
况转换成代码，一点也不好写。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
d*******l
发帖数: 338 | 8 如果是求回路，那就和下面那个链接里的问题一样了：
http://www.docin.com/p-46797997.html
说不定里面的方法也能用到非回路的情况。
不过那可是偏难的竞赛题，插头dp什么的。面试的时候最多也就说个朴素方法。。 |
h*******0
发帖数: 68 | 9 I have a solution which takes about 50 seconds for the 8x7 matrix. The brute
force recursive DFS takes more than 200 minutes on the same machine. The C+
+ code is given below.
[root@cli-linux ~]# ./findPaths
Searching...
Total 301716 paths found in 53 seconds. |
i**********e
发帖数: 1145 | 10 先顶再看。
请问你是怎么想到的？
可以简单说说思路吗？
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
brute
C+
【在 h*******0 的大作中提到】
: I have a solution which takes about 50 seconds for the 8x7 matrix. The brute
: force recursive DFS takes more than 200 minutes on the same machine. The C+
: + code is given below.
: [root@cli-linux ~]# ./findPaths
: Searching...
: Total 301716 paths found in 53 seconds.
|
h*******0
发帖数: 68 | 11 思路主要是调试费时的DFS发现的。在递归DFS方法里，每发现一条新路经，我就打印当
前总路经数。我发现有时要花几分钟发现下一条新路经。 调试时，我发现在这几分钟
里，刚开始的几步把Matrix分成两部分了，例如
2 0 + 0 0 0 0
- 0 - 0 0 0 0
- - - 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
3 0 0 0 0 1 1
这种情况下，不可能发现一条合乎条件的路经了。 再递归那么多剩下的点就是浪费时
间。所以走到'+'位置时，应该立刻返回。这个处理把时间降为原来的差不多1/(100 -
150).
我又加了一个HashMap记录一些中间结果，不过这个改进对上面的性能影响不大。可能
只有1/(1-1.3). 加起来，总时间大概是递归DFS的1/(150-200).
【在 i**********e 的大作中提到】
: 先顶再看。
: 请问你是怎么想到的？
: 可以简单说说思路吗？
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: brute
: C+
|
