ratInMaze

Consider a rat placed at (0, 0) in a square matrix m[][] of order n and has to reach the destination at (n-1, n-1). Your task is to complete the function ratInMaze() which returns a sorted array of strings denoting all the possible directions which the rat can take to reach the destination at (n-1, n-1). The directions in which the rat can move are ‘U'(up), ‘D'(down), ‘L’ (left), ‘R’ (right). Noted that the rat cannot turn back to previous cell.

Given a 2D-matrix with 0’s and 1’s fill in it. 0 means that cell is blocked and 1 means rat can move to that cell.

Find all the possible directions which the rat can take to reach the destination at (n-1, n-1), sorted in alphabetical order.

Example

• For m = [[1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1]], the output should be ratInMaze(m) = ['DDRDRR', 'DRDDRR'].
  
  For example
  1 0 0 0
  1 1 0 1
  1 1 0 0
  0 1 1 1
  For the above matrix the rat can reach the destination at (3, 3) from (0, 0) by two paths ie DRDDRR and DDRDRR
  when printed in sorted order we get ['DDRDRR', 'DRDDRR'].

Input/Output

• [execution time limit] 0.5 seconds 

• [input] array.array.int m

  Matrix of integer of the same length. Each value contain only 0 or 1.

  Constraints:
  
  1 ≤ m.length ≤ 16,
  
  1 ≤ m[i].length ≤ 16.

  m.length = m[0].length

• [output] array.string

  All the possible directions which the rat can take to reach the destination