Can anyone provide the editorial for ROLLBAR question of FEB Lunchtime.
Thank you…
1 Like
It’s pending for being posted by the admin
1 Like
Hints:
First, think about the basic problem where you can take only one step in any direction
Solution:
brute force would be costly
better solution would be to use bfs(breadth-first search) from the target cell
same ideas are used for solving this problem.
You should know bfs on grids before solving this problem(Practice similar problems to become familiar - Eg problem: https://www.codechef.com/problems/L56LABY)
Short Explanation of Solution:
We can define a point( this is basically the current state to be processed ) as:
struct point{
int posx, posy ;
int roll_direction ; // direction of roll (useful only if state = rolled)
int state ; // standing or rolled over (i've used 0 or 1 respectively)
} ;
Assume you have to reach the cell (gx, gy)
There are 2 states possible at any moment:
- you are standing on a cell (x, y)
- you are lying flat on 2 cells
lying flat can be represented using (x,y) and direction arrow(converted to integers) instead of two coordinates
where (x, y) can be one of those cells(this is what i’ve chosen, there may be other ways to represent but i’ve chosen this one)
Initialize all distances to -1, dist[x][y] = -1 for all ( 0 < x < n && 0 < y < m) (other values such as INF can also be chosen)
We implement bfs from the target cell, initializing dist[gx][gy][roll_dir][0] = 0 (i have used 2 different distances for different states) and putting it in bfs queue, and for each point in bfs queue, put in queue the neighbouring cells(think on paper how to represent the neighbours as points) and increase their distance by 1 than previous cell(also check whether they are valid points or not).
You should be familiar with bfs on grid to understand it better
Repeat this process until queue becomes empty
At the end, display the distances
The implementation is a tough part though(atleast for me), have to think a lot carefully before implementing, took a lot of time for me.
There may be better approaches possible, look at codes of high rated coders
my solution code link: https://www.codechef.com/viewsolution/23224872
2 Likes
