Problem10632--Minimize the number of turns needed to reach from top left cell to bottom right cell of the matrix

10632: Minimize the number of turns needed to reach from top left cell to bottom right cell of the matrix

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

Given a binary 2D matrix maze of size $N \times N$ such that a cell (r, c) is blocked if maze[r] = 0 and unblocked if maze[r] = 1, the task is to start from cell (1, 1) to reach (N, N1) by minimizing the number of turns. 

We can take any of the four directions (Up, Left, Right, Down) as the starting direction. Then, from each cell, we can either move forward one cell in the current direction or turn left or right by 90 degrees. Return -1 if it is impossible to reach the cell (N, N).

Sample 1 Input

2
1 1
1 1

Sample 1 Output

1
We can take the initial direction as right and continue moving till we reach the second column, after which we take a turn and start moving downwards till we reach cell (N, N).

Sample 2 Input

3
1 0 1
1 1 0
0 1 1

Sample 2 Output

3

Three turns are needed to reach the cell (N, N) from cell (1, 1).

Source/Category