在二维数组中查找完整的单词

Question

结论如下:[0,2]->[1,2]->[2,2]->[2,3]->[2,4]->[3,4]->[4,4]->[5,4]->[5,3]->[5,2]->[5,1]->[4,1]->[4,2]->[3,2]->[3,1]->[2,1]->[2,2]->[1,2]->[2,2]->[1,2]->[2,2]->[2,2]->[1,2]->[2,2]->[2,2]->[2,2]->[1,2]

我不明白故障在哪里，如何修复，请帮忙。

我的代码：

public class GFS {
    private static int R;
    private static int C;
    private static int[] x = {-1, 0, 1, 0};
    private static int[] y = {0, 1, 0, -1};
    private static StringBuilder stringBuilder = new StringBuilder();
    private static int indexForWord = 1;

    public static void main(String[] args) {
        R = 7;
        C = 7;
        /*String word = "BOBA";
        String cross = "QWBOABOBGSBSERTY";*/
        /*String word = "KING";
        String cross = "QLGNAEKIRLRNGEAE";*/
        /*String word = "APPLE";
        String cross = "UKJVXNAPBXELPLHVNLDKBVVNM";*/
        String word = "DISABILITATING";
        String cross = "FBDHBAAGNITISTDASABIDDBITILBNILALASGTATIGIYGNTGND";
        char[][] grid = createMatrix(cross);

        search2D(grid, word, 2, 0);
        System.out.println(stringBuilder.toString());
    }

    static char[][] createMatrix(String input) {
        char[][] newArr = new char[R][C];
        int index = 0;
        for (int i = 0; i < newArr.length; i++) {
            for (int j = 0; j < newArr.length; j++) {
                newArr[i][j] = input.charAt(index++);
            }
        }
        return newArr;
    }

    static void print(char[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid.length; j++) {
                System.out.print(grid[i][j] + "  ");
            }
            System.out.println();
        }
    }

    static boolean search2D(char[][] grid, String word, int positionX, int positionY) {
        char oldChar = grid[positionY][positionX];

        if (indexForWord >= word.length()) {
            return true;
        }
        int top = positionY - 1 < 0 ? positionY : positionY - 1;
        int bottom = positionY + 1 >= grid.length ? positionY : positionY + 1;
        int right = positionX + 1 >= grid.length ? positionX : positionX + 1;
        int left = positionX - 1 < 0 ? positionX : positionX - 1;

        if (grid[top][positionX] == word.charAt(indexForWord)) {
            indexForWord++;
            grid[positionY][positionX] = ' ';
            boolean check = search2D(grid, word, positionX, top);
            if (check) {
                stringBuilder.append("[").append(top).append(", ").append(positionX).append("]");
                return true;
            } else {
                for (int j = indexForWord; j >= 0; j--) {
                    if (word.charAt(j) == oldChar) {
                        indexForWord = j + 1;
                        grid[positionY][positionX] = oldChar;
                        break;
                    }
                }
            }
        }
        if (grid[bottom][positionX] == word.charAt(indexForWord)) {
            indexForWord++;
            grid[positionY][positionX] = ' ';
            boolean check = search2D(grid, word, positionX, bottom);
            if (check) {
                stringBuilder.append("[").append(bottom).append(", ").append(positionX).append("]");
                return true;
            } else {
                for (int j = indexForWord; j >= 0; j--) {
                    if (word.charAt(j) == oldChar) {
                        indexForWord = j + 1;
                        grid[positionY][positionX] = oldChar;
                        break;
                    }
                }
            }
        }
        if (grid[positionY][left] == word.charAt(indexForWord)) {
            indexForWord++;
            grid[positionY][positionX] = ' ';
            boolean check = search2D(grid, word, left, positionY);
            if (check) {
                stringBuilder.append("[").append(positionY).append(", ").append(left).append("]");
                return true;
            } else {
                for (int j = indexForWord; j >= 0; j--) {
                    if (word.charAt(j) == oldChar) {
                        indexForWord = j + 1;
                        grid[positionY][positionX] = oldChar;
                        break;
                    }
                }
            }
        }
        if (grid[positionY][right] == word.charAt(indexForWord)) {
            indexForWord++;
            grid[positionY][positionX] = ' ';
            boolean check = search2D(grid, word, right, positionY);
            if (check) {
                stringBuilder.append("[").append(positionY).append(", ").append(right).append("]");
                return true;
            } else {
                for (int j = indexForWord; j >= 0; j--) {
                    if (word.charAt(j) == oldChar) {
                        indexForWord = j + 1;
                        grid[positionY][positionX] = oldChar;
                        break;
                    }
                }
            }
        }
        return false;
    }
}

Answer 1

出现这种情况是因为从错误路径回溯时indexforword设置不正确，并且存在重复字符（在您的示例中，是T）

else {
    for (int j = indexForWord; j >= 0; j--) {
        if (word.charAt(j) == oldChar) {
           indexForWord = j + 1;
           grid[positionY][positionX] = oldChar;
           break;
        }
}

相反，只要在每次检查为false时后退一次就足够了（在所有4种情况下）：

else {
       grid[positionY][positionX] = oldChar;
       indexForWord--;
     }

同样，结果也是反向的([5,0]->[4,0]->[4,1]->[5,1]等），所以您必须将其反向或找出另一种方法。