mercredi 1 juillet 2015

Grid Recursion Not Functioning

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