A robot is standing in the upper left corner of an n x n grid. Because of the sl

Question

A robot is standing in the upper left corner of an n x n grid. Because of the slight tilt of the terrain, only the steps right and down deplete the charge by one unit; moving in the other two directions does not deplete the charge at all.

Certain squares contain charging stations. The robot starts fully charged, and after being fully charged it can make 10 steps before running out of power.

When the robot passes through a charging station, it is fully recharged.

Your task is to plan a route for the robot, if it is possible at all, in which it does not run out of power and reaches the bottom right corner.

Design an algorithm that under this new condition determines if the robot is able to
reach the desired destination.

Explanation / Answer

Algorithm :

Step 1 : In any possible solution robot will move N rights steps and N down steps to reach (0,0), or we can say that initial robot has permission to move N rights steps and N down steps.

Step 2 : When ever robot moves right we reduce its remaining number of right steps by 1, same is for down movement.

Step 3 : At every position(except at boundary, where it will have only one option) robot have two options, one is it can go down or other is it can go right.

Step 4 : It will terminate when robot will have no remaining down of right steps.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.