The constraints of this task give us a hint that there is no complicated algorithm which must be hardly implemented. After doing a few tests with pen on paper you might figure out a few things. First of all suppose we have NxM grid, so after doing one full cycle (on cycle means that we went to the end of the first row, then turned down, went to the bottom of the grid, then turned left went to the end and then turned upwards and went until we reached the coordinate (2,1) which means that we are again facing right which means that we have go all over again but on the grid of size (N-2,M-2). For a better understanding have a look at the picture below.
The red line represents the first cycle, after it we are again facing right and it is the same as passing 1x2 grid. So, the first thing is decreasing the grid as much as we can by cutting 2s out of it. How do we cut 2s? We take the minimum of 2 sides minus one, and if that number is even then we subtract it from both sides or we decrease it with 1 and then subtract it. After the cutting process the smaller side of grid will be left either 1 or 2. Now it is time only for a few conditions. In case of (1,1) the answer is R, in case of (1,2) it is R, in case of (2,1) it is D , in case of (2,2) it is 'U' , in case of (1,other) , it is R and in case of , (other ,1) is D and for (2,other) is 'L' and (other, 2) is 'U'. Also check out the source code .
The red line represents the first cycle, after it we are again facing right and it is the same as passing 1x2 grid. So, the first thing is decreasing the grid as much as we can by cutting 2s out of it. How do we cut 2s? We take the minimum of 2 sides minus one, and if that number is even then we subtract it from both sides or we decrease it with 1 and then subtract it. After the cutting process the smaller side of grid will be left either 1 or 2. Now it is time only for a few conditions. In case of (1,1) the answer is R, in case of (1,2) it is R, in case of (2,1) it is D , in case of (2,2) it is 'U' , in case of (1,other) , it is R and in case of , (other ,1) is D and for (2,other) is 'L' and (other, 2) is 'U'. Also check out the source code .
No comments:
Post a Comment