U*******L 发帖数: 94 | 1 4x4的矩阵,左上走到右下,可以走上下左右四个方向,不能走走过的格子,多少种
unique的走法?
bfs+去重复太麻烦,有更简单的想法/解法吗 |
A**u 发帖数: 2458 | 2 backtrack方法
注意优化,去掉不可能的path
我也是比照 这个题目的 比如 递增整数, a1,a2,a3,...,an
求所有组合,使得 它的和=target.
这个就用backtrack
两个题目思路一样。
另外的办法,就是推公式了,不过不显然
【在 U*******L 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 4x4的矩阵,左上走到右下,可以走上下左右四个方向,不能走走过的格子,多少种 : unique的走法? : bfs+去重复太麻烦,有更简单的想法/解法吗
|
H****r 发帖数: 2801 | 3 C(6,3)?
【在 U*******L 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 4x4的矩阵,左上走到右下,可以走上下左右四个方向,不能走走过的格子,多少种 : unique的走法? : bfs+去重复太麻烦,有更简单的想法/解法吗
|
U*******L 发帖数: 94 | 4 这个回溯和BFS没什么区别吧?而且一样要去重复
【在 A**u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : backtrack方法 : 注意优化,去掉不可能的path : 我也是比照 这个题目的 比如 递增整数, a1,a2,a3,...,an : 求所有组合,使得 它的和=target. : 这个就用backtrack : 两个题目思路一样。 : 另外的办法,就是推公式了,不过不显然
|
U*******L 发帖数: 94 | 5 能走4个方向,所以肯定不是这个结果了
【在 H****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : C(6,3)?
|
U*******L 发帖数: 94 | 6 Nevermind,写出来了,就是一个小递归,以前想复杂了 |
A**u 发帖数: 2458 | 7 不用去重复
递归就可以了。
不过有些路径不可能,你就不要再递归了
【在 U*******L 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个回溯和BFS没什么区别吧?而且一样要去重复
|
H****r 发帖数: 2801 | 8 嗯,偶想简单了,这个估计得实际搜路径了...
【在 U*******L 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能走4个方向,所以肯定不是这个结果了
|
d*s 发帖数: 699 | 9 花了40多分钟写出来了,这个题一般面试给多长时间?
【在 U*******L 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 4x4的矩阵,左上走到右下,可以走上下左右四个方向,不能走走过的格子,多少种 : unique的走法? : bfs+去重复太麻烦,有更简单的想法/解法吗
|