Java：搜索二维数组中的单词

我已经学习了大约4个月的Java，这是我学习的第一门编程语言。 对于学校，我们必须做一个项目，一个基于控制台的游戏。 我选择了Boggle。

我有一个带有骰子的ArrayList，每个都有一个随机的“向上”，然后ArrayList被洗牌，一个二维数组充满了每一面的值。 此时arrays充满了字符串，字符可能是更好的选择，但是很容易改变。

我面临的问题是我需要能够在数组中找到单词。 Boggle中的单词可以向任何方向移动，每个单独的块只能使用一次，但路径可以交叉，也可以对角搜索。 我设法找到数组中是否存在第一个字母。 如果不是，则可以中止搜索，如果存在则需要开始搜索，搜索单词的第二个字符，该字符必须在第一个字符的块周围。

我做了一些数学运算，发现它总是以“i-1和j-1”为例，作为周围区块的左上角。 我解决了这个问题，但似乎无法找到单词…而且，如果周围有2个“e”，我不知道如何搜索每个“e”的单词。 这是我到目前为止的代码：

这是我目前最重要的课程，Gameboard类

public class Gameboard { private List dices = new ArrayList(); private final int boardSize; private String[][] board; private boolean [][] blocksAvailable; private Random random = new Random(); public GameBoard() { // Making the board with a given size (will be changeable later but is "4" for now) boardSize = 4; board = new String[boardSize][boardSize]; blocksAvailable = new boolean[boardSize][boardSize]; for(int i = 0; i < boardSize; i++) { for(int j = 0; j < boardSize; j++) { blocksAvailable[i][j] = true; } } } public String[][] getBoard() { return board; } public int getFullSize() { return boardSize*boardSize; } public void makeBoard() { //random "side up" for each dice for(int i = 0; i < dices.size(); i++) { dices.get(i).setSideUp(); } // Shuffle all dices Collections.shuffle(dices); // Fill the board with the values of the dices int counter = 0; for(int i = 0; i < boardSize; i++) { for(int j = 0; j < boardSize; j++) { board[i][j] = dices.get(counter++).getSideUp(); } } } public String showBoard() { //Show the board, each block divided by "|" String str = ""; for(int i = 0; i < boardSize; i++) { for(int j = 0; j < boardSize; j++) { str += String.format("|%s|", board[i][j].toString()); if(j == 3) { str += "\n"; } } } return str; } public void addDices() { dices.add(new dice("R", "I", "F", "O", "B", "X")); dices.add(new dice("I", "F", "E", "H", "E", "Y")); dices.add(new dice("D", "E", "N", "O", "W", "S")); dices.add(new dice("U", "T", "O", "K", "N", "D")); dices.add(new dice("H", "M", "S", "R", "A", "O")); dices.add(new dice("L", "U", "P", "E", "T", "S")); dices.add(new dice("A", "C", "I", "T", "O", "A")); dices.add(new dice("Y", "L", "G", "K", "U", "E")); dices.add(new dice("Q", "B", "M", "J", "O", "A")); dices.add(new dice("E", "H", "I", "S", "P", "N")); dices.add(new dice("V", "E", "T", "I", "G", "N")); dices.add(new dice("B", "A", "L", "I", "Y", "T")); dices.add(new dice("E", "Z", "A", "V", "N", "D")); dices.add(new dice("R", "A", "L", "E", "S", "C")); dices.add(new dice("U", "W", "I", "L", "R", "G")); dices.add(new dice("P", "A", "C", "E", "M", "D")); } public boolean searchWord(String word) { String wordUp = woord.toUpperCase(); String firstLetter = Character.toString(wordUp.charAt(0)); for(int i = 0; i < boardSize;i++) { for(int j = 0; j < boardSize;j++) { if(firstLetter.equals(board[i][j]) == true) { int a = i; int b = j; String theLetter = ""; // First letter found, continue search for(int h = 1; h  -1) { a = values[0]; b = values[1]; } else { return false; } } return true; } } } return false; } public int[] searchLetter(String letter, int i, int j) { int[] values = new int[2]; try{if(board[i-1][j-1].equals(letter) && blocksAvailable[i-1][j-1] == true) { values[0] = i-1; values[1] = j-1; blocksAvailable[i-1][j-1] = false; } else if(board[i-1][j].equals(letter) && blocksAvailable[i-1][j] == true) { values[0] = i-1; values[1] = j; blocksAvailable[i-1][j] = false; } else if(board[i-1][j+1].equals(letter) && blocksAvailable[i-1][j+1] == true) { values[0] = i-1; values[1] = j+1; blocksAvailable[i-1][j+1] = false; } else if(board[i][j-1].equals(letter) && blocksAvailable[i][j-1] == true) { values[0] = i; values[1] = j-1; blocksAvailable[i][j-1] = false; } else if(board[i][j+1].equals(letter) && blocksAvailable[i][j+1] == true) { values[0] = i; values[1] = j+1; blocksAvailable[i][j+1] = false; } else if(board[i+1][j-1].equals(letter) && blocksAvailable[i+1][j-1] == true) { values[0] = i+1; values[1] = j-1; blocksAvailable[i+1][j+1] = false; } else if(board[i+1][j].equals(letter) && blocksAvailable[i+1][j] == true) { values[0] = i+1; values[1] = j; blocksAvailable[i+1][j] = false; } else if(board[i+1][j+1].equals(letter) && blocksAvailable[i+1][j+1] == true) { values[0] = i+1; values[1] = j+1; blocksAvailable[i+1][j+1] = false; } else { values[0] = -1; // If not found, negative values, easy to check in searchWord if letter was found values[1] = -1; }}catch (ArrayIndexOutOfBoundsException e) { } return values; } } 

Answer 1

这可能会被删除，因为我不会回答你的问题。 但请，请相当，使用：

 // instead of: board[i-1][j-1] public String getBoardValue(int x, int y) { if (x<0 || x>=boardSize) return ""; if (y<0 || y>=boardSize) return ""; return board[x][y]; } 

使用这种辅助方法你会

• 确保不抛出IndexArrayOutOfBoundsException
• 始终具有非空板值

Answer 2

好吧，你问的问题有点复杂。你必须看看你的Array中所有可能的方向。我建议你看看迷你项目并看看它们的评估logic 。你可以在谷歌上找到很多项目例如http://1000projects.org/java-projects-gaming.html

我不是要求你复制粘贴，而只是想知道以正确的方式做事。 几年前我用c/c++制作了一个XO游戏，可以给你代码（如果你想的话）检查x和o的组合（你可以看出代码，语法差别不大）。

Answer 3

您的方法searchLetter可以重写为更容易理解。

 public boolean isValid(int x, int y) { return x>= 0 && x < boardSize && y >=0 && y < boardSize; } public int[] searchLetter(String letter, int i, int j) { int[] values = new int[2]; //initialization as not found. values[0] = -1; values[1] = -1; for(int ix = i-1; ix <= i+1 ; ix++){ for(int jx = j-1; jx <= j+1 ; jx++){ if(i == ix && j == jx) //skip the cell from were the search is performed continue; if(isValid(ix,jx) && board[ix][jx].equals(letter) && blocksAvailable[ix][jx] == true) { values[0] = ix; values[1] = jx; blocksAvailable[ix][jx] = false; //early return return values; } } return values; } 

即使没有评论，读者也会暗示这是某种邻近的搜索。

事实是你的算法应该返回一个可能的下一个位置的列表。上面的代码返回第一次出现。 如果您将每对索引放在列表中而不是返回第一个索引，您将看到所有候选字母。 在这样做的同时，您将实现呼吸优先搜索的getNeighbour或adjancentVertexes 。

Answer 4

一个提示：一旦找到首字母，而不是逐个查找下一个字母，只需计算从该点可以得到的8个相同长度的单词。 您可能会发现少于8个，具体取决于该信函在董事会中的位置。 一旦你能够在一个方向上找到它，就可以更容易地将该逻辑转换为其他可能的方向。 然后你只需要比较这些单词，如果没有匹配，找到首字母并重复相同的过程。

Answer 5

我在接受采访时被问到这个问题，我没有多少时间，所以我向采访员解释了我将如何解决这个问题。 他的回答似乎没问题，甚至没有让我尝试编码，可能是因为他知道这个问题不像看起来那么微不足道，而且我们没有足够的时间。 在我的采访结束后，我在家尝试了一下，但我的解决方案有一些错误。 一直在考虑它并提出我之前发布的想法，然后注意到这篇文章是3岁，所以我决定编写它。 此解决方案有效，但仍有改进的余地：

 import java.util.LinkedHashSet; import java.util.Set; public class StringsArrays { public static void main(String[] args) { final char[][] matrix = new char[4][4]; matrix[0] = new char[] { 'G', 'A', 'B', 'C' }; matrix[1] = new char[] { 'O', 'O', 'E', 'F' }; matrix[2] = new char[] { 'O', 'H', 'O', 'I' }; matrix[3] = new char[] { 'J', 'K', 'L', 'D' }; System.out.println(search("JOOG", matrix)); //N System.out.println(search("BEOL", matrix)); //S System.out.println(search("AB", matrix)); //E System.out.println(search("FE", matrix)); //W System.out.println(search("HEC", matrix)); //NE System.out.println(search("DOOG", matrix)); //NW System.out.println(search("GOOD", matrix)); //SE System.out.println(search("FOK", matrix)); //SW System.out.println(search("HO", matrix)); } public static boolean search(final String word, char[][] matrix) { final char firstLetter = word.charAt(0); for (int y = 0; y < matrix.length; y++) { for (int x = 0; x < matrix[y].length; x++) { if (matrix[y][x] == firstLetter) { final Set words = readInAllDirections(word.length(), x, y, matrix); if (words.contains(word)) { return true; } } } } return false; } enum Direction { NORTH, SOUTH, EAST, WEST, NORTH_EAST, NORTH_WEST, SOUTH_EAST, SOUTH_WEST } private static Set readInAllDirections(final int length, final int x, final int y, final char[][] matrix) { final Set words = new LinkedHashSet<>(); for (final Direction direction : Direction.values()) { words.add(readWord(length, x, y, matrix, direction)); } return words; } private static String readWord(final int length, final int xBegin, final int yBegin, final char[][] matrix, final Direction direction) { final int xEnd = getXEnd(xBegin, length, direction); final int yEnd = getYEnd(yBegin, length, direction); int x; int y; final StringBuilder matrixWord = new StringBuilder(); if (direction == Direction.SOUTH) { if (yEnd > matrix.length-1) { return null; } for (y = yBegin; y <= yEnd; y++) { matrixWord.append(matrix[y][xBegin]); } } if (direction == Direction.NORTH) { if (yEnd < 0) { return null; } for (y = yBegin; y >= yEnd; y--) { matrixWord.append(matrix[y][xBegin]); } } if (direction == Direction.EAST) { if (xEnd > matrix[yBegin].length-1) { return null; } for (x = xBegin; x <= xEnd; x++) { matrixWord.append(matrix[yBegin][x]); } } if (direction == Direction.WEST) { if (xEnd < 0) { return null; } for (x = xBegin; x >= xEnd; x--) { matrixWord.append(matrix[yBegin][x]); } } if (direction == Direction.SOUTH_EAST) { if (yEnd > matrix.length-1 || xEnd > matrix[yBegin].length-1) { return null; } x = xBegin; y = yBegin; while (y <= yEnd && x <= xEnd) { matrixWord.append(matrix[y][x]); y++; x++; } } if (direction == Direction.SOUTH_WEST) { if (yEnd > matrix.length-1 || xEnd < 0) { return null; } x = xBegin; y = yBegin; while (y <= yEnd && x >= xEnd) { matrixWord.append(matrix[y][x]); y++; x--; } } if (direction == Direction.NORTH_EAST) { if (yEnd < 0 || xEnd > matrix[yBegin].length-1) { return null; } x = xBegin; y = yBegin; while (y >= yEnd && x <= xEnd) { matrixWord.append(matrix[y][x]); y--; x++; } } if (direction == Direction.NORTH_WEST) { if (yEnd < 0 || xEnd < 0) { return null; } x = xBegin; y = yBegin; while (y >= yEnd && x >= xEnd) { matrixWord.append(matrix[y][x]); y--; x--; } } return matrixWord.toString(); } private static int getYEnd(final int y, final int length, final Direction direction) { if (direction == Direction.SOUTH || direction == Direction.SOUTH_EAST || direction == Direction.SOUTH_WEST) { // y0 + length + ? = y1 return y + length - 1; } if (direction == Direction.NORTH || direction == Direction.NORTH_EAST || direction == Direction.NORTH_WEST) { // y0 - length + ? = y1 return y - length + 1; } // direction == Direction.EAST || direction == Direction.WEST) return y; } private static int getXEnd(final int x, final int length, final Direction direction) { if (direction == Direction.EAST || direction == Direction.NORTH_EAST || direction == Direction.SOUTH_EAST) { // x0 + length + ? = x1 return x + length - 1; } if (direction == Direction.WEST || direction == Direction.NORTH_WEST || direction == Direction.SOUTH_WEST) { // x0 - length + ? = x1 return x - length + 1; } // direction == Direction.NORTH || direction == Direction.SOUTH) return x; } }