Move in a grid with a minimal change in direction

Question

There is a grid, each cell of which contains either 0 or 1. There is a robot that can move horizontally or vertically in the grid. The starting position of the robot and the ending position. On his way from start to finish, he may need to change direction from horizontal to vertical or vertical to horizontal. We need to find the minimum number of direction changes needed to move the robot from beginning to end. There can be several paths from start to finish. 1 means wall, and 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 the grid above, if the robot starts at (1, 0) cells and reaches (3.6), then there are 2 paths. One of these paths requires 3 direction changes, and the other path requires 1 direction change, so the answer is 1. My approach - Using dfs calculates the change in direction along each path from source to destination. Give the minimum value of the change in direction. But it does not work for large input. If someone can suggest a better approach, then this will be helpful.

Answer 1

Stage 1: Let's start by simply converting the grid to a graph:

• Each square with a value of 0 in the grid is a node (there is no need for wall nodes on the graph).
• Edges are added for nodes representing adjacent squares. All edges at this stage have a value of 0 .

Step 2: Convert the graph to the graph of the movement of the direction * .

Looking at node n , we replace it with four mini-nodes, each of which (mentally) represents the wall of the square representing the node. The edges between the mini-nodes exist only if the connected square has a neighboring square. The values ​​on these edges can be 0 (if the edge continues the direction — that is, from left to right or up-down) or 1 (if the edge “turns the corner” - that is, right or right).

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

* This is the name I wrote, do not bother looking for it.

Answer 2

Apply BFS.

• Make Each cell stores the current direction of movement, and then the neighboring nodes must be assigned a weight in accordance with the direction.

• If at any stage you find that the node value will be more than one calculated last time solution, or if this cell is a dead end, discard this cell. Otherwise, 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

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 elements 0 in horizontal and vertical positions to the starting point, as VISITED, and mark the change in direction as 0. When you visit them, put them in the queue. After the first iteration, the grid looks like

0 VVV
V 0 1 1
V 0 0 0
V 0 0 0

Then we get the next item from the queue and continue. Now we increase the change of direction by +1. When we reach the end point, we return a minimal change in direction.