Блог

У меня сложная задача. Мне нужно записывать слова в ячейки «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, 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;
    }
}
 

Это происходит из indexForWord -за того, что значение не задано правильно при возврате с неправильного пути, и есть повторяющиеся символы (в вашем случае это T)

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

Вместо этого достаточно просто отступать один раз каждый check раз, когда значение равно false (во всех 4 случаях):

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

Также результат будет обратным ([5, 0] -> [4, 0] -> [4, 1] -> [5, 1] и т.д.), Так что вам придется отменить его или придумать другой подход.

В дополнение к тому, что сказал Бахидж :

     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]
 

(К сожалению, я не могу прокомментировать его / ее ответ, потому что у меня недостаточно репутации, лол)