我有一项艰巨的任务。我需要在二维数组中匹配“stringbuilder”单元格时将单词写入其中。这意味着我必须找到完整的单词,避免重复的单元格。为了更好的理解,我会附上一张照片,在黄色单元格中正确遍历,其中红色单元格是错误的路径。
结论如下:[0,2]->[1,2]->[2,2]->[2,3]->[2,4]->[3,4]->[4,4]->[5,4]->[5,3]->[5,2]->[5,1]->[4,1]->[4,0]->[5,0]现在我的结论是:[5,0]->[4,0]->[4,1]->[4,2]->[3,2]->[3,1]->[2,2]->[1,2]
我不明白故障在哪里,怎么解决,请帮忙。
我的代码:
public class GFS {
private static int R;
private static int C;
private static int[] x = {-1, 0, 1, 0};
private static int[] y = {0, 1, 0, -1};
private static StringBuilder stringBuilder = new StringBuilder();
private static int indexForWord = 1;
public static void main(String[] args) {
R = 7;
C = 7;
/*String word = "BOBA";
String cross = "QWBOABOBGSBSERTY";*/
/*String word = "KING";
String cross = "QLGNAEKIRLRNGEAE";*/
/*String word = "APPLE";
String cross = "UKJVXNAPBXELPLHVNLDKBVVNM";*/
String word = "DISABILITATING";
String cross = "FBDHBAAGNITISTDASABIDDBITILBNILALASGTATIGIYGNTGND";
char[][] grid = createMatrix(cross);
search2D(grid, word, 2, 0);
System.out.println(stringBuilder.toString());
}
static char[][] createMatrix(String input) {
char[][] newArr = new char[R][C];
int index = 0;
for (int i = 0; i < newArr.length; i++) {
for (int j = 0; j < newArr.length; j++) {
newArr[i][j] = input.charAt(index++);
}
}
return newArr;
}
static void print(char[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid.length; j++) {
System.out.print(grid[i][j] + " ");
}
System.out.println();
}
}
static boolean search2D(char[][] grid, String word, int positionX, int positionY) {
char oldChar = grid[positionY][positionX];
if (indexForWord >= word.length()) {
return true;
}
int top = positionY - 1 < 0 ? positionY : positionY - 1;
int bottom = positionY + 1 >= grid.length ? positionY : positionY + 1;
int right = positionX + 1 >= grid.length ? positionX : positionX + 1;
int left = positionX - 1 < 0 ? positionX : positionX - 1;
if (grid[top][positionX] == word.charAt(indexForWord)) {
indexForWord++;
grid[positionY][positionX] = ' ';
boolean check = search2D(grid, word, positionX, top);
if (check) {
stringBuilder.append("[").append(top).append(", ").append(positionX).append("]");
return true;
} else {
for (int j = indexForWord; j >= 0; j--) {
if (word.charAt(j) == oldChar) {
indexForWord = j + 1;
grid[positionY][positionX] = oldChar;
break;
}
}
}
}
if (grid[bottom][positionX] == word.charAt(indexForWord)) {
indexForWord++;
grid[positionY][positionX] = ' ';
boolean check = search2D(grid, word, positionX, bottom);
if (check) {
stringBuilder.append("[").append(bottom).append(", ").append(positionX).append("]");
return true;
} else {
for (int j = indexForWord; j >= 0; j--) {
if (word.charAt(j) == oldChar) {
indexForWord = j + 1;
grid[positionY][positionX] = oldChar;
break;
}
}
}
}
if (grid[positionY][left] == word.charAt(indexForWord)) {
indexForWord++;
grid[positionY][positionX] = ' ';
boolean check = search2D(grid, word, left, positionY);
if (check) {
stringBuilder.append("[").append(positionY).append(", ").append(left).append("]");
return true;
} else {
for (int j = indexForWord; j >= 0; j--) {
if (word.charAt(j) == oldChar) {
indexForWord = j + 1;
grid[positionY][positionX] = oldChar;
break;
}
}
}
}
if (grid[positionY][right] == word.charAt(indexForWord)) {
indexForWord++;
grid[positionY][positionX] = ' ';
boolean check = search2D(grid, word, right, positionY);
if (check) {
stringBuilder.append("[").append(positionY).append(", ").append(right).append("]");
return true;
} else {
for (int j = indexForWord; j >= 0; j--) {
if (word.charAt(j) == oldChar) {
indexForWord = j + 1;
grid[positionY][positionX] = oldChar;
break;
}
}
}
}
return false;
}
}
2条答案
按热度按时间o4tp2gmn1#
这是因为
indexForWord
当从错误的路径回溯并且存在重复字符时设置不正确(在您的情况下,是t)相反,只要每一次退后一步就足够了
check
为假(在所有4种情况下):结果也是相反的([5,0]->[4,0]->[4,1]->[5,1]等等),所以你必须反转它或者想出另一种方法。
watbbzwu2#
除了bahij所说的:
应使用0而不是1初始化。
结合bahij的解决方案,这个
(不幸的是,我不能评论他/她的答案,因为我没有足够的声誉哈哈)