J*****v
发帖数: 314 | 1 给你一个老版手机的按键，只有0-9，注意老实手机0在最下面。参数是n，从1的位子开
始，
用走国际象棋的马的方法拨电话。n是第n步 有几种可能性。比如： n = 2 结果是2. n
= 3
结果是7. n = 4 结果是11. n = 5 结果是16.
怎么用dfs才能知道第n步有几种可能？ | r******7
发帖数: 13 | 2 抄的一亩三分地的例子吧^^，原文数字是错的。简单递归就可以了。
n
【在 J*****v 的大作中提到】
: 给你一个老版手机的按键，只有0-9，注意老实手机0在最下面。参数是n，从1的位子开
: 始，
: 用走国际象棋的马的方法拨电话。n是第n步 有几种可能性。比如： n = 2 结果是2. n
: = 3
: 结果是7. n = 4 结果是11. n = 5 结果是16.
: 怎么用dfs才能知道第n步有几种可能？
| e***l
发帖数: 3 | 3 弄个64x64的矩阵A，其中i,j为1的点是马可以从i跳到j
N步，算出A_n = A ^ N，这个乘法可以在log(N)级别个乘法完成。
最后答案就是 A_n(i0，j0),i0,j0是问题中的位置 |
|
