请教G家onsite一道题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教G家onsite一道题

请教G家onsite一道题# JobHunting - 待字闺中

z*n2012-11-15 08:11

1 楼

一个矩阵，比如m*n
从一个点可以访问它的八个相邻点（上、下、左、右、左上、左下、右上、右下）
如果一个方向上的点已经被访问过了，则可以继续访问这个方向上的下一个未被访问的
点（比如当前点是(5,5)，如果（5,4）已经被访问，则可以访问(5,3)，如果(5,3)也被
访问了，则可以访问（5,2）…… 对角线方向的也是如此,(5,5)可以访问(4,4)，如果(
4,4)已经被访问，可以访问(3,3)……）
现在需要遍历这个矩阵上的所有点，则有多少种可能性？（起点和终点不限）

h*n2012-11-15 08:11

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*e2012-11-15 08:11

3 楼

前面有人问过，好像只要求数量级。

果(

【在 z*********n 的大作中提到】

p*22012-11-15 08:11

4 楼

这题复杂度很大呀。

e*e2012-11-15 08:11

5 楼

8 to the power of m*n: 8^(m*n)

z*n2012-11-15 08:11

6 楼

dfs开销的确会很大
面试官提示的是dp可以做，不过我仍然没想出来。。。

【在 h****n 的大作中提到】

: dfs 访问标记 counter
: 不过递归总归开销太大不知道有没有直观的dp解法
:
: 一个矩阵，比如m*n从一个点可以访问它的八个相邻点（上、下、左、右、左上、左下
: 、右上、右下）如果一个方向上的点已经被访问过了，则可以继续访问这个方向上的下
: 一个未被访问的点（比如........
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56

z*n2012-11-15 08:11

7 楼

不知道您是否还有印象是什么时候的帖子，多谢
我面试的时候面试官说的是求总数，没说是数量级

【在 f*****e 的大作中提到】

: 前面有人问过，好像只要求数量级。
:
: 果(