java - 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)整数计数 = 0； (被宣布在类(class)的顶部，如果你想知道我从哪里得到这个词[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 中标记当前位置，并通过使用 word.substring(1) 和那些坐标。如果您用完了 word 中的字母，您就找到了它并返回 true。请注意，如果您返回 false，则需要从 visited 中删除当前位置。

您可以使用一个函数来完成此操作，但通过拆分逻辑，我个人认为它会更容易在您的头脑中进行管理。一个缺点是它确实对单词中的每个第一个字母进行了额外的比较。要使用单个函数，您需要使用 boolean 值或深度计数器来跟踪您所处的“模式”。

编辑:你最长的单词应该只有 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);

我最初是在脑海中这样做的，然后沿着这条路尝试向您展示它是如何工作的。如果我真的要实现这个，我会做一些不同的事情(主要是消除单词中第一个字母的双重比较，可能是通过将两者组合成一个方法，尽管你可以通过重新排列当前方法中的逻辑来做到这一点)，但上面的代码确实起作用，应该可以帮助您更好地理解递归搜索。