Problem Link:https://cses.fi/problemset/task/1193/

Solution:

Okay, at first, this seems to me like a regular path-finding problem, which we can proceed by applying BFS/DFS.

However, the challenge I faced is how to print the path in the output.

One approach, which I gave thought to was applying a DFS traversal from the starting cell and storing the corresponding path in a data structure and backtracking if the final output isn't a valid one.

(Similar problem: Leetcode 980)

leetcode.com/problems/unique-paths-iii

But one thing observation: The constraints are huge for this approach to work. {O(3^(m*n))}

Approach:

Apart from the visited matrix, we need to maintain a path matrix in which every cell will store a pair<int,int> corresponding to cell (i,j ), which would give information about the previous cell of the path.

[Current cell (i,j) + pair<int,int> = prev cell ]

Note: We need not return the shortest path,so it wouldn't matter what path[i][j] stores.

Start iterating from the last node from path[i][j] of the end cell.(Using the above formula),and reach to the starting cell and store each of the elements while iterating in a vector of pair.

Reverse that vector.

Link to the code:https://cses.fi/paste/d1b0eb029b70f9d667622e/

Problem:

You are given a map of a labyrinth, and your task is to find a path from start to end. You can walk left, right, up and down.

Input

The first input line has two integers n and m: the height and width of the map.

Then there are n lines of m characters describing the labyrinth. Each character is . (floor), # (wall), A (start), or B (end). There is exactly one A and one B in the input.

Output

First print "YES", if there is a path, and "NO" otherwise.

If there is a path, print the length of the shortest such path and its description as a string consisting of characters L (left), R (right), U (up), and D (down). You can print any valid solution.

Constraints

• 1≤n,m≤1000

Example

Input:
5 8 ######## #.A#...# #.##.#B# #......# ########

Output:
YES 9 LDDRRRRR