下面是我的代码片段:package com.dynamicprogramming;
import java.util.ArrayList;
import java.util.List;
public class BoogleProblem {
public static int[] Path_Row = {0, 0, 1, 1, -1, 1, -1, -1};
public static int[] Path_Col = {1, -1, -1, 1, 1, 0, 0, -1};
public static void findWord(char[][] board, boolean[][] visited, int row, int col, String word,
List<String> englishDictionary) {
if (englishDictionary.contains(word)) {
System.out.println(word);
}
if (board.length == word.length()) {
return;
}
visited[row][col] = true;
for (int index = 0 ; index < board.length; index++) {
int rowNew = row + Path_Row[index];
int colNew = col + Path_Col[index];
if (ifValid(rowNew, colNew, visited)) {
visited[rowNew][colNew] = true;
findWord(board, visited, rowNew, colNew, word + board[rowNew][colNew], englishDictionary);
// Backtracking logic goes here
visited[rowNew][colNew] = false;
}
}
}
public static boolean ifValid(int row, int col, boolean[][] visited) {
if ((row >= 0) && (row < 3) && (col >= 0) && (col < 3) && !visited[row][col]) {
return true;
} else {
return false;
}
}
public static void main(String[] args) {
char[][] board = {{'G', 'I', 'Z'},
{'U', 'E', 'K'},
{'Q', 'S', 'E'}};
boolean[][] visited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length ; i++) {
for (int j = 0; j < board[0].length; j++) {
visited[i][j] = false;
}
}
List<String> englishDictionary = new ArrayList<String>();
englishDictionary.add("GEEKS");
englishDictionary.add("QUIZ");
englishDictionary.add("FOR");
englishDictionary.add("GO");
String word = "";
for (int i = 0; i < board.length; i++) {
for (int j = 0 ; j < board[0].length; j++) {
findWord(board, visited, 0, 0, word + board[i][j], englishDictionary);
}
}
}
}
这是行不通的&什么也没做。正如我所观察到的,在字符串多于2个字符的大多数情况下,ifvalid()方法都返回false。请告诉我,这里出了什么问题。
1条答案
按热度按时间fdbelqdn1#
试试这个。
输出