迭代深度优先搜索查找字符串(2D数组)

Question

我正尝试着创造一种迭代方法去创造一款拼字游戏。这个类包含一个名为"board"的二维字符串数组的字段，还有一个名为"haveVisit"的二维布尔值数组。调用test2的方法循环遍历整个棋盘，查找目标字符串的第一个字符的位置，然后将坐标传递给test2方法，返回一个包含坐标的列表。

return1Index方法接受一个2D数组坐标，并从对应的1d数组中创建一个int表示坐标。而return2DIndex则相反，返回一个包含两个坐标的int数组。

public List<Integer> test2(int row1, int row2, String findMe){
     String temp = findMe;
     List<Integer> output = new ArrayList<Integer>();
     if (board[row1][row2].charAt(0) != findMe.charAt(0))
        return output;
     haveVisit = new boolean[size][size];
     int row = row1; 
     int column = row2;                                    
     output.add(return1DIndex(row, column));           
     haveVisit[row][column] = true;                   
     //for each letter in the string
     for(int j = 0; j < temp.length(); j++)
        //for every column and row combination
        for (int x = row - 1; x < row + 2 ; x++)
           for (int y = column - 1; y < column + 2 ; y++)
              //if index is valid and not visited
              if (x > -1 && y > -1 && y < size && x < size && !haveVisit[x][y])
                 //if the output is the same size as string, return
                 if(output.size() == findMe.length())
                    return output;
                 //if the character in the board matches the char we're looking for
                 if(board[x][y].charAt(0) == temp.charAt(j))
                 {
                    haveVisit[x][y] = true;
                    output.add(return1DIndex(x, y));
                    //update row and column indices
                    row = x;
                    column = y;
                 }
              }
           }
     return output;
  }

由于某些原因，这种方法只有50%的时间有效。当字母从左到右或从上到下排列时，该方法可以很好地找到它们，但是从右到左或从下到上查找单词永远不会起作用，除非在一种情况下:当你搜索长度为1或2的字符串时，该方法总是有效的。

我有一个有效的递归解决方案，但我想尝试这种方式。有什么想法，为什么这不会工作?

编辑:代码现在工作从右到左，但仍然不工作时，试图向上搜索

Answer 1

我不知道到底是什么问题，但有几个怀疑:

• 您正在更新行和列索引，同时检查它们的邻居。这就像在迭代数组时从数组中删除一个元素:它定义良好，但具有复杂的语义。我建议要么纾困(贪婪算法)或保持匹配堆栈(更深的搜索，需要保存访问单元的堆栈太)。

• for缺少左花括号，但是右花括号存在，提示缺少代码。

• 我不熟悉boggle，但是一个字母不可能有两个相似的邻居，比如AXA吗?通过output.add(return1DIndex(x, y));，你可以输出两种方法来得到相同的字母。

最后output可能比findMe长。

我的建议是在你解决bug的时候遵循更标准的深度优先搜索格式。Wikipedia有一个非递归的伪代码实现，例如:https://en.wikipedia.org/wiki/Depth-firstrongearch#Pseudocode .