const ratInMaze = (m , n) => {
	const LEN = m.length
	var directions = {
		D : [1 ,0],
		L : [0,-1],
		R : [0,1] ,
		U : [-1,0],
	}
	const res = []


	function traverse(row , col , s , vis) {	
		if (row === LEN -1 && col === LEN-1)  {
			const copy = s.slice()
			return res.push(copy)
		}

		for (let [dir,[dx,dy]] of Object.entries(directions)) {
			let [r,c] = [row + dx , col + dy]
			
			if (isValid(r,c , vis)) {	
				visited[r][c] = true 
				traverse(r,c, s+dir , vis )				
				visited[r][c] = false
			}
		}
	}

	function isValid(i,j , vis) {
		if (i < 0 || i >= n || j < 0 || j >= n)
			return false
		return (m[i][j] === 1 && !vis[i][j])
	}


	const visited = Array(n).fill(Array(n).fill(false))
	visited[0][0] = true

	traverse(0, 0, "",  visited)
	return res
}