0

我正在尝试调试我的课程。这门课正在通过一块拼图板并找到每条可用的路径。路径包括水平、垂直和对角线。你不能重复一个步骤。我目前有很多打印语句试图找出我哪里出错了，但我似乎找不到它。我把这些留在了。我认为这与我的 currentPath[][] 有关。任何指针提示将不胜感激。

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;
}

}

更新了有效的课程。在调用 push 方法之前需要制作一个新的 pathBoard 副本。谢谢杀屏。

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());
    }
}
4

1 回答 1

0

正如评论中提到的，看起来您遇到的具体问题是多个路径共享同一个数组，该数组描述了您搜索的路径。这会产生错误，其中它们的搜索历史相互覆盖，留下一个不是特别有用的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循环中，您将弹出其中一个，然后new SearchPath(searchPath.x - 1, searchPath.y, board, searchPath)在检查未通过该contains方法使用新的 x/y 坐标后推送 a。（请注意，可能也不需要使用堆栈来存储搜索路径，因为您应该通过递归搜索调用获得相同的搜索模式。）

于 2013-10-24T04:30:25.793 回答