RDR2_1 - Escape the New America


So, Mr. Intelligent, have you played the game Red Dead Redemption 2? Yeah, man, this game deserves a Heavenly place in the hearts of gamers.

Our hero Arthur Morgan is now on Newyork city in the modern civilization of America. As always, he is now being chased by some Cops. As the civilization has developed a lot, now there are a lots of Police Stations in different places of Newyork. And there are also a lots of buildings and shopping malls spreading all around the city. Besides there are also some docks from which our hero Arthur can get out of the New America as well as escaping from the cops. There are some roads in between all the obstacles of the city which will lead our hero to any docks from which he can escape.

In this problem, we will consider Newyork city as an N × M matrix. Where each police station is denoted as the letter 'S' and the roads are considered as '.'. And whenever you find the character '#', that means nobody can get through this as it is an obstacle. Arthur and the Cops can only travel through the roads. Each Police Station contains exactly one cop. Each one cop will start his journey from a police station and will move along the road. And by any means, if our hero Arthur can get to any border of the given matrices without being caught by the cops, that means, he has escaped. Remember, that border should not contain any obstacle nor any police station.

You're given the initial position of Arthur ('A'). Note that, the cops can start their journey from any police station and can also move only along the roads. Arthur has to move in such a way that, there are no cops at that time when he get through that certain point of road.

Now, as being an intelligent companion of Arthur, you have to tell, if it is possible to get out of the New America. If it is possible, you have to tell the path which Arthur should follow and the length of that path.

Constraints

  • 1 ≤ n, m ≤ 1000

Input

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

After this there are n lines of m characters describing the map. Each character is . (road), # (obstacles), A (starting position of Arthur), or S (Police Stations). There is exactly one A in the input.

Output

First print "YES" if your goal is possible, and "NO" otherwise.

If your goal is possible, also print an example of a valid path (the length of the path and its description using characters D, U, L, and R). You have to print the shortest path, as long as its length is at most n × m steps.

Sample

Input 1:
4 4
#.#S
#.##
#A..
####

Output 1:
YES
2
UU
Input 2:
4 4
#..S
#.##
#A.#
####

Output 2:
NO


hide comments
codingjedi048: 2021-10-01 12:02:44

@Sushovan Sen, Police will also move optimally to capture Arthur. If the situation is such that, the police have to stay at the police station to capture Arthur, then the police can remain immobile.

Sushovan Sen: 2021-10-01 10:59:40

Can a police stay in a position without moving? What is expected output of this case :
4 4
#.S.
#.##
#A.#
####

Last edit: 2021-10-01 11:53:52
Vipul Srivastava: 2021-09-08 18:26:59

@codingjedi048 thanks for the test case, I think I got the issue, will try again.

Thanks, got AC, great question !

Last edit: 2021-09-08 18:46:53
Vipul Srivastava: 2021-09-05 19:18:55

then I print
YES
0
and an empty line

codingjedi048: 2021-09-05 16:20:50

@Vipul Srivastava, are you covering the corner case correctly.?. What if, Arthur initially starts his journey from any border.?.

Vipul Srivastava: 2021-09-05 09:57:27

Now I have no idea why I am getting WA. @Author can you give me some hint, I understand if you don't as there are already I/O samples.

codingjedi048: 2021-09-03 07:46:17

@appan, yes, Arthur can initially be in the border and in that case you have to print the length of the empty string and the string itself.

appan: 2021-09-02 18:35:15

can arthur starting position be in the border? if yes, should we print just an empty string for the path?

Vipul Srivastava: 2021-09-01 08:23:37

@Author in my opinion I took care of that, anyways thanks I will look more closely.


Added by:Dr. AddictStein
Date:2021-08-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Dr. AddictStein Research Lab