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

wqlqzqxt  于 2021-06-29  发布在  Java
关注(0)|答案(2)|浏览(379)

我有一项艰巨的任务。我需要在二维数组中匹配“stringbuilder”单元格时将单词写入其中。这意味着我必须找到完整的单词,避免重复的单元格。为了更好的理解,我会附上一张照片,在黄色单元格中正确遍历,其中红色单元格是错误的路径。

结论如下:[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,0]->[5,0]现在我的结论是:[5,0]->[4,0]->[4,1]->[4,2]->[3,2]->[3,1]->[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;
    }
}
o4tp2gmn

o4tp2gmn1#

这是因为 indexForWord 当从错误的路径回溯并且存在重复字符时设置不正确(在您的情况下,是t)

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

相反,只要每一次退后一步就足够了 check 为假(在所有4种情况下):

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

结果也是相反的([5,0]->[4,0]->[4,1]->[5,1]等等),所以你必须反转它或者想出另一种方法。

watbbzwu

watbbzwu2#

除了bahij所说的:

private static int indexForWord = 1;

应使用0而不是1初始化。
结合bahij的解决方案,这个

[5, 0][4, 0][4, 1][5, 1][5, 2][5, 3][5, 4][4, 4][3, 4][2, 4][2, 3][2, 2][1, 2][0, 2]

(不幸的是,我不能评论他/她的答案,因为我没有足够的声誉哈哈)

相关问题