PROBLEM LINKS:
Author: sikander_nsit
Tester: sikander_nsit
Editorialist: sikander_nsit
DIFFICULTY:
EASY-MEDIUM
PROBLEM:
Given a 2D matrix consisting of 0 and 1 find the shortest path from (1,1) to (n,m) such that the path should consist of alternate 0 and 1.
EXPLANATION:
This was a standard BFS problem. In the question the condition was that if Eon is standing in a room marked ‘0’ then he can only go to a room marked ‘1’ and if he is in room ‘1’ then he must go to a room marked ‘0’. So he had to travel from (1,1) to (n,m) with alternate ‘0’ and ‘1’.
Start the BFS at (1,1). Visit the current node. Check all 4 adjacent cells. If different than the current cell then push its coordinates in the queue. We can keep 2D DP array to store the minimum distance of every cell from (1,1). Whenever a cell(i,j) is visited DP[i][j] is updated and its neighbours if valid are pushed into the queue. This will be O(nm) complexity. At the end we can simply print dp[n][m] and if it is not visited then it means there was no path so print “-1”.
The property of BFS which is used here is that BFS visits every node with shortest distance from the source. DFS can timeout if not implemented properly when the whole maze is made up of alternate 1s and 0s.
AUTHOR’S SOLUTION:
Author’s solution can be found here.