Итеративная глубина, первый поиск для поиска строки (2D Array)

Я пытаюсь создать итеративный подход к изумительной игре. Класс содержит поля для двумерного массива строк, называемого "board", и имеет двумерный массив логических значений, называемый "haveVisit". Метод, который вызывает test 2, проходит по всей доске, находя позиции первого символа целевой строки, затем передает координаты в метод test2, возвращая список, содержащий координаты.

Метод return1Index принимает координату двумерного массива at, создает из него int, представляющий координаты из соответствующего 1d массива. Return2DIndex делает обратное и возвращает массив int, содержащий две координаты.

public List<Integer> test2(int row1, int row2, String findMe){
     String temp = findMe;
     List<Integer> output = new ArrayList<Integer>();
     if (board[row1][row2].charAt(0) != findMe.charAt(0))
        return output;
     haveVisit = new boolean[size][size];
     int row = row1; 
     int column = row2;                                    
     output.add(return1DIndex(row, column));           
     haveVisit[row][column] = true;                   

     //for each letter in the string
     for(int j = 0; j < temp.length(); j++)

        //for every column and row combination
        for (int x = row - 1; x < row + 2 ; x++)
           for (int y = column - 1; y < column + 2 ; y++)

              //if index is valid and not visited
              if (x > -1 && y > -1 && y < size && x < size && !haveVisit[x][y])
                 //if the output is the same size as string, return
                 if(output.size() == findMe.length())
                    return output;

                 //if the character in the board matches the char we're looking for
                 if(board[x][y].charAt(0) == temp.charAt(j))
                 {
                    haveVisit[x][y] = true;
                    output.add(return1DIndex(x, y));

                    //update row and column indices
                    row = x;
                    column = y;
                 }
              }
           }
     return output;
  }

По какой-то причине этот метод работает только в 50% случаев. Этот метод отлично работает с поиском букв, когда они расположены слева направо или сверху вниз, но поиск слов справа налево или снизу вверх никогда не работает, за исключением одного случая: когда вы ищете строку длиной 1 или 2, где этот метод всегда работает.

У меня есть работающее рекурсивное решение, но я хотел попробовать этот способ. Есть мысли, почему это не сработает?

Изменить: код теперь работает справа налево, но все равно не работает при попытке поиска вверх.

Источник

1 ответ

Я не знаю точно, в чем проблема, но есть несколько подозреваемых:

  • Вы обновляете индексы строк и столбцов, проверяя их соседей. Это похоже на удаление элемента из массива во время его итерации: он хорошо определен, но имеет хитрую семантику. Я предлагаю либо выручить (жадный алгоритм), либо сохранить стек совпадений (более глубокий поиск также требует сохранения стека посещенных ячеек).

  • forВ ней отсутствуют открывающие скобки, но есть закрывающие скобки, что указывает на отсутствие кода.

  • Я не знаком с потрясением, но разве в письме не может быть двух похожих соседей? AXA? Просто делая output.add(return1DIndex(x, y)); Вы можете выводить два способа получить одну и ту же букву. Вы можете в конечном итоге с output длиннее чем findMe,

Я предлагаю придерживаться более стандартного формата поиска в глубину, пока вы устраняете ошибки. В Википедии есть нерекурсивная реализация псевдокода, например: https://en.wikipedia.org/wiki/Depth-first_search.

Источник
Другие вопросы по тегам