所以我一直在为游戏 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]
最佳答案
您当前的搜索功能实际上并没有做任何事情。我假设这是家庭作业，天下没有免费的午餐 ;)
最简单的方法是使用两个递归函数:
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);
我最初是在脑海中这样做的，然后沿着这条路尝试向您展示它是如何工作的。如果我真的要实现这个，我会做一些不同的事情(主要是消除单词中第一个字母的双重比较，可能是通过将两者组合成一个方法，尽管你可以通过重新排列当前方法中的逻辑来做到这一点)，但上面的代码确实起作用，应该可以帮助您更好地理解递归搜索。
关于java - Java 中的递归搜索，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5765215/