Given a n×m grid maze which consists of walls (#
), floors (.
), start (A
), and end(B
). You can walk in four directions: up, down, left and right, but you cannot pass the walls. Please output a path to walk from the start to the end with minimum steps, or it is impossible to go from the start to the end.
The first line contains two integers n and m, being the number of rows and columns of the grid maze.
The following n lines describes the maze. Each line has m characters which is one of #
, .
, A
, or B
.
There is exactly one A
and B
in the input.
Restrictions
If it is possible to go from the start to the end, print "YES" in the first line, the number of minimum steps in the second line.
If it is impossible, please print "NO" in the first line.
Remember there should be a ‘\n’ at the end of the last line of output.