I'm trying to find all the paths in the maze where the only valid moves are going right ("H") or doing down ("V"). I want to return a list of strings of these paths.
My code currently does not return a list of these strings and I think the error is in trying to using the same String object to build the answer recursively. If anyone could help me fix that (or any other errors they might see) I would really appreciate it!
I considered making a Coordinate class, is this the right approach? If so, I'm not sure how to use this class to make the proper string. This is what I thought the class could look like:
public static class Coordinate {
public int row, col;
public String path;
public Coordinate (int row, int col) {
this.row = row;
this.col = col;
path = new String();
}
public addLetter(String s) {
path = path + s;
}
}
An example of what the question is asking, if my matrix is of size 3:
0 1 2
0 X H H
1 V
2 V
0 1 2
0 X H
1 V H
2 V
0 1 2
0 X H
1 V
2 V H
0 1 2
0 X
1 V H H
2 V
0 1 2
0 X
1 V H
2 V H
0 1 2
0 X
1 V
2 V H H
And all the possible strings are:
- HHVV, HVHV, HVVH, VHHV, VHVH, VVHH
So if the input n is equal to 3, the function should return a list of strings ["HHVV", "HVHV", "HVVH", "VHHV", "VHVH", "VVHH"].
If the input n is 2, the function should return: ["HV", "VH"].
class Result {
public static List<String> getSafePaths(int n) {
//do a dfs on the graph
List<String> paths = new ArrayList<>();
int er = n - 1;
int ec = n - 1;
int[][] matrix = new int[n][n];
matrix[0][0] = 2; //all visited nodes changed to two
getPaths(matrix, 0, 0, er, ec, paths, "");
return paths;
}
public static void getPaths(int[][] matrix, int sr, int sc, int er, int ec, List<String> paths, String s) {
if(sr == er && sc == ec) {
paths.add(new String(s));
}
final int[][] SHIFTS = {
{0, 1}, //go right
{1,0} // go down
};
for(int[] shift : SHIFTS) {
int right = -1;
int down = -1;
//are we going down or right? Need this to add correct letter
if(shift[0] == 0) {
right = 1;
}
else {
down = 1;
}
String letter = valid(matrix, sr + shift[0], sc + shift[1], right, down);
if(letter != null) {
if(letter == "H") {
s = s + "H";
}
if(letter == "V") {
s = s + "V";
}
matrix[sr + shift[0]][sc + shift[1]] = 2;
getPaths(matrix, sr + shift[0], sc + shift[1], er, ec, paths, s);
}
}
}
public static String valid(int[][] matrix, int sr, int sc, int right, int down) {
if(sr >= 0 && sr < matrix.length && sc >= 0 && sc < matrix[sr].length && matrix[sr][sc] != 2) {
if(right == 1) {
return "H";
}
else {
return "V";
}
}
return null;
}
}
The main issue (but certainly not the only one) is the marking of visited position (it is marked by setting the value of matrix to 2.).
Once a position is marked by 2, the following searches can not include this position in the path.
Think of the target position for example. After it has been reached, it is marked by 2 which means no following search can get to it anymore. This is why paths contain only one path when search is completed.
In fact, in this case marking visited position is not needed at all. The only possible movements are down and right, so the search can not return to the same position twice.
Simply comment out matrix[currentRow + shift[0]][currentColumn + shift[1]] = 2; to get more paths (and reveal more bugs).
/* check for equality between strings by letter.equals("H")
if(letter == "H") {
s = s + "H";
}
if(letter == "V") {
s = s + "V";
}
*/
//the two if blocks are not needed. letter can only be V or H so simply do:
s=s+letter; //or s+=letter or s=s.concat(letter)