Consider a rat placed at (0, 0) in a square matrix of order N * N. It has to reach the destination at (N - 1, N - 1). Find all possible paths that the rat can take to reach from source to destination. The directions in which the rat can move are 'U'(up), 'D'(down), 'L' (left), 'R' (right). Value 0 at a cell in the matrix represents that it is blocked and rat cannot move to it while value 1 at a cell in the matrix represents that rat can be travel through it.
Note: In a path, no cell can be visited more than one time. If the source cell is 0, the rat cannot move to any other cell.
Example 1:
Input:
N = 4
m[][] = {{1, 0, 0, 0},
         {1, 1, 0, 1}, 
         {1, 1, 0, 0},
         {0, 1, 1, 1}}
Output:
DDRDRR DRDDRR
Explanation:
The rat can reach the destination at 
(3, 3) from (0, 0) by two paths - DRDDRR 
and DDRDRR, when printed in sorted order 
we get DDRDRR DRDDRR.
Example 2:
Input:
N = 2
m[][] = {{1, 0},
         {1, 0}}
Output:
-1
Explanation:
No path exists and destination cell is 
blocked.
Your Task:  
You don't need to read input or print anything. Complete the function printPath() which takes N and 2D array m[ ][ ] as input parameters and returns the list of paths in lexicographically increasing order. 
Note: In case of no path, return an empty list. The driver will output "-1" automatically.
Expected Time Complexity: O((3^{N}^{^2})).
Expected Auxiliary Space: O(L * X), L = length of the path, X = number of paths.
Constraints:
2 ≤ N ≤ 5
0 ≤ m[i][j] ≤ 1

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Complete search

Starter code: #User function Template for python3



class Solution:

    def findPath(self, m, n):

        # code here

Solutions:
class Solution:

	def setup(self):
		global v
		v = [[0 for i in range(100)] for j in range(100)]
		global ans
		ans = []

	def path(self, arr, x, y, pth, n):
		if x == n - 1 and y == n - 1:
			global ans
			ans.append(pth)
			return
		global v
		if arr[x][y] == 0 or v[x][y] == 1:
			return
		v[x][y] = 1
		if x > 0:
			self.path(arr, x - 1, y, pth + 'U', n)
		if y > 0:
			self.path(arr, x, y - 1, pth + 'L', n)
		if x < n - 1:
			self.path(arr, x + 1, y, pth + 'D', n)
		if y < n - 1:
			self.path(arr, x, y + 1, pth + 'R', n)
		v[x][y] = 0

	def findPath(self, m, n):
		global ans
		ans = []
		if m[0][0] == 0 or m[n - 1][n - 1] == 0:
			return ans
		self.setup()
		self.path(m, 0, 0, '', n)
		ans.sort()
		return ans


class Solution:

	def findPath(self, m, n):
		ans = []

		def path_helper(i, j, m, n, vis, direction):
			if i == n - 1 and j == n - 1:
				vis[i][j] = 1
				ans.append(direction)
				vis[i][j] = 0
				return
			if i < 0 or j < 0 or i >= n or (j >= n) or (m[i][j] == 0) or (vis[i][j] == 1):
				return
			vis[i][j] = 1
			path_helper(i + 1, j, m, n, vis, direction + 'D')
			path_helper(i - 1, j, m, n, vis, direction + 'U')
			path_helper(i, j + 1, m, n, vis, direction + 'R')
			path_helper(i, j - 1, m, n, vis, direction + 'L')
			vis[i][j] = 0
			return
		vis = [[0 for j in range(n)] for i in range(n)]
		if m[0][0] == 1 and m[n - 1][n - 1] == 1:
			path_helper(0, 0, m, n, vis, '')
		return ans


class Solution:

	@staticmethod
	def findAllPaths(m, n, i, j, ans, path):
		if i < 0 or j < 0 or i >= n or (j >= n) or (not m[i][j]):
			return ans
		if i == n - 1 and j == n - 1:
			ans.append(path)
			return
		m[i][j] = 0
		Solution.findAllPaths(m, n, i + 1, j, ans, path + 'D')
		Solution.findAllPaths(m, n, i, j + 1, ans, path + 'R')
		Solution.findAllPaths(m, n, i - 1, j, ans, path + 'U')
		Solution.findAllPaths(m, n, i, j - 1, ans, path + 'L')
		m[i][j] = 1
		return ans

	def findPath(self, m, n):
		paths = Solution.findAllPaths(m, n, 0, 0, [], '')
		return paths


class Solution:

	def findPath(self, m, n):
		res = []
		visited = [[0 for i in range(n)] for j in range(n)]
		i = j = 0
		if m[i][j] == 1:
			self.func(m, n, i, j, '', res, visited)
		return res

	def func(self, m, n, i, j, sub, res, visited):
		if i == n - 1 and j == n - 1:
			res.append(sub)
			return
		if i + 1 < n and (not visited[i + 1][j]) and (m[i + 1][j] == 1):
			visited[i][j] = 1
			self.func(m, n, i + 1, j, sub + 'D', res, visited)
			visited[i][j] = 0
		if j - 1 >= 0 and (not visited[i][j - 1]) and (m[i][j - 1] == 1):
			visited[i][j] = 1
			self.func(m, n, i, j - 1, sub + 'L', res, visited)
			visited[i][j] = 0
		if j + 1 < n and (not visited[i][j + 1]) and (m[i][j + 1] == 1):
			visited[i][j] = 1
			self.func(m, n, i, j + 1, sub + 'R', res, visited)
			visited[i][j] = 0
		if i - 1 >= 0 and (not visited[i - 1][j]) and (m[i - 1][j] == 1):
			visited[i][j] = 1
			self.func(m, n, i - 1, j, sub + 'U', res, visited)
			visited[i][j] = 0


class Solution:

	def findPathHelper(self, i, j, a, n, ans, move, vis):
		if i == n - 1 and j == n - 1:
			ans.append(move)
			return
		if i + 1 < n and (not vis[i + 1][j]) and (a[i + 1][j] == 1):
			vis[i][j] = 1
			self.findPathHelper(i + 1, j, a, n, ans, move + 'D', vis)
			vis[i][j] = 0
		if j - 1 >= 0 and (not vis[i][j - 1]) and (a[i][j - 1] == 1):
			vis[i][j] = 1
			self.findPathHelper(i, j - 1, a, n, ans, move + 'L', vis)
			vis[i][j] = 0
		if j + 1 < n and (not vis[i][j + 1]) and (a[i][j + 1] == 1):
			vis[i][j] = 1
			self.findPathHelper(i, j + 1, a, n, ans, move + 'R', vis)
			vis[i][j] = 0
		if i - 1 >= 0 and (not vis[i - 1][j]) and (a[i - 1][j] == 1):
			vis[i][j] = 1
			self.findPathHelper(i - 1, j, a, n, ans, move + 'U', vis)
			vis[i][j] = 0

	def findPath(self, m, n):
		ans = []
		vis = [[0 for _ in range(n)] for _ in range(n)]
		if m[0][0] == 1:
			self.findPathHelper(0, 0, m, n, ans, '', vis)
		return ans


class Solution:

	def path(self, i, j, m, n, db, str):
		if i < 0 or j < 0 or i >= n or (j >= n) or (m[i][j] == 0):
			return
		if i == n - 1 and j == n - 1:
			db.append(str)
			return
		m[i][j] = 0
		self.path(i + 1, j, m, n, db, str + 'D')
		self.path(i, j + 1, m, n, db, str + 'R')
		self.path(i - 1, j, m, n, db, str + 'U')
		self.path(i, j - 1, m, n, db, str + 'L')
		str = ' '
		m[i][j] = 1

	def findPath(self, m, n):
		i = 0
		j = 0
		db = []
		self.path(i, j, m, n, db, '')
		return db


class Solution:

	def findPath(self, m, n):
		all_solutions = []
		paths = {'U': (-1, 0), 'D': (1, 0), 'R': (0, 1), 'L': (0, -1)}

		def solution(x, y, current_path):
			if m[x][y] == 0:
				return -1
			if x < 0 or y < 0 or x > n - 1 or (y > n - 1):
				return -1
			if (x, y) == (n - 1, n - 1):
				all_solutions.append(current_path)
				return
			for (dir, positions) in paths.items():
				_x = x + positions[0]
				_y = y + positions[1]
				if _x < 0 or _y < 0 or _x > n - 1 or (_y > n - 1) or (m[_x][_y] != 1):
					continue
				m[x][y] = 2
				solution(_x, _y, current_path + dir)
				m[x][y] = 1
		solution(0, 0, current_path='')
		return all_solutions


class Solution:

	def findPath(self, m, n):
		paths = []
		moves = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}

		def is_valid(row, col, m, n):
			if row >= n or row < 0 or col >= n or (col < 0):
				return False
			elif m[row][col] == 0:
				return False
			else:
				return True

		def solve(moves, temp, m, n, vis, row, col):
			if row == n - 1 and col == n - 1:
				paths.append(''.join(temp))
			for (k, v) in moves.items():
				(newRow, newCol) = (row + v[0], col + v[1])
				if is_valid(newRow, newCol, m, n) and (not vis[newRow][newCol]):
					temp.append(k)
					vis[newRow][newCol] = True
					solve(moves, temp, m, n, vis, newRow, newCol)
					vis[newRow][newCol] = False
					temp.pop()
		if m[0][0] == 1:
			vis = [[False for i in range(n)] for j in range(n)]
			vis[0][0] = True
			solve(moves, [], m, n, vis, 0, 0)
		return paths


fans = []
moves = [[0, 1, 'R'], [0, -1, 'L'], [1, 0, 'D'], [-1, 0, 'U']]

def valid(i, j, vis, arr):
	if i < 0 or j < 0 or i >= len(arr) or (j >= len(arr[0])) or ((i, j) in vis) or (arr[i][j] == 0):
		return False
	return True

def mgc(arr, i, j, vis, ans):
	global fans, moves
	if i == j and i == len(arr) - 1:
		fans.append(ans)
		return
	vis.add((i, j))
	for k in moves:
		if valid(k[0] + i, k[1] + j, vis, arr):
			mgc(arr, i + k[0], j + k[1], vis, ans + k[2])
	vis.remove((i, j))

class Solution:

	def findPath(self, m, n):
		global fans
		fans = []
		if m[0][0] == 0 or m[n - 1][n - 1] == 0:
			return []
		mgc(m, 0, 0, set(), '')
		return fans


class Solution:

	def findPath(self, m, n):
		res = []
		path = ''
		visited = [[0 for _ in range(n)] for _ in range(n)]
		if m[0][0] == 0 or m[n - 1][n - 1] == 0:
			return res

		def fp(i, j, path):
			if i == n - 1 and j == n - 1:
				res.append(path)
				return
			if i + 1 < n and m[i + 1][j] != 0 and (visited[i + 1][j] != 1):
				visited[i][j] = 1
				fp(i + 1, j, path + 'D')
				visited[i][j] = 0
			if j + 1 < n and m[i][j + 1] != 0 and (visited[i][j + 1] != 1):
				visited[i][j] = 1
				fp(i, j + 1, path + 'R')
				visited[i][j] = 0
			if i - 1 >= 0 and m[i - 1][j] != 0 and (visited[i - 1][j] != 1):
				visited[i][j] = 1
				fp(i - 1, j, path + 'U')
				visited[i][j] = 0
			if j - 1 >= 0 and m[i][j - 1] != 0 and (visited[i][j - 1] != 1):
				visited[i][j] = 1
				fp(i, j - 1, path + 'L')
				visited[i][j] = 0
		fp(0, 0, path)
		if len(res) == 0:
			return []
		res.sort()
		return res


def isValid(i, j, m, n, curr_ans, vis, fin_ans):
	return i >= 0 and j >= 0 and (i < n) and (j < n) and (m[i][j] == 1) and (vis[i][j] == False)

def findPathUtil(i, j, m, n, ans, vis, fin_ans):
	vis[i][j] = True
	if i == n - 1 and j == n - 1:
		fin_ans.append(ans)
	if isValid(i + 1, j, m, n, ans, vis, fin_ans):
		curr_ans = ans
		curr_ans += 'D'
		findPathUtil(i + 1, j, m, n, curr_ans, vis, fin_ans)
	if isValid(i - 1, j, m, n, ans, vis, fin_ans):
		curr_ans = ans
		curr_ans += 'U'
		findPathUtil(i - 1, j, m, n, curr_ans, vis, fin_ans)
	if isValid(i, j + 1, m, n, ans, vis, fin_ans):
		curr_ans = ans
		curr_ans += 'R'
		findPathUtil(i, j + 1, m, n, curr_ans, vis, fin_ans)
	if isValid(i, j - 1, m, n, ans, vis, fin_ans):
		curr_ans = ans
		curr_ans += 'L'
		findPathUtil(i, j - 1, m, n, curr_ans, vis, fin_ans)
	vis[i][j] = False

class Solution:

	def findPath(self, m, n):
		ans = ''
		if m[0][0] == 0:
			return [-1]
		vis = [[False for i in range(n)] for i in range(n)]
		fin_ans = []
		findPathUtil(0, 0, m, n, ans, vis, fin_ans)
		return fin_ans


class Solution:

	def findPath(self, m, n):
		result = []
		getPaths(m, n, result, '', 0, 0)
		return result

def getPaths(m, n, result, temp, r, c):
	if m[r][c] != 1:
		return
	m[r][c] = 2
	if r == n - 1 and c == n - 1:
		result.append(temp)
	nbrs = getNeighbours(m, r, c)
	for (row, col, dir) in nbrs:
		getPaths(m, n, result, temp + dir, row, col)
	m[r][c] = 1

def getNeighbours(m, r, c):
	nbrs = []
	if r > 0:
		nbrs.append((r - 1, c, 'U'))
	if r < len(m) - 1:
		nbrs.append((r + 1, c, 'D'))
	if c > 0:
		nbrs.append((r, c - 1, 'L'))
	if c < len(m[0]) - 1:
		nbrs.append((r, c + 1, 'R'))
	return nbrs


class Solution:

	def f(self, i, j, mat, n, ans, vis, s):
		if i == n - 1 and j == n - 1:
			ans.append(''.join(s))
			return
		if i < n - 1:
			if mat[i + 1][j] == 1 and vis[i + 1][j] == 0:
				s.append('D')
				vis[i + 1][j] = 1
				self.f(i + 1, j, mat, n, ans, vis, s)
				s.pop()
				vis[i + 1][j] = 0
		if j > 0:
			if mat[i][j - 1] == 1 and vis[i][j - 1] == 0:
				s.append('L')
				vis[i][j - 1] = 1
				self.f(i, j - 1, mat, n, ans, vis, s)
				s.pop()
				vis[i][j - 1] = 0
		if j < n - 1:
			if mat[i][j + 1] == 1 and vis[i][j + 1] == 0:
				s.append('R')
				vis[i][j + 1] = 1
				self.f(i, j + 1, mat, n, ans, vis, s)
				s.pop()
				vis[i][j + 1] = 0
		if i > 0:
			if mat[i - 1][j] == 1 and vis[i - 1][j] == 0:
				s.append('U')
				vis[i - 1][j] = 1
				self.f(i - 1, j, mat, n, ans, vis, s)
				s.pop()
				vis[i - 1][j] = 0

	def findPath(self, m, n):
		ans = []
		if m[0][0] == 0 or m[n - 1][n - 1] == 0:
			return ans
		vis = []
		for i in range(n):
			a = []
			for j in range(n):
				a.append(0)
			vis.append(a)
		vis[0][0] = 1
		self.f(0, 0, m, n, ans, vis, [])
		return ans


class Solution:

	def isValid(self, x, y, m, n):
		if x < 0 or y < 0 or x >= n or (y >= n):
			return False
		if m[x][y] == 0:
			return False
		return True

	def sol(self, x, y, m, n, path, visited, dest):
		if x == n - 1 and y == n - 1:
			dest.append(path)
			return True
		if visited[x][y] == 1:
			return False
		visited[x][y] = 1
		if Solution.isValid(self, x + 1, y, m, n):
			Solution.sol(self, x + 1, y, m, n, path + 'D', visited, dest)
		if Solution.isValid(self, x - 1, y, m, n):
			Solution.sol(self, x - 1, y, m, n, path + 'U', visited, dest)
		if Solution.isValid(self, x, y + 1, m, n):
			Solution.sol(self, x, y + 1, m, n, path + 'R', visited, dest)
		if Solution.isValid(self, x, y - 1, m, n):
			Solution.sol(self, x, y - 1, m, n, path + 'L', visited, dest)
		visited[x][y] = 0

	def findPath(self, m, n):
		dest = []
		visited = [[0] * n for _ in range(n)]
		if m[0][0] == 0 or m[n - 1][n - 1] == 0:
			return [-1]
		Solution().sol(0, 0, m, n, '', visited, dest)
		return [-1] if len(dest) == 0 else dest


class Solution:

	def getAns(self, m, n, i, j, res, ans):
		if i == n - 1 and j == n - 1:
			res.append(ans)
			return
		if i < 0 or j < 0 or j >= n or (i >= n) or (m[i][j] == 0):
			return
		c = m[i][j]
		m[i][j] = 0
		top = self.getAns(m, n, i - 1, j, res, ans + 'U')
		left = self.getAns(m, n, i, j - 1, res, ans + 'L')
		right = self.getAns(m, n, i, j + 1, res, ans + 'R')
		bot = self.getAns(m, n, i + 1, j, res, ans + 'D')
		m[i][j] = c

	def findPath(self, m, n):
		if m[n - 1][n - 1] == 0 or m[0][0] == 0:
			return [-1]
		res = []
		self.getAns(m, n, 0, 0, res, '')
		if len(res) > 0:
			return res
		else:
			return [-1]


class Solution:

	def safe(self, x, y, n, v, m):
		if (x >= 0 and x < n) and (y >= 0 and y < n) and (v[x][y] == 0) and (m[x][y] == 1):
			return 1
		else:
			return 0

	def sol(self, x, y, m, n, path, ans, v):
		if x == n - 1 and y == n - 1:
			ans.append(path)
			return
		v[x][y] = 1
		if self.safe(x, y + 1, n, v, m):
			self.sol(x, y + 1, m, n, path + 'R', ans, v)
		if self.safe(x + 1, y, n, v, m):
			self.sol(x + 1, y, m, n, path + 'D', ans, v)
		if self.safe(x, y - 1, n, v, m):
			self.sol(x, y - 1, m, n, path + 'L', ans, v)
		if self.safe(x - 1, y, n, v, m):
			self.sol(x - 1, y, m, n, path + 'U', ans, v)
		v[x][y] = 0

	def findPath(self, m, n):
		x = y = 0
		ans = []
		k = [0] * n
		v = []
		for i in range(n):
			v.append(k[:])
		if m[0][0] == 0:
			return ans
		self.sol(x, y, m, n, '', ans, v)
		return ans


class Solution:

	def path(self, i, j, path, res, grid, n, cache):
		if i == n - 1 and j == n - 1:
			res.append(path)
			return
		cache[i][j] = 1
		if i + 1 < n and grid[i + 1][j] != 0 and (cache[i + 1][j] != 1):
			self.path(i + 1, j, path + 'D', res, grid, n, cache)
		if j - 1 >= 0 and grid[i][j - 1] != 0 and (cache[i][j - 1] != 1):
			self.path(i, j - 1, path + 'L', res, grid, n, cache)
		if j + 1 < n and grid[i][j + 1] != 0 and (cache[i][j + 1] != 1):
			self.path(i, j + 1, path + 'R', res, grid, n, cache)
		if i - 1 >= 0 and grid[i - 1][j] != 0 and (cache[i - 1][j] != 1):
			self.path(i - 1, j, path + 'U', res, grid, n, cache)
		cache[i][j] = 0

	def findPath(self, m, n):
		if m[0][0] == 0 or m[-1][-1] == 0:
			return [-1]
		cache = [[0 for _ in range(n)] for _ in range(n)]
		res = []
		path = ''
		self.path(0, 0, path, res, m, n, cache)
		return res


class Solution:

	def findpaths(self, matrix, n, i, j, seq):
		if i == n - 1 and j == n - 1:
			self.res.append(seq)
			return
		if i < 0 or j < 0 or i == n or (j == n):
			return
		if matrix[i][j] == 0:
			return
		matrix[i][j] = 0
		for (direction, (movi, movj)) in self.directions.items():
			self.findpaths(matrix, n, i + movi, j + movj, seq + direction)
		matrix[i][j] = 1

	def findPath(self, matrix, n):
		if matrix[0][0] == 0 or matrix[-1][-1] == 0:
			return []
		self.res = []
		self.directions = {'R': (0, 1), 'L': (0, -1), 'D': (1, 0), 'U': (-1, 0)}
		self.findpaths(matrix, n, 0, 0, '')
		return self.res


class Solution:

	def findPath(self, m, n):
		if n == 0 or m[0][0] == 0 or m[n - 1][n - 1] == 0:
			return [-1]
		moves = [(-1, 0, 'U'), (1, 0, 'D'), (0, -1, 'L'), (0, 1, 'R')]
		result = []

		def dfs(r, c, slate):
			if r < 0 or r >= n or c < 0 or (c >= n) or (m[r][c] != 1):
				return
			if r == n - 1 and c == n - 1:
				result.append(slate)
			for (i, j, Dir) in moves:
				m[r][c] = 2
				dfs(r + i, c + j, slate + Dir)
				m[r][c] = 1
		dfs(0, 0, '')
		if result:
			return result
		else:
			return [-1]


class Solution:
	dirs = list()
	visited = list()

	def findPath(self, m, n):
		result = list()
		self.visited = [[0] * n for i in range(n)]
		self.dirs = [[0, 1], [1, 0], [-1, 0], [0, -1]]
		if m[0][0] == 1:
			self.helper(m, n, result, 0, 0, list())
		return result

	def helper(self, m, n, result, row, col, path):
		if row == n - 1 and col == n - 1:
			result.append(''.join(path))
			return
		nav = 'RDUL'
		for i in range(len(self.dirs)):
			d = self.dirs[i]
			nr = row + d[0]
			nc = col + d[1]
			if nr >= 0 and nr < n and (nc < n) and (nc >= 0) and (self.visited[nr][nc] == 0) and (m[nr][nc] == 1):
				self.visited[row][col] = 1
				path.append(nav[i])
				self.helper(m, n, result, nr, nc, path)
				path.pop()
				self.visited[row][col] = 0


class Solution:

	def findPath(self, m, n):
		self.res = []
		if m[0][0] == 0:
			return [-1]

		def check(ans, i, j, mat, N):
			if i < 0 or i >= N or j < 0 or (j >= N):
				return False
			if mat[i][j] == 0 or mat[i][j] == 2:
				return False
			if i == N - 1 and j == N - 1:
				self.res.append(ans)
				return
			mat[i][j] = 2
			check(ans + 'U', i - 1, j, mat, N)
			check(ans + 'R', i, j + 1, mat, N)
			check(ans + 'D', i + 1, j, mat, N)
			check(ans + 'L', i, j - 1, mat, N)
			mat[i][j] = 1
		check('', 0, 0, m, n)
		if not self.res:
			return [-1]
		return self.res


class Solution:

	def findPath(self, m, n):
		row = 0
		col = 0
		arr = []
		p = ''
		if m[n - 1][n - 1] == 0:
			return []

		def dfs(p, row, col, arr):
			if row == n - 1 and col == n - 1:
				arr.append(p)
				return
			if row < 0 or row >= n or col < 0 or (col >= n):
				return
			if m[row][col] != 1:
				return
			m[row][col] = -1
			dfs(p + 'D', row + 1, col, arr)
			dfs(p + 'R', row, col + 1, arr)
			dfs(p + 'U', row - 1, col, arr)
			dfs(p + 'L', row, col - 1, arr)
			m[row][col] = 1
		dfs(p, row, col, arr)
		return arr


class Solution(object):

	def findPath(self, board, n):

		def backtracking(row, col, combination):
			if not (0 <= row < n and 0 <= col < n):
				return
			if board[row][col] == 'V' or board[row][col] == 0:
				return
			if row == col == n - 1:
				result.append(''.join(combination))
				return
			for (rval, cval, direction) in directions:
				board[row][col] = 'V'
				combination.append(direction)
				backtracking(row + rval, col + cval, combination)
				combination.pop()
				board[row][col] = 1
		result = []
		if board[0][0] == 0 or board[n - 1][n - 1] == 0:
			return result
		directions = [(1, 0, 'D'), (0, -1, 'L'), (0, 1, 'R'), (-1, 0, 'U')]
		backtracking(0, 0, [])
		return result


def sol(row, col, n, mat, path, ans, dRow, dCol):
	if col == n - 1 and row == n - 1:
		ans.append(path)
		return ans
	d = 'DLRU'
	for i in range(4):
		nextRow = row + dRow[i]
		nextCol = col + dCol[i]
		if nextRow < n and nextCol < n and (nextRow >= 0) and (nextCol >= 0) and (mat[nextRow][nextCol] != 0):
			mat[row][col] = 0
			ans = sol(nextRow, nextCol, n, mat, path + d[i], ans, dRow, dCol)
			mat[row][col] = 1
	return ans

class Solution:

	def findPath(self, m, n):
		if m[0][0] == 0:
			return [-1]
		ans = []
		dRow = [1, 0, 0, -1]
		dCol = [0, -1, 1, 0]
		return sol(0, 0, n, m, '', ans, dRow, dCol)


def sol(row, col, n, mat, path, ans):
	if col == n - 1 and row == n - 1:
		ans.append(path)
		return ans
	last = ''
	if len(path) != 0:
		last = path[-1]
	if row != n - 1 and mat[row + 1][col] != 0 and (mat[row + 1][col] > 0):
		mat[row + 1][col] = -1
		ans = sol(row + 1, col, n, mat, path + 'D', ans)
		mat[row + 1][col] = 1
	if col != 0 and mat[row][col - 1] != 0 and (mat[row][col - 1] > 0):
		mat[row][col - 1] = -1
		ans = sol(row, col - 1, n, mat, path + 'L', ans)
		mat[row][col - 1] = 1
	if col != n - 1 and mat[row][col + 1] != 0 and (mat[row][col + 1] > 0):
		mat[row][col + 1] = -1
		ans = sol(row, col + 1, n, mat, path + 'R', ans)
		mat[row][col + 1] = 1
	if row != 0 and mat[row - 1][col] != 0 and (mat[row - 1][col] > 0):
		mat[row - 1][col] = -1
		ans = sol(row - 1, col, n, mat, path + 'U', ans)
		mat[row - 1][col] = 1
	return ans

class Solution:

	def findPath(self, m, n):
		if m[0][0] == 0:
			return [-1]
		ans = []
		m[0][0] = -1
		return sol(0, 0, n, m, '', ans)


from collections import deque

class Solution:

	def __findPathHelper(self, row, col, m, n):
		if m[row][col] == 0:
			return
		if row == n - 1 and col == n - 1:
			self.res.append(''.join(self.temp_sol))
			return
		m[row][col] = 0
		for (row_offset, col_offset, symb) in self.dirs:
			(next_row, next_col) = (row + row_offset, col + col_offset)
			if 0 <= next_row < n and 0 <= next_col < n:
				self.temp_sol.append(symb)
				self.__findPathHelper(next_row, next_col, m, n)
				self.temp_sol.pop()
		m[row][col] = 1

	def findPath(self, m, n):
		(self.res, self.temp_sol) = ([], deque())
		self.dirs = [(1, 0, 'D'), (0, -1, 'L'), (0, 1, 'R'), (-1, 0, 'U')]
		self.__findPathHelper(0, 0, m, n)
		return self.res


class Solution:

	def findPath(self, m, n):
		res = []
		vis = [[0] * n for i in range(n)]
		s = ''
		if m[0][0] == 0 or m[n - 1][n - 1] == 0:
			return res

		def dfs(r, c, vis, s):
			if r == n - 1 and c == n - 1:
				res.append(s)
				return
			if r < 0 or c < 0 or r >= n or (c >= n) or (vis[r][c] == 1) or (m[r][c] == 0):
				return
			vis[r][c] = 1
			dfs(r + 1, c, vis, s + 'D')
			dfs(r - 1, c, vis, s + 'U')
			dfs(r, c + 1, vis, s + 'R')
			dfs(r, c - 1, vis, s + 'L')
			vis[r][c] = 0
		dfs(0, 0, vis, s)
		res.sort()
		return res


class Solution:

	def findPath(self, m, n):
		(ans, dir, dl) = ([], [[1, 0], [0, -1], [0, 1], [-1, 0]], ['D', 'L', 'R', 'U'])

		def dfs(node, path):
			(i, j) = node
			if m[i][j] != 1:
				return
			if i == n - 1 and j == n - 1:
				ans.append(path)
				return
			m[i][j] = 2
			for d in range(4):
				(ni, nj) = (i + dir[d][0], j + dir[d][1])
				if ni >= 0 and ni < n and (nj >= 0) and (nj < n) and (m[ni][nj] != 2):
					path += dl[d]
					dfs((ni, nj), path)
					path = path[:len(path) - 1]
			m[i][j] = 1
			return
		dfs((0, 0), '')
		return ans


from typing import List

class Solution:

	def findPathHelper(self, i: int, j: int, a: List[List[int]], n: int, ans: List[str], move: str, vis: List[List[int]]):
		if i == n - 1 and j == n - 1:
			ans.append(move)
			return
		if i + 1 < n and (not vis[i + 1][j]) and (a[i + 1][j] == 1):
			vis[i][j] = 1
			self.findPathHelper(i + 1, j, a, n, ans, move + 'D', vis)
			vis[i][j] = 0
		if j - 1 >= 0 and (not vis[i][j - 1]) and (a[i][j - 1] == 1):
			vis[i][j] = 1
			self.findPathHelper(i, j - 1, a, n, ans, move + 'L', vis)
			vis[i][j] = 0
		if j + 1 < n and (not vis[i][j + 1]) and (a[i][j + 1] == 1):
			vis[i][j] = 1
			self.findPathHelper(i, j + 1, a, n, ans, move + 'R', vis)
			vis[i][j] = 0
		if i - 1 >= 0 and (not vis[i - 1][j]) and (a[i - 1][j] == 1):
			vis[i][j] = 1
			self.findPathHelper(i - 1, j, a, n, ans, move + 'U', vis)
			vis[i][j] = 0

	def findPath(self, m, n):
		ans = []
		vis = [[0 for _ in range(n)] for _ in range(n)]
		if m[0][0] == 1:
			self.findPathHelper(0, 0, m, n, ans, '', vis)
		return ans


class Solution:

	def findPath(self, m, n):
		visited = [[0 for _ in range(n)] for _ in range(n)]
		results = []

		def path(cur_path, i, j):
			if i == n - 1 and j == n - 1:
				results.append(''.join(cur_path))
				return
			if m[i][j] == 0:
				return
			if i + 1 < n and m[i + 1][j] == 1 and (visited[i + 1][j] == 0):
				cur_path.append('D')
				visited[i + 1][j] = 1
				path(cur_path, i + 1, j)
				cur_path.pop()
				visited[i + 1][j] = 0
			if j - 1 > -1 and m[i][j - 1] == 1 and (visited[i][j - 1] == 0):
				cur_path.append('L')
				visited[i][j - 1] = 1
				path(cur_path, i, j - 1)
				cur_path.pop()
				visited[i][j - 1] = 0
			if j + 1 < n and m[i][j + 1] == 1 and (visited[i][j + 1] == 0):
				cur_path.append('R')
				visited[i][j + 1] = 1
				path(cur_path, i, j + 1)
				cur_path.pop()
				visited[i][j + 1] = 0
			if i - 1 > -1 and m[i - 1][j] == 1 and (visited[i - 1][j] == 0):
				cur_path.append('U')
				visited[i - 1][j] = 1
				path(cur_path, i - 1, j)
				cur_path.pop()
				visited[i - 1][j] = 0
			return
		visited[0][0] = 1
		path([], 0, 0)
		return results


class Solution:

	def findPath(self, m, n):
		ans = []

		def isSafe(m, visited, n, scrx, scry):
			if scrx >= 0 and scry >= 0 and (scrx < n) and (scry < n) and (m[scrx][scry] == 1) and (visited[scrx][scry] != 1):
				return True
			else:
				return False

		def helper(m, visited, temp, n, scrx, scry):
			if scrx == n - 1 and scry == n - 1:
				ans.append(temp)
				return
			visited[scrx][scry] = 1
			if isSafe(m, visited, n, scrx + 1, scry):
				helper(m, visited, temp + 'D', n, scrx + 1, scry)
			if isSafe(m, visited, n, scrx, scry - 1):
				helper(m, visited, temp + 'L', n, scrx, scry - 1)
			if isSafe(m, visited, n, scrx, scry + 1):
				helper(m, visited, temp + 'R', n, scrx, scry + 1)
			if isSafe(m, visited, n, scrx - 1, scry):
				helper(m, visited, temp + 'U', n, scrx - 1, scry)
			visited[scrx][scry] = 0
		if m[0][0] == 0:
			return []
		visited = []
		for i in range(n):
			col = []
			for j in range(n):
				col.append(0)
			visited.append(col)
		helper(m, visited, '', n, 0, 0)
		return ans


class Solution:

	def findPath(self, matrix, n):
		ans = list()

		def util(i, j, coveredCoord, path):
			if (i, j) in coveredCoord or i < 0 or i >= n or (j < 0) or (j >= n):
				return
			if matrix[i][j] == 0:
				return
			if i == j == n - 1:
				ans.append(path)
				return
			coveredCoord.add((i, j))
			util(i - 1, j, coveredCoord.copy(), path + 'U')
			util(i, j - 1, coveredCoord.copy(), path + 'L')
			util(i + 1, j, coveredCoord.copy(), path + 'D')
			util(i, j + 1, coveredCoord.copy(), path + 'R')
		util(0, 0, set(), '')
		return ans


class Solution:

	def findPath(self, m, n):
		ans = ''
		ds = []
		dI = [+1, 0, 0, -1]
		dJ = [0, -1, +1, 0]

		def path(i, j, ans, vis):
			if i == n - 1 and j == n - 1:
				ds.append(ans)
				return
			dir = 'DLRU'
			for k in range(4):
				nexti = i + dI[k]
				nextj = j + dJ[k]
				if nexti >= 0 and nextj >= 0 and (nexti < n) and (nextj < n) and (not vis[nexti][nextj]) and (m[nexti][nextj] == 1):
					vis[i][j] = 1
					path(nexti, nextj, ans + dir[k], vis)
					vis[i][j] = 0
		vis = [[0 for _ in range(n)] for _ in range(n)]
		if m[0][0] == 1:
			path(0, 0, ans, vis)
		return ds


class Solution:

	def findPath(self, m, n):
		matrix = m
		if matrix[0][0] == 0 or matrix[n - 1][n - 1] == 0:
			return [-1]
		visited_vals = [(0, 0)]
		solutions = []

		def helper(i, j, direction, path):
			path += direction
			if i >= n - 1 and j >= n - 1:
				solutions.append(path)
				return
			if i < 0 or j < 0 or i >= n or (j >= n) or (matrix[i][j] == 0) or ((i, j) in visited_vals):
				return
			visited_vals.append((i, j))
			for new_direction in ['L', 'D', 'R', 'U']:
				if new_direction == 'L':
					helper(i, j - 1, new_direction, path)
				elif new_direction == 'D':
					helper(i + 1, j, new_direction, path)
				elif new_direction == 'R':
					helper(i, j + 1, new_direction, path)
				else:
					helper(i - 1, j, new_direction, path)
			visited_vals.pop()
		helper(0, 1, 'R', '')
		helper(1, 0, 'D', '')
		if not solutions:
			return [-1]
		return solutions


class Solution:

	def findPath(self, m, n):
		vis = [[0 for i in range(n)] for j in range(n)]
		if m[0][0] == 0:
			return []
		return self.func(m, n, '', [], 0, 0, vis)

	def func(self, m, n, str1, paths, i, j, vis):
		if i == n - 1 and j == n - 1 and (m[i][j] == 1):
			paths.append(str1)
			return paths
		vis[i][j] = 1
		if j + 1 < n and vis[i][j + 1] == 0 and (m[i][j + 1] == 1):
			paths = self.func(m, n, str1 + 'R', paths, i, j + 1, vis)
			vis[i][j + 1] = 0
		if i - 1 >= 0 and vis[i - 1][j] == 0 and (m[i - 1][j] == 1):
			paths = self.func(m, n, str1 + 'U', paths, i - 1, j, vis)
			vis[i - 1][j] = 0
		if i + 1 < n and vis[i + 1][j] == 0 and (m[i + 1][j] == 1):
			paths = self.func(m, n, str1 + 'D', paths, i + 1, j, vis)
			vis[i + 1][j] = 0
		if j - 1 >= 0 and vis[i][j - 1] == 0 and (m[i][j - 1] == 1):
			paths = self.func(m, n, str1 + 'L', paths, i, j - 1, vis)
			vis[i][j - 1] = 0
		return paths


class Solution:

	def findPath(self, m, n):
		vis = [[0] * n for i in range(n)]

		def dfs(i, j, vis, s, m):
			if i == n - 1 and j == n - 1:
				if m[i][j] == 1:
					ans.append(s)
				return
			if 0 <= i < n and 0 <= j < n and (vis[i][j] == 0) and (m[i][j] == 1):
				m[i][j] = 0
				dfs(i + 1, j, vis, s + 'D', m)
				dfs(i - 1, j, vis, s + 'U', m)
				dfs(i, j + 1, vis, s + 'R', m)
				dfs(i, j - 1, vis, s + 'L', m)
				m[i][j] = 1
			else:
				return
		ans = []
		dfs(0, 0, vis, '', m)
		return ans


class Solution:

	def findPath(self, m, n):
		if m[n - 1][n - 1] == 0 or m[0][0] == 0:
			return []
		lst = []
		visited = [[0 for i in range(n)] for j in range(n)]
		self.dfs(0, 0, m, visited, lst, '', n)
		return lst

	def dfs(self, i, j, m, visited, lst, ans, n):
		if i == n - 1 and j == n - 1:
			lst.append(ans)
			return
		if i > 0 and m[i - 1][j] == 1 and (visited[i - 1][j] == 0):
			visited[i][j] = 1
			self.dfs(i - 1, j, m, visited, lst, ans + 'U', n)
			visited[i][j] = 0
		if i < n - 1 and m[i + 1][j] == 1 and (visited[i + 1][j] == 0):
			visited[i][j] = 1
			self.dfs(i + 1, j, m, visited, lst, ans + 'D', n)
			visited[i][j] = 0
		if j > 0 and m[i][j - 1] == 1 and (visited[i][j - 1] == 0):
			visited[i][j] = 1
			self.dfs(i, j - 1, m, visited, lst, ans + 'L', n)
			visited[i][j] = 0
		if j < n - 1 and m[i][j + 1] == 1 and (visited[i][j + 1] == 0):
			visited[i][j] = 1
			self.dfs(i, j + 1, m, visited, lst, ans + 'R', n)
			visited[i][j] = 0


class Solution:

	def solve(self, i, j, ans, res, mat, visited, n):
		if i == n - 1 and j == n - 1:
			res.append(ans)
			return
		if i < n - 1 and mat[i + 1][j] == 1 and (visited[i + 1][j] != 'v'):
			visited[i][j] = 'v'
			self.solve(i + 1, j, ans + 'D', res, mat, visited, n)
			visited[i][j] = '.'
		if j > 0 and mat[i][j - 1] == 1 and (visited[i][j - 1] != 'v'):
			visited[i][j] = 'v'
			self.solve(i, j - 1, ans + 'L', res, mat, visited, n)
			visited[i][j] = '.'
		if j < n - 1 and mat[i][j + 1] == 1 and (visited[i][j + 1] != 'v'):
			visited[i][j] = 'v'
			self.solve(i, j + 1, ans + 'R', res, mat, visited, n)
			visited[i][j] = '.'
		if i > 0 and mat[i - 1][j] == 1 and (visited[i - 1][j] != 'v'):
			visited[i][j] = 'v'
			self.solve(i - 1, j, ans + 'U', res, mat, visited, n)
			visited[i][j] = '.'

	def findPath(self, m, n):
		if m[n - 1][n - 1] == 0 or m[0][0] == 0:
			return []
		res = []
		visited = [['.' for _ in range(n)] for _ in range(n)]
		self.solve(0, 0, '', res, m, visited, n)
		return res


def rat_in_maze_rec(m, i, j, res, path, n, vis, di, dj):
	if i == n - 1 and j == n - 1:
		res.append(''.join(path[:]))
		return
	dir = 'DLRU'
	for idx in range(4):
		nexti = i + di[idx]
		nextj = j + dj[idx]
		if 0 <= nexti < n and 0 <= nextj < n and (not vis[nexti][nextj] == 1) and (m[nexti][nextj] == 1):
			vis[i][j] = 1
			path.append(dir[idx])
			rat_in_maze_rec(m, nexti, nextj, res, path, n, vis, di, dj)
			path.pop()
			vis[i][j] = 0

class Solution:

	def findPath(self, m, n):
		if m[0][0] == 0 or m[n - 1][n - 1] == 0:
			return []
		res = []
		path = []
		vis = [[0 for _ in range(n)] for _ in range(n)]
		di = [+1, 0, 0, -1]
		dj = [0, -1, 1, 0]
		rat_in_maze_rec(m, 0, 0, res, path, n, vis, di, dj)
		return res


class Solution:

	def findPath(self, m, n):

		def ax(vis, i, j, s):
			if i < 0 or j < 0 or j >= n or (i >= n):
				return False
			if m[i][j] == 0 or vis[i][j] == 1:
				return False
			if i == n - 1 and j == n - 1:
				r.append(s)
				return
			vis[i][j] = 1
			ax(vis, i - 1, j, s + 'U')
			ax(vis, i + 1, j, s + 'D')
			ax(vis, i, j - 1, s + 'L')
			ax(vis, i, j + 1, s + 'R')
			vis[i][j] = 0
		r = []
		vis = [[0] * n for _ in range(n)]
		ax(vis, 0, 0, '')
		return r


class Solution:
	ans = []
	arr = []

	def gen(self, grid, n, i, j, visited):
		if i == n - 1 and j == n - 1:
			g = self.arr.copy()
			self.ans.append(''.join(g))
			return
		visited[i][j] = 1
		if i - 1 >= 0 and visited[i - 1][j] == 0 and (grid[i - 1][j] == 1):
			visited[i - 1][j] = 1
			self.arr.append('U')
			self.gen(grid, n, i - 1, j, visited)
			self.arr.pop()
			visited[i - 1][j] = 0
		if j - 1 >= 0 and visited[i][j - 1] == 0 and (grid[i][j - 1] == 1):
			visited[i][j - 1] = 1
			self.arr.append('L')
			self.gen(grid, n, i, j - 1, visited)
			self.arr.pop()
			visited[i][j - 1] = 0
		if i + 1 < n and visited[i + 1][j] == 0 and (grid[i + 1][j] == 1):
			visited[i + 1][j] = 1
			self.arr.append('D')
			self.gen(grid, n, i + 1, j, visited)
			self.arr.pop()
			visited[i + 1][j] = 0
		if j + 1 < n and visited[i][j + 1] == 0 and (grid[i][j + 1] == 1):
			visited[i][j + 1] = 1
			self.arr.append('R')
			self.gen(grid, n, i, j + 1, visited)
			self.arr.pop()
			visited[i][j + 1] = 0
		visited[i][j] = 0

	def findPath(self, m, n):
		self.ans = []
		self.arr = []
		visited = []
		for i in range(n):
			a = []
			for j in range(n):
				a.append(0)
			visited.append(a)
		if m[0][0] == 1:
			self.gen(m, n, 0, 0, visited)
		if len(self.ans) == 0:
			return [-1]
		return self.ans


class Solution:

	def findPath(self, m, n):

		def dfs(x, y, path, res, visited):
			if x < 0 or x >= n or y < 0 or (y >= n) or (m[x][y] == 0):
				return
			if x == n - 1 and y == n - 1:
				res.append(path)
				return
			if (x, y) in visited:
				return
			dfs(x + 1, y, path + 'D', res, visited + [(x, y)])
			dfs(x - 1, y, path + 'U', res, visited + [(x, y)])
			dfs(x, y - 1, path + 'L', res, visited + [(x, y)])
			dfs(x, y + 1, path + 'R', res, visited + [(x, y)])
		paths = []
		dfs(0, 0, '', paths, [])
		return paths


class Solution:

	def solve(self, m, n, x, y, visited, path, answer):
		if x == n - 1 and y == n - 1 and (m[x][y] != 0):
			answer.append(path)
			return
		if -1 < x < n and -1 < y < n and (not visited[x][y]) and (m[x][y] != 0):
			visited[x][y] = 1
			self.solve(m, n, x + 1, y, visited, path + 'D', answer)
			self.solve(m, n, x - 1, y, visited, path + 'U', answer)
			self.solve(m, n, x, y + 1, visited, path + 'R', answer)
			self.solve(m, n, x, y - 1, visited, path + 'L', answer)
			visited[x][y] = 0

	def findPath(self, m, n):
		visited = []
		for i in range(n):
			visited.append([0] * n)
		answer = []
		self.solve(m, n, 0, 0, visited, '', answer)
		return answer if answer else []


class Solution:

	def findPath(self, m, n):
		if m[0][0] == 0:
			return [-1]
		import sys
		sys.setrecursionlimit(10 ** 9)
		visited = [[False for j in range(n)] for i in range(n)]
		dx = [1, 0, 0, -1]
		dy = [0, -1, 1, 0]
		d = ['D', 'L', 'R', 'U']
		result = []
		temp = []
		visited[0][0] = True
		self.solve(0, 0, m, n, visited, dx, dy, d, result, temp)
		return result

	def solve(self, i, j, m, n, visited, dx, dy, d, result, temp):
		if i == n - 1 and j == n - 1:
			st = ''.join(temp)
			result.append(st)
			return
		for r in range(4):
			x = i + dx[r]
			y = j + dy[r]
			if x >= 0 and x < n and (y >= 0) and (y < n) and (m[x][y] == 1) and (not visited[x][y]):
				visited[x][y] = True
				temp.append(d[r])
				self.solve(x, y, m, n, visited, dx, dy, d, result, temp)
				visited[x][y] = False
				temp.pop()


class Solution:

	def findPath(self, m, n):
		visited = set()
		ans = []

		def solve(r, c, st):
			if r < 0 or c < 0 or r >= n or (c >= n) or (m[r][c] == 0) or ((r, c) in visited):
				return
			if r == n - 1 and c == n - 1:
				ans.append(st)
				return
			visited.add((r, c))
			solve(r + 1, c, st + 'D')
			solve(r, c - 1, st + 'L')
			solve(r, c + 1, st + 'R')
			solve(r - 1, c, st + 'U')
			visited.remove((r, c))
		if m[0][0] == 0:
			return ans
		solve(0, 0, '')
		return ans


class Solution:

	def __init__(self):
		self.ans = []

	def findPath(self, m, n):
		self.util(n, m, 0, 0, [])
		return self.ans

	def util(self, n, m, x, y, path):
		if x == n - 1 and y == n - 1 and (m[x][y] == 1):
			self.ans.append(''.join(path))
			return
		if not 0 <= x < n or not 0 <= y < n or m[x][y] == 0:
			return
		else:
			m[x][y] = 0
			self.util(n, m, x + 1, y, [*path, 'D'])
			self.util(n, m, x - 1, y, [*path, 'U'])
			self.util(n, m, x, y + 1, [*path, 'R'])
			self.util(n, m, x, y - 1, [*path, 'L'])
			m[x][y] = 1
		return


class Solution:

	def findPath(self, m, n):
		ans = []
		visited = [[0 for _ in range(n)] for _ in range(n)]
		path = ''
		if m[0][0] == 0 or m[n - 1][n - 1] == 0:
			return [-1]
		self.solve(0, 0, m, n, ans, visited, path)
		return ans

	def isSafe(self, n, x, y, vis, maze):
		if (x >= 0 and x < n) and (y >= 0 and y < n) and (vis[x][y] == 0) and (maze[x][y] == 1):
			return True
		else:
			return False

	def solve(self, x, y, maze, n, ans, vis, path):
		if x == n - 1 and y == n - 1:
			ans.append(path)
			return
		vis[x][y] = 1
		if self.isSafe(n, x + 1, y, vis, maze):
			self.solve(x + 1, y, maze, n, ans, vis, path + 'D')
		if self.isSafe(n, x, y - 1, vis, maze):
			self.solve(x, y - 1, maze, n, ans, vis, path + 'L')
		if self.isSafe(n, x, y + 1, vis, maze):
			self.solve(x, y + 1, maze, n, ans, vis, path + 'R')
		if self.isSafe(n, x - 1, y, vis, maze):
			self.solve(x - 1, y, maze, n, ans, vis, path + 'U')
		vis[x][y] = 0


class Solution:

	def findPath(self, m, n):

		def solve(i, j, move):
			if i == n - 1 and j == n - 1:
				ans.append(move)
				return
			d = 'DLRU'
			for k in range(4):
				ni = i + di[k]
				nj = j + dj[k]
				if ni >= 0 and nj >= 0 and (ni < n) and (nj < n) and (vis[ni][nj] == 0) and (m[ni][nj] == 1):
					vis[i][j] = 1
					solve(ni, nj, move + d[k])
					vis[i][j] = 0
		ans = []
		vis = [[0 for i in range(n)] for j in range(n)]
		di = [+1, 0, 0, -1]
		dj = [0, -1, 1, 0]
		if m[0][0] == 1:
			solve(0, 0, '')
		return ans


class Solution:

	def findPath(self, a, n):
		vis = [[0 for i in range(n)] for j in range(n)]
		drow = [-1, 0, 1, 0]
		dcol = [0, 1, 0, -1]
		ans = []

		def solve(row, col, s):
			if row == n - 1 and col == n - 1:
				ans.append(s)
				return
			dis = 'URDL'
			for i in range(4):
				nr = row + drow[i]
				nc = col + dcol[i]
				if nc >= 0 and nr >= 0 and (nc < n) and (nr < n) and (a[nr][nc] == 1) and (vis[nr][nc] == 0):
					vis[row][col] = 1
					solve(nr, nc, s + dis[i])
					vis[row][col] = 0
		if a[0][0] == 1:
			solve(0, 0, '')
		return ans


class Solution:

	def findPath(self, m, n):
		dir_ = [(-1, 0, 'U'), (0, 1, 'R'), (1, 0, 'D'), (0, -1, 'L')]
		ans = []
		pathVisited = set()

		def isValid(x, y):
			return -1 < x <= n - 1 and -1 < y <= n - 1 and (m[x][y] != 0)

		def rec(i, j, path):
			if (i, j) == (n - 1, n - 1):
				if m[i][j] == 1:
					ans.append(path)
				return
			if isValid(i, j):
				pathVisited.add((i, j))
				for d in dir_:
					(x, y, letter) = (i + d[0], j + d[1], d[2])
					if (x, y) not in pathVisited:
						rec(x, y, path + letter)
				pathVisited.remove((i, j))
		rec(0, 0, '')
		return ans