1

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

我有一个带有骰子的 ArrayList,每个都有一个随机的“面朝上”,然后 ArrayList 被打乱,一个二维数组被每个面朝上的值填充。此时数组中充满了字符串,字符可能是更好的选择,但它很容易更改。

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

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

这是我此刻最重要的课,游戏板课

public class Gameboard {

private List<Dice> dices = new ArrayList<Dice>();
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 < hetWoord.length(); h++) {
                    theLetter = Character.toString(wordUp.charAt(h));
                    int[] values = searchLetter(theLetter, a, b);
                    if(values[0] > -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;
}
}
4

5 回答 5

7

这可能会被删除,因为我不会回答你的问题。但是请,非常请,使用:

// 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
  • 总是有一个非空的板值
于 2013-01-21T13:11:11.983 回答
0

好吧,你问的有点复杂。你必须查看你的单词中所有可能的方向Array。我建议你应该看看迷你项目,看看他们logic的评估。你可以在谷歌上找到很多项目。示例http://1000projects.org/java-projects-gaming.html

我不是要您复制粘贴,而是要了解以适当的方式做事。几年前我在 中制作了一个 XO 游戏c/c++,可以给你检查 x 和 o 组合的代码(如果你愿意的话)(你可以弄出代码,语法差别不大)。

于 2013-01-21T13:56:55.533 回答
0

您的方法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。

于 2013-01-21T15:19:43.390 回答
0

我在面试时被问到这个问题,我没有太多时间了,所以我向面试官解释了我将如何解决这个问题。他似乎对我的回答很满意,甚至没有要求我尝试编写代码,可能是因为他知道这个问题并不像看起来那么简单,而且我们没有足够的时间。面试结束后,我在家里试了一下,但我的解决方案有一些错误。一直在思考它并提出了我之前发布的想法,然后注意到这篇文章已经 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<String> 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<String> readInAllDirections(final int length, final int x, final int y, final char[][] matrix) {
        final Set<String> 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;
    }
}
于 2016-01-29T01:10:33.987 回答
0

一个提示:一旦你找到了第一个字母,而不是一个一个地寻找下一个字母,只需计算你可以从那个点得到的 8 个相同长度的可能单词。根据该字母在黑板上的位置,您可能会发现少于 8 个。一旦你能够为一个方向弄清楚这一点,将这个逻辑转换为其他可能的方向就会更容易。然后你只需要比较这些单词,如果没有匹配,找到首字母并重复相同的过程。

于 2016-01-28T22:08:07.937 回答