我正在做一个应用程序,将找到所有的字,可以与相邻的瓷砖在一个4x4网格(Boggle)。我已经到了可以输入一串字母的地方,算法将在最佳时间内找到所有可用的单词。然而,我需要知道的不仅仅是有效的词,但他们的方块在黑板上的位置。
这里是主要的游戏类。该算法递归地从一个字母开始,然后检查是否存在以该字母加上其邻居开始的单词。如果不存在单词,路径将被阻塞,算法将继续到下一个字母。如果有一个单词带有该前缀,对该邻居做同样的事情。
import java.io.IOException;
import java.util.ArrayList;
public class Game {
private final int boardSize = 4;
private BoardSquare[][] squares;
private ArrayList<String> validWords;
private static WordTree trie;
private static int counter = 0;
private DevRunner runner;
public Game(String letters) throws IOException{
validWords = new ArrayList<String>();
runner = new DevRunner();
trie = new WordTree();
squares = new BoardSquare[boardSize][boardSize];
for (int y=0; y<boardSize; y++){
for (int x=0; x<boardSize; x++){
squares[x][y] = new BoardSquare(letters.charAt(y*boardSize + x), y*boardSize + x);
}
}
for (int y=0; y<boardSize; y++){
for (int x=0; x<boardSize; x++){
for (int a=-1; a<2; a++){
for (int b=-1; b<2; b++){
if (a == 0 && b == 0) continue;
if (x+b < 0 || y+a < 0) continue;
if (x+b > boardSize-1 || y+a > boardSize-1) continue;
squares[x][y].addNeighbor(squares[x+b][y+a]);
}
}
}
}
getPossibleCombinations();
System.out.println(counter + " words found.");
}
public void getPossibleCombinations(){
for (int y=0; y<boardSize; y++){
for (int x=0; x<boardSize; x++){
doNeigh(squares[x][y], "", new ArrayList<Integer>());
}
}
}
public void doNeigh(BoardSquare square, String path, ArrayList<Integer> locations) {
square.setIsActive(true);
path += square.getData();
locations.add(square.getPosition());
if (trie.has(path) != 0){
for (BoardSquare neighbor : square.getNeighbors()){
if (!neighbor.getIsActive()){
doNeigh(neighbor, path, locations);
};
}
}
if (trie.has(path) == 1 && !validWords.contains(path)){
System.out.print(path + " is a word! (");
validWords.add(path);
for (int i : locations){
System.out.print(i + " -> ");
}
System.out.print("\n");
sendWord(path);
counter++;
}
square.setIsActive(false);
}
public void sendWord(String s){
}
public static void main(String[] args){
try {
long t1 = System.currentTimeMillis();
Game g = new Game("SIOZTRTEBAINERLA");
long t2 = System.currentTimeMillis();
System.out.println("The algorithm took " + Long.toString(t2-t1) + " milliseconds to complete.");
} catch (IOException e) {
e.printStackTrace();
}
}
}
SITAR is a word! (0 -> 1 -> 2 -> 4 -> 5 -> 8 -> 9 -> 5 -> 2 -> 6 -> 8 -> 10 -> 6 -> 7 -> 11 -> 13 -> 14 -> 15 ->
SIT is a word! (0 -> 1 -> 2 -> 4 -> 5 -> 8 -> 9 -> 5 -> 2 -> 6 -> 8 -> 10 -> 6 -> 7 -> 11 -> 13 -> 14 -> 15 -> 6 -> 8 -> 10 -> 12 -> 13 -> 8 -> 10 -> 5 -> 6 -> 7 -> 11 -> 14 -> 15 -> 12 -> 14 -> 14 ->
SIR is a word! (0 -> 1 -> 2 -> 4 -> 5 -> 8 -> 9 -> 5 -> 2 -> 6 -> 8 -> 10 -> 6 -> 7 -> 11 -> 13 -> 14 -> 15 -> 6 -> 8 -> 10 -> 12 -> 13 -> 8 -> 10 -> 5 -> 6 -> 7 -> 11 -> 14 -> 15 -> 12 -> 14 -> 14 -> 5 -> 2 -> 3 -> 6 -> 7 -> 4 -> 6 -> 8 -> 9 -> 10 -> 6 -> 7 -> 9 -> 11 -> 6 -> 7 -> 14 -> 15 -> 13 -> 14 -> 15 ->
SITAR is a word! (0 -> 1 -> 4 -> 9 -> 5 ->
SIT is a word! (0 -> 1 -> 4 ->
SIR is a word! (0 -> 1 -> 5 ->
...
任何帮助都很感激,谢谢。
必须从Doneigh()
末尾的locations
中删除最后一个元素。否则,这条道路将无限增长。
NowCoder 题目描述 判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向上下左右移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如下面的矩阵包含了一条 bfce 路径。 解题思路 使用回溯法(backtracking)进行求解,它是一种暴力搜索方法,通过搜索所有可能的结果来求解问题。回溯法在一次搜
我目前正在做一个音频信号处理项目,需要在Java中的一个复杂矩阵上使用SVD。我当前的线性代数库是Apache Commons。但它只提供实矩阵的SVD,JAMA、JBLAS、EJML、ojAlgo都不支持复杂的SVD。 我一直在用一些技巧从一个等效的实矩阵中找到SVD。然而,当我重建矩阵时,这种技术对于虚部有很大的不准确性。
一、题目 请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中任意一格开始,每一步可以在矩阵中间向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。 举例分析 例如在下面的3*4的矩阵中包含一条字符串”bcced”的路径。但矩阵中不包含字符串“abcb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二格子之后,路径
我遇到的问题是: 机器人位于m x n网格的左上角。机器人只能在任何时间点向下或向右移动。机器人正试图到达网格的右下角。有多少种可能的独特路径? 我提交的代码是: 提交后,我知道我的代码只比其他提交的代码快21%。这意味着我的代码不是最优的。出于好奇,我检查了另一份提交的文件,它比我的要快得多。 更好的解决方案是: 如你所见,它的时间复杂度是线性的,而我的是二次的。但我无法理解背后的逻辑。
我正在尝试编写一个递归方法,它可以找到一个路径,而不需要回溯到一个int矩阵中的一个位置,这个矩阵包含值0,1。0可以踩,1不行。我也限制了一条超过50步的路径。 Location是一个具有行和列值(x,y)的对象。locationEquals是一个函数,如果两个位置相同,则返回true,否则返回false。map变量是我试图在其中找到路径的矩阵。 执行以下代码后'选项'为空,这意味着它没有找到方
我不知道该如何解决这个问题。我得到了一个有12个节点A-L的图。17个边缘连接它们。我被告知要找到从A到L的所有路径。我可以遍历一个节点多次,但只能遍历一次边。输出应该打印每个路径和路径总数。 例如,如果只有1个路径。输出应为: 我想一个递归的深度优先搜索函数应该可以解决这个问题,但我就是想不出一个打印每一条路径的方法。例如,如果我的函数找到一个路径ABDL并到达结尾L,它将打印ABDL。然后它回