Robotic Vacuum Cleaner: Minimum Moves to Clean Grid

You are given a grid with N rows and M columns. Each cell in the grid is either an empty cell denoted by ., an obstacle denoted by #, or the initial position of a robotic vacuum cleaner denoted by R.

Your task is to determine the minimum number of moves required for the vacuum cleaner to reach all empty cells (cells with .). The vacuum cleaner can move one step at a time in one of the four cardinal directions: up, down, left, or right. If it is impossible for the vacuum cleaner to clean all empty cells, output -1.

Note: The initial cell marked with R is not counted as an empty cell even if it could have been marked with .. Only the cells marked by . are considered for cleaning.

The moves are counted as the number of steps taken from the starting point to the moment when all empty cells have been reached during the exploration.

The answer must be computed using an optimal path search (for example, using breadth-first search).

inputFormat

The first line of input contains two integers N and M, separated by a space, representing the number of rows and columns respectively.

This is followed by N lines, each containing a string of M characters. Each character is one of R, ., or #, which respectively denote the starting position of the robotic vacuum cleaner, an empty cell that needs cleaning, and an obstacle that cannot be passed through.

outputFormat

Output a single integer: the minimum number of moves required for the robotic vacuum cleaner to clean all empty cells. If it is impossible to clean all empty cells, output -1.

3 3
R..
.#.
...

4