Loading...
Loading...
Loading...
Ishaan is testing a robot in his college lab. The floor is a grid of r rows and c columns. A . is an open cell and a # is a box the robot cannot enter.
The robot starts at the top-left cell and must reach the bottom-right cell. It moves one cell at a time: D (down), L (left), R (right) or U (up). It never visits the same cell twice in one route.
Print every possible route.
. or #.0.Example 1
Input
2 2 .. ..
Output
2 DR RD
Down then right, or right then down. DR comes before RD in dictionary order.
Example 2
Input
3 3 ..# #.. #..
Output
2 RDDR RDRD
From the top-left the robot must go right and then down. From there it can reach the target in two ways.
Try the problem first. Open one hint at a time.
From a cell, try the four moves in the order D, L, R, U. Trying them in letter order prints the routes in dictionary order.
Mark a cell as visited when you step on it, so a route never comes back to it.
When a call returns, unmark the cell and remove the last letter. Another route may use that cell later.
Reaching the bottom-right cell completes one route: save a copy of the letters so far. Print the count first, then the saved routes.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor