map = [[
****.**.
*.*..**.
*..****+
......*.
]]

pos = {8,3}
nose = {-1,0}

local function map_info(map)
	local w = (map:find("\n", 1, true) or #map+1) - 1
	local h = #map/(w+1)
	local n = 0
	for m in map:gmatch("%*") do n = n + 1 end
	return w, h, n
end

local moves = {{1,0}, {-1,0}, {0,1}, {0,-1}}

local function sol(w,h,map,path)
	local dirs = {
		["10"] = "R",
		["-10"] = "L",
		["01"] = "D",
		["0-1"] = "U",
	}

	print("solution")
	print(map)
	for i,e in ipairs(path) do
		print(e[1], e[2], dirs[("%d%d"):format(e[3] or 1, e[4] or 0)])
	end
	os.exit()
end

local function oac(w, h, map, n, path, ax, ay)
	--print(w,h,map, n, path, ax, ay, "|")
	--print(map)
	if n==0 then sol(w,h,map,path) end
	
	local old = path[#path]

	for i,move in ipairs(moves) do
		if not (move[1] == -ax and move[2] == -ay) then
			local step = 1
			while true do
				local x = old[1]+move[1]*step
				local y = old[2]+move[2]*step
				if (x == 0) or (x > w) or (y == 0) or (y > h) then
					break
				end
				
				local pos = (y-1)*(w+1) + (x-1) + 1
				local item = map:byte(pos)
				--print(old[1], old[2], "->", x,y, item)
				if item == 42 then
					local nmap = map:sub(1, pos-1) .. "+" .. map:sub(pos+1)
					table.insert(path, {x,y, move[1], move[2]})
					oac(w, h, nmap, n-1, path, move[1], move[2])
					table.remove(path)
					--print("break")
					break
				end

				step = step + 1
			end
		end
	end
end

local w, h, n = map_info(map)

print(#map, w,h,n)
oac(w, h, map, n, {pos}, nose[1], nose[2])
print("nope")