PROBLEM LINK:Author: Vitaliy Herasymiv DIFFICULTY:Easy. PREREQUISITES:Simulation. PROBLEM:Given a robot and $N\times N$ grid, find any valid sequence of moves starting from $(1,1)$ such that there are no more than three consecutive turns that moved the robot in the same direction and robot covers each cell atleast once. QUICK EXPLANATION:Start at $(1,1)$ and at each step, consider two consecutive rows and visit in pattern $DRURDRU$(D=Down, R=Right, U=Up). Once both rows are done, jump to another pair of rows. Take care of hurdles using some specific technique. See explanation for details. EXPLANATION:There might be many possible solutions to the problem, lets discuss one of them. We need to derive an strategy which will be covering all of the cells using minimum number of steps and later we have to increase the steps to stop ourselves to go to forbidden cells. Start at coordinate $(1,1)$, Consider two rows at a time. visit in the pattern $DRURDRU$. If in any row, we found a forbidden cell then it will fall in one of these two cases.
In second case, we are visiting a cell more than once but we are skipping a cell as well. So, number of steps will not exceed number of cells. So, if $N$ is even then in worst case we are using $O(N^2)$ number of steps. If $N$ is odd, we are using $(N1)^{th}$ row twice so, we using $N(N+1)$ number of step in worst case. While connecting the row pair ending we will be using at most $5$ steps while there is some forbidden cell, which can be shown using the following image. If there is no forbidden cell, we can do it in lesser number of steps.
It is easy to see we are never taking three steps in same direction in any of the case. In first two cases, we are taking at most two steps in the same direction. While we are switching the pair of rows, we are taking three steps in one direction in the same direction and later changing the direction just after third step. Solution:Setter's solution can be found here
This question is marked "community wiki".
asked 21 Mar '15, 19:11

I don't first case when N is 2 it will be like 1) Nnonforbidden cell Fforbidden cell answered 24 Mar '15, 05:22

How is the solution handling the cases where it might not be possible to traverse the entire row. Something like .#... .#... ..#.. ..#.. ..... One valid solution to this would be DDRDLDRRRURDUULURULLD. Setter's solution never returns the correct answer here. Shouldn't there be some basic graph based solution. answered 28 May '15, 21:14
