I'm trying to solve a problem on Project Euler (Project 16) using grid recursion and it isn't working out so well - I'm just ending up with what seems like an infinite loop. The goal is to count how many routes you can take to get from the top left of a 20x20 grid to the bottom right of the grid, so I start from the origin and placed a number in myGrid[20][20] that indicates it's at the bottom right corner.
private static int[][] myGrid;
public static int numRoutes(int x, int y){
if (x < 0 || x >= 20 || y < 0 || y>= 20){
return 0;
}
if (myGrid[x][y] == 1){
return 1;
}
int count = 0;
count += numRoutes(x+1, y);
count += numRoutes(x, y+1);
return count;
}
public static void main (String args[]) throws Exception{
myGrid = new int[21][21];
for (int i = 0; i < 21; i++){
Arrays.fill(myGrid[i], 0);
}
myGrid[20][20] = 1;
int num = numRoutes(0,0);
System.out.println(num);
}
This comprises most of my recursion, and I think that I have all of the appropriate base cases. Any thoughts on what's going wrong?
Aucun commentaire:
Enregistrer un commentaire