I'm trying to write a program that outputs (in the console) all possible paths (in (x1,x1) --> (x2,x2) --> etc.. format) for navigating a grid of size NxN, from top-left to bottom-right; i.e. from (0,0) to (N-1,N-1). You can only move down or right; i.e. from (0,0) to (0,1) or to (1,0). I want the program to output each time a full path set is found (i.e. all moves from top-left to bottom-right), and what that path set is.
It seems as though the best way to write this is with a recursive method inputting each move into an arrayList (see the buildPath method - the last method in the program), which is where I'm having trouble.
To make it slightly more complicated, I'm also generating random grid positions that are "off-limits" and as such can't be passed through. That said, I can probably work that part out for myself once we/I figure out how to actually get the thing working with any paths at all.
How would I implement a recursive method to determine which paths are possible? Any help is appreciated (even pseudo-code would be better than nothing)!
Here is my code so far (the simple bits are in pseudo-code to make it easier to work through, but let me know if I should put the full code in):
import java.util.*;
public class RecursiveAlgorithm {
public static ArrayList<Integer> allPaths = new ArrayList<Integer>();
public static ArrayList<String> pathSet = new ArrayList<String>();
public static int path;
public static int N, M, x = 0, y = 0;
public static String nString, mString;
public static boolean grid[][];
public static int right, down;
@SuppressWarnings("resource")
public static void main(String[] args) {
//sets the current position to (0,0)
right = 0;
down = 0;
Input value of N (size of grid)
Input value of M (number of off-limits locations)
offLimits(N, M); //calls offLimits method to randomly generate off-limits locations
buildPath(right, down, allPaths, N); //calls buildPath method
}
public static void offLimits (int N, int M) {
int mCount = 0;
if (M == 0){
} else {
while (mCount < (M + 1)) {
//int range1 = (max - min) + 1;
int range1 = ((N-1) - 1) + 1;
int range2 = ((N-1) - 0) + 1;
int random1 = (int)((Math.random() * range1) + 1);
int random2 = (int)(Math.random() * range2);
//if an 'off-limits' point is generated at the finish point, move it to either 1 place to the left or 1 place above
if ((random1 == N-1) && (random2 == N-1)) {
int switchSelect = (int)(Math.random() * 2);
while (switchSelect > 0) {
switch (switchSelect){
case 1: random1--;
break;
case 2: random2--;
break;
}
}
}
//sets a grid position to 'off-limits' (i.e. random1 = 1, random2 = 2 --> (1, 2) is 'off-limits')
grid[random1][random2] = true;
//counts the amount of off-limits grid locations generated
mCount++;
}
}
}
public static ArrayList<String> buildPath (int right, int down, ArrayList<Integer> allPaths, int N) {
//Updates path with current location (right, down)
/***** FROM HERE ON IS WHERE I AM HAVING TROUBLE *****/
//Stopping Condition
if ((right == N-1) && (down == N-1)) { //robot cannot go right
allPaths.add(path);
return pathSet;
}
//Recursive Steps
if (right == N-1) { //robot cannot go right
buildPath (right, down + 1, allPaths, N);
} else if (down == N-1) { //robot cannot go down
buildPath (right + 1, down, allPaths, N);
} else { //robot CAN go right or go down
buildPath (right + 1, down, allPaths, N);
//pathSet.add(Integer.toString(right));
//pathSet.add(Integer.toString(down));
buildPath (right, down + 1, allPaths, N);
if (grid[x][y] == false) {
//valid new position (substitute x and y for proposed new path step)
} else if (grid[x][y] == true) {
//off-limits position (substitute x and y for proposed new path step)
}
}
return pathSet;
}
}
