Блог

Итак, я писал программу для игры 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]. Итак, это то, что я пробовал, но я продолжаю получать ошибки out of bounds! Вот в чем проблема…

     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]

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

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

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

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

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

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

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

Редактировать: Ваше самое длинное слово должно быть только 16 . Boggle использует доску 4×4, а word не может использовать одно и то же местоположение дважды. Не то чтобы это действительно имело значение, но это могло бы быть для назначения. Также обратите внимание, что я просто сделал это в своей голове и не уверен, что у меня получилось на 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 amp;amp; y2 == y) ||
                visited[x2][y2])
            {
                continue;
            }

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

        }
    }

    return adjoining;
}
  

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

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

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