我正在尝试调试我的类。这个类正在经历一个令人难以置信的板子，并找到每一个可用的路径。路径包括水平、垂直和对角线。您不得重复某个步骤。我目前有很多打印语句试图找出我出错的地方，但我似乎找不到它。我把这些留了下来。我认为这与我当前的路径[][]有关。任何指示提示将不胜感激。
public class FindWords {
String [][] board;
final int LAST_LETTER = 2;
final int BEEN_THERE = 1;
final int AVAILABLE = 0;
BoggleDictionary Dictionary;
private StackADT<SearchWords> searchStack = new ArrayStack<SearchWords>();
public StackADT<SearchWords> foundStack = new ArrayStack<SearchWords>();
public FindWords (String [][] board) throws Exception {
this.board = board;
this.Dictionary = new BoggleDictionary();
//this.foundStack = null;
}
public void startSearch(){
for (int i = 0; i < board.length; i++){
for (int j = 0; j < board[0].length; j++){
System.out.println(board[i][j]);
String firstLetter = "";
int [][] pathBoard = makeBlankBoard();
pathBoard[i][j] = LAST_LETTER;
System.out.println(">>" + Arrays.deepToString(pathBoard));
firstLetter = board[i][j];
System.out.println("first letters : " + firstLetter + " <====");
SearchWords thisPath = new SearchWords(pathBoard, firstLetter);
searchStack.push(thisPath);
}
}
Search();
}
private boolean Search(){
while (!searchStack.isEmpty())
{
SearchWords searchObj = searchStack.pop();
int [][] currentPath = searchObj.getPath();
int [][] array = new int [currentPath.length][currentPath[0].length];
for (int i = 0; i <currentPath.length; i++){
for (int j = 0; j <currentPath[0].length; j++){
array[i][j] = currentPath[i][j];
}
}
String makingString = searchObj.getString();
if (makingString.length() > 2){
if (Dictionary.contains(makingString)){
foundStack.push(searchObj);
}
}
for (int i = 0; i < array.length; i ++){
for (int j = 0; j < array[0].length; j++){
if (array[i][j] == LAST_LETTER){ //finding the last position in the string
int x = i;
int y = j;
//array[i][j] = BEEN_THERE;
pushPosition(searchObj, x+1, y+1, i, j); //lower left then going counter-clockwise
pushPosition(searchObj, x, y+1, i, j);
pushPosition(searchObj, x-1, y+1, i, j);
pushPosition(searchObj, x-1, y, i, j);
pushPosition(searchObj, x-1, y-1, i, j);
pushPosition(searchObj, x, y-1, i, j);
pushPosition(searchObj, x+1, y-1, i, j);
pushPosition(searchObj, x+1, y, i, j);
}
}
}
}
return true;
}
private void pushPosition (SearchWords obj, int x, int y, int i, int j){
int [][] currentPath = obj.getPath();
String makingString = obj.getString();
System.out.println("In push method: " + Arrays.deepToString(currentPath) +x+y+i+j);
if (validPosition(x, y, currentPath)){
currentPath[x][y] = LAST_LETTER;
currentPath[i][j] = BEEN_THERE;
System.out.println("after valid ch: "+ Arrays.deepToString(currentPath));
makingString = makingString + board[x][y];
SearchWords newPath = new SearchWords(currentPath, makingString);
System.out.println("is string getting longer: " + makingString);
System.out.println("Stack size: " + searchStack.size());
System.out.println("pushing back on stack"+ Arrays.deepToString(currentPath));
searchStack.push(newPath);
}
}
private boolean validPosition (int x, int y, int [][] path){
boolean result = false;
if (x >= 0 && x < board.length && y >= 0 && y < board[x].length){
if (path[x][y] == AVAILABLE){
System.out.println("Checked position : " + x + y);
result = true;
}
}
return result;
}
private int [][] makeBlankBoard(){
int row = board.length;
int col = board[0].length;
int [][] blankBoard = new int [row][col];
for (int i = 0; i < board.length; i++){
for (int j = 0; j < board[0].length; j++){
blankBoard[i][j] = AVAILABLE;
}
}
return blankBoard;
}
}
更新了有效的类。在调用推送方法之前需要创建路径板的新副本。谢谢杀戮。
private void Search(){
while (!searchStack.isEmpty())
{
System.out.println("stack size in search: " + searchStack.size());
SearchWords searchObj = searchStack.pop();
int lastLetterRow = searchObj.getRow();
int lastLetterCol = searchObj.getCol();
String stringSoFar = searchObj.getString();
int [][] pathBoard = searchObj.getPath();
System.out.println ("row then Col: " + lastLetterRow + lastLetterCol);
System.out.println ("string so far: " + stringSoFar);
System.out.println("Path board so far in search: " + Arrays.deepToString(pathBoard)+ "n");
if (stringSoFar.length() > 2){
if (Dictionary.contains(stringSoFar)){
foundStack.push(searchObj);
System.out.println("Found word!! " + stringSoFar);
}
}
System.out.println("made it past if dict");
//lower left then going counter-clockwise
pushPosition (pathBoard, stringSoFar, lastLetterRow+1, lastLetterCol+1, lastLetterRow, lastLetterCol);
pathBoard = makeCopy(pathBoard);
pushPosition (pathBoard, stringSoFar, lastLetterRow, lastLetterCol+1, lastLetterRow, lastLetterCol);
pathBoard = makeCopy(pathBoard);
pushPosition(pathBoard, stringSoFar, lastLetterRow, lastLetterCol+1, lastLetterRow, lastLetterCol);
pathBoard = makeCopy(pathBoard);
pushPosition(pathBoard, stringSoFar, lastLetterRow-1, lastLetterCol+1, lastLetterRow, lastLetterCol);
pathBoard = makeCopy(pathBoard);
pushPosition(pathBoard, stringSoFar, lastLetterRow-1, lastLetterCol, lastLetterRow, lastLetterCol);
pathBoard = makeCopy(pathBoard);
pushPosition(pathBoard, stringSoFar, lastLetterRow-1, lastLetterCol-1, lastLetterRow, lastLetterCol);
pathBoard = makeCopy(pathBoard);
pushPosition(pathBoard, stringSoFar, lastLetterRow, lastLetterCol-1, lastLetterRow, lastLetterCol);
pathBoard = makeCopy(pathBoard);
pushPosition(pathBoard, stringSoFar, lastLetterRow+1, lastLetterCol-1, lastLetterRow, lastLetterCol);
pathBoard = makeCopy(pathBoard);
pushPosition(pathBoard, stringSoFar, lastLetterRow+1, lastLetterCol, lastLetterRow, lastLetterCol);
}
System.out.println("FOUND WORDS:");
while(!foundStack.isEmpty()){
SearchWords foundWords = foundStack.pop();
System.out.println(foundWords.getString());
}
}
如评论中所述，看起来您遇到的特定问题是多个路径共享描述您搜索的路径的同一数组。这会产生错误，其中它们的搜索历史记录相互覆盖，从而在currentPath数组中留下一组不是特别有用的信息。
为推送的每个路径执行数组复制可能会解决此问题（代码中可能还有其他问题，但没有任何内容出现在我身上。
我提倡一种不同的方法来存储路径数组，因为实际上没有必要每次都复制整个网格。相反，您可以将每个路径跟踪为：
- 路径中
- 最后一个字母的位置（对于在路径中执行下一步很有用，就像在您的算法中一样）
- 通向该点的上一个路径（这将是相同类型的对象）
代码示例如下所示（请注意，我尚未对此进行测试，因为它仅用作示例）：
class SearchPath {
int x, y;
String string;
SearchPath prior;
// x,y are most recent position; prior is the path up to this point, or null
public SearchPath(int x, int y, String board, SearchPath prior) {
this.x = x;
this.y = y;
this.string = (prior != null ? prior.string : "") + board[x][y];
this.prior = prior;
}
// To check if an x,y location collides with this path
public contains(int x, int y) {
if (this.x == x && this.y == y) {
return true;
} else if (prior == null) {
return false;
} else {
return prior.contains(x,y);
}
}
}
在你的初始循环（startSearch）中，你将推动没有先前路径的对象（new SearchPath(i, j, board, null)）。在search循环中，您将弹出其中一个，然后在检查新的 x/y 坐标是否未通过 contains 方法使用后推送new SearchPath(searchPath.x - 1, searchPath.y, board, searchPath)。（请注意，使用堆栈来存储搜索路径可能也不是必需的，因为您应该通过进行递归搜索调用来获得相同的搜索模式。