Moving in grid with minimum direction change

Question

There is a grid whose every cell contains either 0 or 1. There is a robot which can move either horizontally or vertically in grid. There is a starting position of robot & an end position. In its path from start to end, it might need to change its direction from horizontal to vertical or vertical to horizontal. We need to find the minimum number of direction changes needed for moving the robot from start to end. There may be multiple paths from start to end. 1 means wall & 0 means passage. For ex -

1 1 1 1 1 1 1
0 0 0 0 0 0 0
1 1 1 1 1 0 0
1 1 1 1 1 1 0

In above grid if robot starts from (1, 0) the cell & reaches (3,6) then there are 2 paths One of those path needs 3 direction changes & other path requires 1 direction change so the answer is 1. My approach - Using dfs calculate direction change in every path from source to destination. Report the minimum value of direction change. But it is not working for large sized input. If someone can suggest a better approach then it would be helpful.

Answer 1

Stage 1: Start off by transforming the grid into a graph in the obvious way:

1. Every square with value 0 in the grid is a node (no need for the wall nodes in the graph).
2. Edges are added for nodes that represent adjacent squares. All edges at this stage have a value of 0.

Stage 2: Transform the graph into a direction moving graph*.

Looking at a node n, we replace it with four mini-nodes, each (mentally) representing the wall of the square the node is representing. Edges between the mini-nodes exist only if related square has an adjacent square. The values on these edges can be 0 (if the edge continues the direction - i.e. left to right or up-down) or 1 (if the edge "turns a corner" - i.e. right-down, or right-up).

Once this is done, run Dijkstra or some similar algorithm.

* This is a name I made up, don't bother googling it.

Answer 2

Apply BFS.

1. Make Each cell store the current direction of traversing & then adjacent nodes has to be allocated the weight as per the direction.

2. If at any stage, you find that the value of the node to be greater than the one computed last time solution or, if that cell is a dead end then discard that cell. Else add the same to the queue.

   This should solve the problem for sure.

Answer 3

One approach to this problem is as follows:

Suppose the input grid is

0 0 0 0
0 0 1 1
0 0 0 0
0 0 0 0

start is (1,1) and end is (4,4).

Now starting from 1,1 mark all the 0 element in horizontal and vertical to the start point as VISITED and mark the direction change as 0. As you visit them put them in a queue. After first iteration the grid looks like

0 V V V
V 0 1 1
V 0 0 0
V 0 0 0

Then we get the next element from the queue and proceed. Now we increase the direction change to +1. When we reach the end point we return the minimum direction change.