Need Help in approach

help
1

You and Prem are playing a game show called blind maze.

Prem will be at inside the grid and will be blind folded, and you will be guiding him to victory.

In this game you are given a N x N maze A. The maze has some pillars within the grid, and the rest are on the outskirts of the grid, such that Prem can never leave the grid.

Prem starts off from (1, 1) and can never step on a pillar.

You can only give the commands, move forward, turn 90° left , turn 90° right or do nothing.

But as the prize money is huge, there has to be some twist. In this game, Prem can start facing up or right, and that direction is not known to you.

If you give an instruction such that Prem is going to collide with a pillar, then Prem will not move at all.

Find the minimum length of instructions such that no matter which side Prem is facing, he will be able to exit the grid i.e. reach N x N.
If he is not able to exit then return -1.


Input Format:

The first and the only argument of input contains N strings of length N, representing the grid.
	=> Grid[i][j] = 0 : No Pillar. 
	=> Grid[i][j] = 1 : Pillar.

Output Format:

Return an integer representing the minimum possible length of instructions.

Constraints:

1 <= N <= 100

How to Approach this Problem?

2

Assuming each cell can be visited atmost once, this question is similar to this and can be solved in 3 * N^2

1 Like
3

in the link, the problem has fixed movement of direction i.e to (i+1,j) , (i−1,j) or (i,j+1). but in above problem, direction may change for e.g if you are facing east then 90* left rotation will lead to facing north direction (no movement happens, just change of face) so how to approach this one?

4

Let’s think in another way, assume you are cell (i, j) then add a edge to the cell where you can go(if possible) and run floyd warshall to get minimum value.

5

how exactly you do this ? if you have read question carefully then there’s little trick that some cells are ‘0’ (cannot pass through) and also we need to print minimum commands needed to reach right bottom.