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;
}

Adding 3 linked lists in the correct order and returning result linked list

#define E_INVALID_PARAMETER -1

int getNumber(node* root)
{
if(root == NULL)
{
return E_INVALID_PARAMETER;
}

int ret = 0;
node* temp = root;
while(temp)
{
int data = temp->data;
//checks to find data is valid
ret = ret*10 + data;
temp = temp->next;
}
return ret;
}

node * createLL(int num)
{
node* head = null;
node* prev = null;

while(num)
{
int data = num % 10;
head = (node *)malloc(sizeof(node));
if(head == NULL)
{
return NULL;
}
head->data = data;
head->next = prev;
prev = head;
num = num/10;
}

return head;
}

node * sumList (node* a, node *b, node* c)
{
if(a == NULL || b == NULL || c == NULL)
{
return NULL;
}
int aNum = 0;
int bNum = 0;
int cNum = 0;

aNum = getNumber(a);
bNum = getNumber(b);
cNum = getNumber(c);

if(a == E_INVALID_PARAMETER || b == E_INVALID_PARAMETER || c == E_INVALID_PARAMETER)
{
return NULL;
}

return createLL(aNum + bNum + cNum);
}