I have a difficult task. I need to write words to "stringBuilder" cells when they match in a two-dimensional array. This means that I have to find the complete word avoiding duplicate cells. For a better understanding, I will attach a photo of the correct traversal in yellow cells, where red cells are the wrong path.
The conclusion should be as follows: [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] Now my conclusion is: [5, 0]->[4, 0]->[4, 1]->[4, 2]->[3, 2]->[3, 1]->[2, 1]->[2, 2]->[1, 2]
I can't understand where the failure is and how to fix it, please help.
My code:
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;
}
}