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

Question

我试图创建一个boggle游戏的迭代方法。该类包含一个名为“Board”的2D字符串数组的字段，并有一个名为“HaveVisit”的2D布尔数组。调用test2的方法遍历整个板，查找目标字符串第一个字符的位置，然后将坐标传递给test2方法，返回一个包含坐标的列表。

return1Index方法获取一个2D数组坐标at，创建一个int表示对应的1D数组的坐标。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

我不知道问题到底出在哪里，但有几个疑点：

>

您正在更新行和列索引，同时检查它们的邻居。这就像在遍历数组时从数组中删除一个元素一样：它定义得很好，但语义很棘手。我建议要么省略（贪婪算法），要么保留匹配的堆栈（更深的搜索，也需要保存访问的单元格堆栈）。

的缺少开始大括号，但结束大括号在那里，这表明缺少代码。

我不熟悉boggle，但是一个字母不可能有两个相似的邻居，比如AXA吗？只需执行output.add(return1DIndex(x,y））；，就可以输出两种获取相同字母的方法。您可能会得到output长于findme的结果。

我的建议是，在排除错误的同时，遵循更标准的深度优先搜索格式。Wikipedia有一个非递归伪代码实现，例如:https://en.Wikipedia.org/wiki/depth-first_search#pseudocode。