z*********n
发帖数: 5 | 1 一个矩阵，比如m*n
从一个点可以访问它的八个相邻点（上、下、左、右、左上、左下、右上、右下）
如果一个方向上的点已经被访问过了，则可以继续访问这个方向上的下一个未被访问的
点（比如当前点是(5,5)，如果（5,4）已经被访问，则可以访问(5,3)，如果(5,3)也被
访问了，则可以访问（5,2）…… 对角线方向的也是如此,(5,5)可以访问(4,4)，如果(
4,4)已经被访问，可以访问(3,3)……）
现在需要遍历这个矩阵上的所有点，则有多少种可能性？（起点和终点不限） | h****n
发帖数: 1093 | 2 dfs 访问标记 counter
不过递归总归开销太大 不知道有没有直观的dp解法
一个矩阵，比如m*n从一个点可以访问它的八个相邻点（上、下、左、右、左上、左下
、右上、右下）如果一个方向上的点已经被访问过了，则可以继续访问这个方向上的下
一个未被访问的点（比如........
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 z*********n 的大作中提到】
: 一个矩阵，比如m*n
: 从一个点可以访问它的八个相邻点（上、下、左、右、左上、左下、右上、右下）
: 如果一个方向上的点已经被访问过了，则可以继续访问这个方向上的下一个未被访问的
: 点（比如当前点是(5,5)，如果（5,4）已经被访问，则可以访问(5,3)，如果(5,3)也被
: 访问了，则可以访问（5,2）…… 对角线方向的也是如此,(5,5)可以访问(4,4)，如果(
: 4,4)已经被访问，可以访问(3,3)……）
: 现在需要遍历这个矩阵上的所有点，则有多少种可能性？（起点和终点不限）
| f*****e
发帖数: 2992 | 3 前面有人问过，好像只要求数量级。
果(
【在 z*********n 的大作中提到】
: 一个矩阵，比如m*n
: 从一个点可以访问它的八个相邻点（上、下、左、右、左上、左下、右上、右下）
: 如果一个方向上的点已经被访问过了，则可以继续访问这个方向上的下一个未被访问的
: 点（比如当前点是(5,5)，如果（5,4）已经被访问，则可以访问(5,3)，如果(5,3)也被
: 访问了，则可以访问（5,2）…… 对角线方向的也是如此,(5,5)可以访问(4,4)，如果(
: 4,4)已经被访问，可以访问(3,3)……）
: 现在需要遍历这个矩阵上的所有点，则有多少种可能性？（起点和终点不限）
| p*****2
发帖数: 21240 | | e****e
发帖数: 418 | 5 8 to the power of m*n: 8^(m*n) | z*********n
发帖数: 5 | 6 dfs开销的确会很大
面试官提示的是dp可以做，不过我仍然没想出来。。。
【在 h****n 的大作中提到】
: dfs 访问标记 counter
: 不过递归总归开销太大 不知道有没有直观的dp解法
:
: 一个矩阵，比如m*n从一个点可以访问它的八个相邻点（上、下、左、右、左上、左下
: 、右上、右下）如果一个方向上的点已经被访问过了，则可以继续访问这个方向上的下
: 一个未被访问的点（比如........
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
| z*********n
发帖数: 5 | 7 不知道您是否还有印象是什么时候的帖子，多谢
我面试的时候面试官说的是求总数，没说是数量级
【在 f*****e 的大作中提到】
: 前面有人问过，好像只要求数量级。
:
: 果(
| b*****u
发帖数: 648 | 8 8个方向确实麻烦，leetcode上有个两个方向的dp题 | z*********n
发帖数: 5 | 9 两个方向上的应该是经典题了
这个题不仅8个方向，而且初始点和终止点都不定
【在 b*****u 的大作中提到】
: 8个方向确实麻烦，leetcode上有个两个方向的dp题
| g*******r
发帖数: 44 | 10 你能说的更清楚点吗？当前点是(5,5)，如果（5,4）已经被访问，则可以访问(5,3)，
那我们能从(5,4)访问(4,4)吗？ | z*********n
发帖数: 5 | 11 5,5可以直接访问4,4，这俩是相邻点（一个点有八个相邻点）
如果5,4已经被访问过，可以从5,5穿过5,4访问5,3
但是不可以从5,5穿过5,4访问4,3，就是必须在同一个方向上
，
【在 g*******r 的大作中提到】
: 你能说的更清楚点吗？当前点是(5,5)，如果（5,4）已经被访问，则可以访问(5,3)，
: 那我们能从(5,4)访问(4,4)吗？
|
|
