Рекурсивно найти слово в сетке

Question

Я работаю над вопросом алгоритма, чтобы найти слово на сетке.

Мое решение состоит из первого нахождения первой буквы слова в сетке, а затем, если найдено, рекурсивно пройти через 8 направлений, пока каждый индекс слова не будет соответствовать индексам сетки и не вернет строку. Прилагается мой код:

Я отслеживаю свои текущие позиции x и y, а затем увеличиваю позицию строки тогда и только тогда, когда есть совпадение в индексе слова с индексом внутри сетки. Однако, с этим фрагментом кода, есть что-то не так с моей рекурсии вызывает переполнение стека:

public static void findWord(int row, int col, char[][] grid, String w) { 
    int rowLength = row; 
    int colLength = col; 

    char[] word = w.toCharArray(); 

    for(int j = 0; j < colLength; j++) { 
     for(int i = 0; i < rowLength; i++) { 
      // Check if first index of word is in this location 
      if(word[0] == grid[j][i]) { 
       // Iterate through each 8 directions to find the next word 
       for(int dir = 0; dir < 8; dir++) { 
        recursiveFind(i, j, i, j, dir, 0, word, grid, rowLength, colLength); 
       } 
      } 
     } 
    } 
} 

public static boolean recursiveFind(
     int initialX, 
     int initialY, 
     int currentX, 
     int currentY, 
     int dir, 
     int currentPos, 
     char[] word, 
     char[][] grid, 
     int rowLength, 
     int colLength) 
{ 
    // base case is if currentPos == length of word 
    if(word.length == currentPos) { 
     System.out.println("Initial: " + initialX + " " + initialY); 
     System.out.println("Final: " + currentX + " " + currentY); 
    } 

    if(dir == 0) { // 1 
     currentX = currentX; // 0 
     currentY -= 1; // -1 
    } else if(dir == 1) { 
     currentX += 1; // 1 
     currentY -= 1; // -1 
    } else if(dir == 2) { 
     currentX += 1; // 1 
     currentY = 0; // 0 
    } else if(dir == 3) { 
     currentX += 1; // 1 
     currentY += 1; // 1 
    } else if(dir == 4) { 
     currentX = currentX; // 0 
     currentY += 1; // 1 
    } else if(dir == 5) { 
     currentX -= 1; // -1 
     currentY += 1; // 1 
    } else if(dir == 6) { 
     currentX -= 1; // -1 
     currentY = currentY; // 0 
    } else { 
     currentX -= 1; // -1 
     currentY -= 1; // -1 
    } 

    if(currentX < 0 || 
      currentX == rowLength || 
      currentY < 0 || 
      currentY == colLength || 
      grid[currentY][currentX] != word[currentPos]){ 
     return false; 
    } 
    return recursiveFind(initialX, initialY, currentX, currentY, dir, currentPos + 1, word, grid, rowLength, colLength); 
} 

Main.java

char[][] myGrid = new char[][]{ 
      {'H', 'Q', 'W', 'C', 'S'}, 
      {'E', 'S', 'P', 'K', 'D'}, 
      {'D', 'X', 'A', 'F', 'L'}, 
      {'O', 'C', 'H', 'K', 'H'}, 
      {'C', 'T', 'Y', 'C', 'A'}, 
    }; 

    String myWord = "CODE"; 

    findWord(5, 5, myGrid, myWord); 

В настоящее время я пытаюсь поставить некоторые отладочные, чтобы увидеть, что вопрос, однако, если кто-то хочет оказать мне некоторую помощь по этому поводу, он будет высоко оценен!

EDIT:

Я исправил проблему переполнения стека с помощью return true в базовом случае. Однако мои результаты заключаются в следующем, которые не возвращают ожидаемые значения, которые я хотел.

Initial X: 3, Initial Y: 0, Dir: 0, Current X: 3, Current Y: 0 
Initial X: 3, Initial Y: 0, Dir: 1, Current X: 3, Current Y: 0 
Initial X: 3, Initial Y: 0, Dir: 2, Current X: 3, Current Y: 0 
Initial X: 3, Initial Y: 0, Dir: 3, Current X: 3, Current Y: 0 
Initial X: 3, Initial Y: 0, Dir: 4, Current X: 3, Current Y: 0 
Initial X: 3, Initial Y: 0, Dir: 5, Current X: 3, Current Y: 0 
Initial X: 3, Initial Y: 0, Dir: 6, Current X: 3, Current Y: 0 

Answer 1

Я изменил его, чтобы проверить правильность текущего положения, а затем продолжить поиск. В противном случае верните значение false.

public static boolean recursiveFind(
     int initialX, 
     int initialY, 
     int currentX, 
     int currentY, 
     int dir, 
     int currentPos, 
     char[] word, 
     char[][] grid, 
     int rowLength, 
     int colLength) { 
    // base case is if currentPos == length of word 
    if (word.length == currentPos) { 
     System.out.println("Initial: " + initialX + " " + initialY); 
     System.out.println("Final: " + currentX + " " + currentY); 
     return true; 
    } 

    if (currentX >= 0 && currentX < rowLength && currentY >= 0 && currentY < colLength && grid[currentY][currentX] == word[currentPos]) { 
     if (dir == 0) { // 1 
      currentX = currentX; // 0 
      currentY -= 1; // -1 
     } else if (dir == 1) { 
      currentX += 1; // 1 
      currentY -= 1; // -1 
     } else if (dir == 2) { 
      currentX += 1; // 1 
      currentY = 0; // 0 
     } else if (dir == 3) { 
      currentX += 1; // 1 
      currentY += 1; // 1 
     } else if (dir == 4) { 
      currentX = currentX; // 0 
      currentY += 1; // 1 
     } else if (dir == 5) { 
      currentX -= 1; // -1 
      currentY += 1; // 1 
     } else if (dir == 6) { 
      currentX -= 1; // -1 
      currentY = currentY; // 0 
     } else { 
      currentX -= 1; // -1 
      currentY -= 1; // -1 
     } 

     return recursiveFind(initialX, initialY, currentX, currentY, dir, currentPos + 1, word, grid, rowLength, colLength); 
    } 

    return false; 

} 

EDIT: С вашей последней правкой, проблема заключается в том, что вы изменяете CurrentX/CurrentY перед проверкой текущего положения.

Этот фрагмент кода:

if(currentX < 0 || 
     currentX == rowLength || 
     currentY < 0 || 
     currentY == colLength || 
     grid[currentY][currentX] != word[currentPos]){ 
    return false; 
} 

должно произойти, прежде чем сделать:

if(dir == 0) { // 1 
    currentX = currentX; // 0 
    currentY -= 1; // -1 
} else if(dir == 1) { 
    currentX += 1; // 1 
    currentY -= 1; // -1 
} else if(dir == 2) { 
    currentX += 1; // 1 
    currentY = 0; // 0 
} else if(dir == 3) { 
    currentX += 1; // 1 
    currentY += 1; // 1 
} else if(dir == 4) { 
    currentX = currentX; // 0 
    currentY += 1; // 1 
} else if(dir == 5) { 
    currentX -= 1; // -1 
    currentY += 1; // 1 
} else if(dir == 6) { 
    currentX -= 1; // -1 
    currentY = currentY; // 0 
} else { 
    currentX -= 1; // -1 
    currentY -= 1; // -1 
} 

Или вы действительно не проверяя текущее положение: P

Answer 2

С первого взгляда, я думаю, что проблема может быть, что вы не прекращает рекурсию, когда currentpos достигает длину слова, так что он будет продолжать идти, пока она не переливается. Базовый регистр должен заканчиваться рекурсией, но ваш продолжается, если условие для возврата false не выполняется.

Edit: Im уверен, что условие директории 2 должно быть:

else if(dir == 2) { 
     currentX += 1; // 1 
     currentY = currentY; // 0 
    } 

В противном случае вы перезагрузить текущую Y, как у вас сейчас

EDIT: Кроме того, вы не должны отправьте currentpos как 0 для начала рекурсии, потому что он снова сравним с первой буквой слова. Рекурсия должна начинаться со второго символа, поскольку вы уже сравнили первый. Не забудьте добавить значение true, и ваша программа должна работать. Я просто попробовал это на своем компьютере.