Wednesday, July 30, 2014

Matrix paths from start to end traversing unoccupied cells

public class CoOrd
{
int X;
int Y;
public CoOrd(int x, int y)
{
X = x;
Y = y;
}
}

public static ArrayList getAllPaths(int[][] matrix, CoOrd start, CoOrd end)
{
ArrayList paths = new ArrayList();
getPaths(matrix, start, end, paths);
return paths; //assumings callers check the return ArrayList length
}

public static void getPaths(int[][] matrix, CoOrd start, CoOrd end, ArrayList paths)
{
if(start.X == end.X && start.Y == end.Y) //return when start meets end
{
return;
}
if(matrix[Start.X, Start.Y] == 0) //assuming 0 is an unoccupied cell and rest are occupied
{
paths.add(start);
}
else
{
/recurse right
CoOrd X1point = new CoOrd(start.X+1,start.Y);
getPaths(matrix, X1point, end, paths);

//recurse up
CoOrd Y1point = new CoOrd(start.X,start.Y+1);
getPaths(matrix, Y1point, end, paths);
}
return;
}

1 comment: