Рекурсивный поиск в Java

Question

Итак, я пишу программу для игры Boggle. Я создаю небольшую доску для пользователя, но проблема в том, что я не знаю, как проверить, есть ли это слово на доске рекурсивно. Я хочу иметь возможность проверить, действительно ли введенное слово есть на доске и является ли оно действительным. Под действительным я имею в виду, что буквы слова должны быть смежными друг с другом. Для тех, кто играл в boggle, вы поймете, что я имею в виду. Все, что я хочу сделать, это проверить, есть ли слово на доске.

Это то, что я имею до сих пор ....

import java.io.*;
public class boggle {
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(isr);
    private String s = "";
    private int [][] lettersNum = new int [5][5];
    private char [][] letters = new char [5][5];
    private char [] word = new char [45]; // Size at 45, because the longest word in the dictionary is only 45 letters long 
    private char [] temp; 

    public void generateNum()
    {
        for (int row = 0; row < 5; row ++)
        {
            for (int col = 0; col < 5; col++)
            {
                lettersNum [row][col] = (int) (Math.random() * 26 + 65);
            }
        }
    }

    public void numToChar()
    {
        for (int row = 0; row < 5; row ++)
        {
            for (int col = 0; col < 5; col++)
            {
                letters [row][col] = (char)(lettersNum[row][col]);
            }
        }
    }

    public void display()
    {
        for (int row = 0; row < 5; row ++)
        {
            for (int col = 0; col < 5; col++)
            {
                System.out.print(letters[row][col]);
            }
            System.out.println("");
        }
    }

    public void getInput() throws IOException
    {
        System.out.println("Please enter a word : ");
        s=br.readLine();
        s=s.toUpperCase();
        word = s.toCharArray();
    }

    public int search(int row, int col)
    {
        if((row <0) || (row >= 5) || (col < 0) || (col >= 5))
        {
            return (0);
        }
        else
        {
            temp = word;
            return (1+ search(row +1, col) +
                    search(row -1, col) + 
                    search(row, col + 1) + 
                    search(row, col-1) +
                    search(row +1, col +1)+
                    search(row +1, col -1)+
                    search(row -1, col +1)+
                    search(row -1, col -1));
        }
    }


}

Поиск был моим алгоритмом поиска, чтобы проверить, есть ли слово на доске, но я не знаю, правильно ли оно или будет ли оно работать. Кроме того, я не знаю, как на самом деле сказать пользователю, что слово действительно!

Спасибо за помощь :)

ТАК Я пытался использовать то, что вы предложили ниже, но я не совсем понимаю, что такое int [5] [5]. Так что это то, что я пытался, но я продолжаю выходить за пределы ошибок! Вот такая вот ...

    public void locate()
{
    temp = word[0];
    for (int row = 0; row <5; row++)
    {
        for (int col = 0; col <5; col++)
        {
            if(temp == letters[row][col])
            {
                search(row,col);
            }
        }
    }
}

public int search(int row, int col)
{
    if(letters[row][col-1]==word[count]) // Checks the letter to the left
    {
        count++;
        letters[row][col-1] = '-'; // Just to make sure the program doesn't go back on itself
        return search(row, col-1);
    }
    else if (letters[row][col+1] == word[count])// Checks the letter to the right
    {
        count++;
        letters[row][col+1] = '-';// Just to make sure the program doesn't go back on itself
        return search(row, col +1);
    }
    else if (letters[row+1][col]== word[count])// Checks the letter below
    {
        count++;
        letters[row+1][col] = '-';// Just to make sure the program doesn't go back on itself
        return search(row +1 , col);
    }
    else if (letters[row-1][col]== word[count])// Checks the letter above 
    {
        count++;
        letters[row-1][col] = '-';// Just to make sure the program doesn't go back on itself
        return search(row -1 , col);
    }
    else if (letters[row-1][col-1]== word[count])// Checks the letter to the top left
    {
        count++;
        letters[row-1][col-1] = '-';// Just to make sure the program doesn't go back on itself
        return search(row -1 , col-1);
    }
    else if (letters[row-1][col+1]== word[count])// Checks the letter to the top right
    {
        count++;
        letters[row-1][col+1] = '-';// Just to make sure the program doesn't go back on itself
        return search(row -1 , col+1);
    }
    else if (letters[row+1][col-1]== word[count])// Checks the letter to the bottom left
    {
        count++;
        letters[row+1][col-1] = '-';// Just to make sure the program doesn't go back on itself
        return search(row +1 , col-1);
    }
    else if (letters[row+1][col+1]== word[count])// Checks the letter to the bottom right
    {
        count++;
        letters[row+1][col+1] = '-';// Just to make sure the program doesn't go back on itself
        return search(row +1 , col+1);
    }
    return 0;
}

private int count = 0; (был объявлен в начале класса, на случай, если вам интересно, откуда я взял слово [count] из

Answer 1

Ваша текущая функция поиска на самом деле ничего не делает. Я предполагаю, что это домашнее задание, поэтому нет бесплатного обеда;)

Самый простой подход - использовать две рекурсивные функции:

public boolean findStart(String word, int x, int y)

Это будет выполнять линейный поиск доски в поисках первого символа в word. Если ваше текущее местоположение не совпадает, вы называете себя следующим набором координат. Когда он находит совпадение, он вызывает вашу вторую рекурсивную функцию, используя word, текущее местоположение и новую пустую матрицу 4x4:

public boolean findWord(String word, int x, int y, int[][] visited)

Эта функция сначала проверяет, соответствует ли текущее местоположение первой букве в word. Если это так, он отмечает текущее местоположение в visited и проходит по всем смежным квадратам , за исключением отмеченных в visited, вызывая себя с помощью word.substring(1) и этих координат. Если у вас закончились буквы в word, вы нашли его и вернули true. Обратите внимание, что если вы возвращаете false, вам нужно удалить текущее местоположение из visited.

Вы можете сделать это с помощью одной функции, но, разделив логику, я лично думаю, что вам станет легче управлять в вашей голове. Единственным недостатком является то, что он делает дополнительное сравнение для каждой первой буквы в слове. Чтобы использовать одну функцию, вам необходимо отслеживать, в каком «режиме» вы работали, с помощью логического значения или счетчика глубины.

Редактировать: Ваше самое длинное слово должно быть только 16. Boggle использует доску 4x4, и слово не может использовать одно и то же место дважды. Не то, чтобы это действительно имело значение, но это могло бы быть для назначения. Также обратите внимание, что я просто сделал это в своей голове и не знаю, что я понял это на 100% правильно - комментарии приветствуются.

Редактировать в ответ на комментарии:

Вот как будет выглядеть ваша итерация locate с использованием описанного выше метода:

public boolean locate(String word) 
{ 
    for (int row = 0; row < 4; row++) 
    {  
        for (int col =0; col < 4; col++) 
        { 
            if (word.charAt(0) == letters[row][col])
            {
                boolean found = findWord(word, row, col, new boolean[4][4]);
                if (found) 
                    return true;
            } 
        } 
     }
     return false;
}    

То же самое рекурсивно выглядит следующим образом, что должно помочь:

public boolean findStart(String word, int x, int y)
{
    boolean found = false;
    if (word.charAt(0) == letters[x][y])
    {
        found = findWord(word, x, y, new boolean[4][4]);
    } 

    if (found)
        return true;
    else 
    {
        y++;
        if (y > 3)
        {
            y = 0;
            x++;
        }

        if (x > 3)
           return false;    
    }

    return findStart(word, x, y);
}        

Итак, вот findWord() и вспомогательный метод getAdjoining(), чтобы показать вам, как все это работает. Обратите внимание, что я изменил массив visited на boolean только потому, что это имело смысл:

public boolean findWord(String word, int x, int y, boolean[][] visited)
{
    if (letters[x][y] == word.charAt(0))
    {
        if (word.length() == 1) // this is the last character in the word
            return true;
        else
        {
            visited[x][y] = true;
            List<Point> adjoining = getAdjoining(x,y,visited);

            for (Point p : adjoining)
            {
                boolean found = findWord(word.substring(1), p.x, p.y, visited);
                if (found)
                    return true;
            }
            visited[x][y] = false;
        }

    }
    return false;
}

public List<Point> getAdjoining(int x, int y, boolean[][] visited)
{
    List<Point> adjoining = new LinkedList<Point>();

    for (int x2 = x-1; x2 <= x+1; x2++)
    {
        for (int y2 = y-1; y2 <= y+1; y2++)
        {
            if (x2 < 0 || x2 > 3 ||
                y2 < 0 || y2 > 3 ||
                (x2 == x && y2 == y) ||
                visited[x2][y2])
            {
                continue;
            }

            adjoining.add(new Point(x2,y2));

        }
    }

    return adjoining;
}

Так что теперь, после того, как вы получите ввод от пользователя в виде String (слово), вы просто позвоните:

boolean isOnBoard = findStart(word,0,0);

Первоначально я делал это в своей голове, затем просто пошел по этому пути, чтобы попытаться показать вам, как это работает. Если бы я на самом деле реализовал это, я бы сделал некоторые вещи по-другому (в основном, исключив двойное сравнение первой буквы в слове, возможно, путем объединения двух в один метод, хотя вы можете сделать это, переставив логику в текущих методах), но приведенный выше код работает и должен помочь вам лучше понять рекурсивный поиск.