class field:
    def __init__(self, file):
        self.up = [[0 for i in range(7)] for j in range(12)]
        self.down = [[0 for i in range(7)] for j in range(12)]
        self.left = [[0 for i in range(7)] for j in range(12)]
        self.right = [[0 for i in range(7)] for j in range(12)]
        self.visited = [[0 for i in range(7)] for j in range(12)]
        self.parent = [[[0 , 0] for i in range(7)] for j in range(12)]
        with open(file,"rt") as infile:
            self.map = [list(line.strip()) for line in infile.readlines()]
        for x in range(12):
            for y in range(7):
                if self.map[x][y] == 's':
                    self.start = [x, y]
                if self.map[x][y] == 't':
                    self.tomato = [x, y]
                if self.map[x][y] == 'g':
                    self.goal = [x, y]
                try:
                    if self.map[x-1][y] in ('f','t','g','s'):
                        self.up[x][y] = 1
                    else:
                        self.up[x][y] = 0
                except:
                    self.up[x][y] = 0

                try:
                    if self.map[x][y-1] in ('f','t','g','s'):
                        self.left[x][y] = 1
                    else:
                        self.left[x][y] = 0
                except:
                    self.left[x][y] = 0

                try:
                    if self.map[x][y+1] in ('f','t','g','s'):
                        self.right[x][y] = 1
                    else:
                        self.right[x][y] = 0
                except:
                    self.right[x][y] = 0

                try:
                    if self.map[x+1][y] in ('f','t','g','s'):
                        self.down[x][y] = 1
                    else:
                        self.down[x][y] = 0
                except:
                    self.down[x][y] = 0
                #print(x,y, self.left[x][y], self.up[x][y], self.down[x][y], self.right[x][y],sep=' ')

    def clearpath(self):
        self.visited = [[0 for i in range(7)] for j in range(12)]
        self.parent = [[[0 , 0] for i in range(7)] for j in range(12)]


    def search(self, endx, endy, startx, starty):
        print(startx, starty, endx, endy)
        goalfound = 0
        steps = 0
        queue = [[startx, starty]]
        solution = [[]]
        solution.pop(0)
        while not goalfound:
            x, y = queue.pop(0)
            self.visited[x][y] = 1
            steps += 1
            if self.up[x][y]:
                if not self.visited[x-1][y]:
                    queue.append([x-1, y])
                    self.parent[x-1][y] = x, y
            if self.down[x][y]:
                if not self.visited[x+1][y]:
                    queue.append([x+1, y])
                    self.parent[x+1][y] = x, y
            if self.right[x][y]:
                if not self.visited[x][y+1]:
                    queue.append([x, y+1])
                    self.parent[x][y+1] = x, y
            if self.left[x][y]:
                if not self.visited[x][y-1]:
                    queue.append([x, y-1])
                    self.parent[x][y-1] = x, y
            if [x, y] == [endx, endy]:
                goalfound = 1
                #for row in self.visited:
                #    print(*row)
                #for row in self.parent:
                #    print(*row)

                while [startx, starty] != [x, y]:
                    [x, y] = self.parent[x][y]
                    solution.append([x, y])
                self.clearpath()
                return solution




map = field("map.txt")

#print(map.start)
#print(map.tomato)
#print(map.goal)
#print(map.map)
solution = map.search(map.start[0], map.start[1], map.tomato[0], map.tomato[1]) + map.search(map.tomato[0], map.tomato[1], map.goal[0], map.goal[1])

print(map.search(map.tomato[0], map.tomato[1], map.start[0], map.start[1]))
print(map.search(map.goal[0], map.goal[1],map.tomato[0], map.tomato[1]))
print(solution)
laststep = map.start
lsolution = ""
while solution:
    step = solution.pop(0)
    if (step[0]+1) == laststep[0]:
        lsolution = lsolution + "U"
    elif (step[0]-1) == laststep[0]:
        lsolution = lsolution + "D"
    elif (step[1]+1) == laststep[1]:
        lsolution = lsolution + "L"
    elif (step[1]-1) == laststep[1]:
        lsolution = lsolution + "R"
    laststep = step
print(lsolution)
#while not map.goalfound: