Harrington Web

Robot moving across a NxM matrix.

Thursday, June 5, 2014

Lets say I have a matrix that is a 2 dimensional array of NxM elements and the Robot needs to find all the ways from the top left corner all the way to the bottom right corner. Now the Robot it self has some rules to follow on the way. The Robot can move up, down, left, right in order to get there. However the Robot may not move over the same square more than once.

def robot(matrix,n ,m)
  return 0 if n<0 || m<0 || n>matrix.length-1 || m>matrix.length-1
  return 0 if matrix[n][m] == 1
  return 1 if n==m && n==0
  count=0
  tmp=matrix
  tmp[n][m]=1
  count+=robot(tmp, n+1, m) #right
  count+=robot(tmp, n-1, m) #left
  count+=robot(tmp, n, m+1) #up
  count+=robot(tmp, n, m-1) #down
  tmp[n][m]=0
  return count
end

Now lets say that you have the same size matrix but the Robot can only move down and left.

def robot(matrix,n ,m)
  return 0 if n<0 || m<0 || n>matrix.length-1 || m>matrix.length-1
  return 0 if matrix[n][m] == 1
  return 1 if n==m && n==0
  count=0
  tmp=matrix
  tmp[n][m]=1
  count+=robot(tmp, n-1, m) #left
  count+=robot(tmp, n, m-1) #down
  tmp[n][m]=0
  return count
end