steam clean - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Living

steam clean

steam clean# Living

h*b2010-10-19 07:10

1 楼

一个amazon的算法题描述如下（在以前的面经里面看到的）：
boggle游戏的问题：给定一个4*4的矩阵，每个
位置有一个字母，可以从一个位置跳转到周围八个相邻位置中的任何一个，但不能跳到
已经访问过的位置，要求找出所有的单词（假设给定了一个词典）。
这个题目感觉下code的话很难写的啊？如何用DFS或者递归的话如何避免访问重发的
元素了或者避免Loop. 还有的话用用DFS的如何构造图呢？感觉DFS找一个valid word
比较容易，找出所有的words 感觉太复杂了。大家有什么简洁的算法？。谢谢了。。

A*A2010-10-19 07:10

2 楼

房子马上要close了，master suite是地毯，然后地下室是地毯，其他地方都是砖和木
地板的。本来准备换master的地毯的，seller跟我说他们这个地毯是wool的，看着是
很不错，我想等段时间要换也换木地板（目前没米）。准备steam clean一下，但是不
知道是请人来clean还是自己买机器。如请人来，有什么推荐的吗？如果买，那个牌子
好呀？
多谢！～

g*y2010-10-19 07:10

3 楼

递归和DFS没什么关系

word

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

: 一个amazon的算法题描述如下（在以前的面经里面看到的）：
: boggle游戏的问题：给定一个4*4的矩阵，每个
: 位置有一个字母，可以从一个位置跳转到周围八个相邻位置中的任何一个，但不能跳到
: 已经访问过的位置，要求找出所有的单词（假设给定了一个词典）。
: 这个题目感觉下code的话很难写的啊？如何用DFS或者递归的话如何避免访问重发的
: 元素了或者避免Loop. 还有的话用用DFS的如何构造图呢？感觉DFS找一个valid word
: 比较容易，找出所有的words 感觉太复杂了。大家有什么简洁的算法？。谢谢了。。

C*d2010-10-19 07:10

4 楼

Hoover SteamVac

R*i2010-10-19 07:10

5 楼

My solution:
prefix tree to store all words in dictionary
for each cell in matrix
do BFS
add to BFS queue only if partial_word can be found in prefix tree and
unvisited
O(n^2) solution, may not be optimal, but guarantee to work.

p*b2010-10-19 07:10

6 楼

I think you can also rent one from grocery store or HD.

g*k2010-10-19 07:10

7 楼

个人感觉这就是纯递归的算法题

word

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

k*t2010-10-19 07:10

8 楼

rug doctor is the way to go

【在 A*A 的大作中提到】

: 房子马上要close了，master suite是地毯，然后地下室是地毯，其他地方都是砖和木
: 地板的。本来准备换master的地毯的，seller跟我说他们这个地毯是wool的，看着是
: 很不错，我想等段时间要换也换木地板（目前没米）。准备steam clean一下，但是不
: 知道是请人来clean还是自己买机器。如请人来，有什么推荐的吗？如果买，那个牌子
: 好呀？
: 多谢！～

b*n2010-10-19 07:10

9 楼

#define N 4
void FindWordsBoggle(char board[][N])
{
int i=0,j=0;
char* outStr = (char*) malloc((N*N+1)*sizeof(char));
int* occupMap = (int*) calloc((N*N),sizeof(int));
int level = 0;
RecursiveBoggle(board, outStr, level, occupMap);
free(occupMap);
free(outStr);
}
void RecursiveBoggle(char board[][N], char* outStr, int level, int*
occupMap)
{
int* occupMapCopy = (int*) malloc((N*N)*sizeof(int));
memcpy(occupMapCopy, occupMap, N*N*sizeof(int));
int i=0,j=0;
for ( ; i < N; i++)
{
for (; j < N; j++)
{
if (!occupMapCopy[i*N+j])
{
outStr[level] = board[i][j];
outStr[level+1] = '\0';
/*Find whether the current string is available as a word.*/
if (FindInDictionary(outStr))
printf("%s\n",outStr);
if (FindPrefixInDictionary(outStr))
{
occupMapCopy[i*N+j] = 2;
/*Label neighbors as traversable*/
LabelNeighbors(occupMapCopy, i, j);
RecursiveBoggle(board, outStr, level+1, occupMapCopy);
}
}
}
}
free(occupMapCopy);
}
void LabelNeighbors(int* occupMap, int i, int j)
{
int ii=0,jj=0;
for (; ii < N; ++ii)
{
for (; jj < N; ++jj)
{
if (occupMap[ii*N+jj] == 2)
/*already used*/
continue;
else if ( abs(ii-i) <=1 && abs(jj-j) <=1 )
/*can be next character*/
occupMap[ii*N+jj] = 0;
else occupMap[ii*N+jj] = 1; /*not reachable*/
}
}
}