1

这是我第一次使用递归来做除了找到数字的阶乘之外的事情。我正在构建一个程序来在拼图板上查找单词。以下是导致段错误的函数：

void findWord(vector<string>& board, set<string>& dictionary,
          string prefix, int row, int column){
  prefix += getTile(board, row, column);
  if(prefix.length() > biggestWordLength)
    return;
  if(isOutOfBounds(row, column))
    return;
  if(isWord(prefix, dictionary) == 1)
    foundWords.insert(prefix);
  if(isWord(prefix, dictionary) == 0)
    return;
  //Note: this does not prevent using the same tile twice in a word
  findWord(board, dictionary, prefix, row-1, column-1);
  findWord(board, dictionary, prefix, row-1, column);
  findWord(board, dictionary, prefix, row-1, column+1);
  findWord(board, dictionary, prefix, row, column-1);
  findWord(board, dictionary, prefix, row, column+1);
  findWord(board, dictionary, prefix, row+1, column-1);
  findWord(board, dictionary, prefix, row+1, column);
  findWord(board, dictionary, prefix, row+1, column+1);
}
4

1 回答 1

3

在所有情况下，您都在向各个方向递归。考虑这个简化的递归版本：

void findword(... int x, int y, ...) {
   ...
   findword(... x, y+1, ...);
   findword(... x, y-1, ...);
   ...
}

现在考虑何时需要x == 5和y == 5（例如，任何其他位置都一样好）。我在下面使用缩​​进来表示嵌套调用：

findword(... 5, 5, ...)
   findword(..., 5, 6, ...)    // x, y+1
      ...
   findword(..., 5, 5, ...)    // x, y-1
      // ouch! this is just the same as before, so it will eventually:
      findword(..., 5, 6, ...)
      findword(..., 5, 5, ...)
          // ouch!... here again! shall I continue?

现在，考虑一下算法。查找单词时，首先选择第一个字符，然后选择一个方向，然后按该方向测试有多少个字母可以组成一个单词。您实现的算法不仅尝试查找单词，还尝试查找任何随机形状的单词。

于 2014-02-06T04:20:05.897 回答