Problem Link - Maze of Digits
Problem Statement -
Johnny, a third year computer science student of Byteland University, is rushing with his AI assignment project which is due tomorrow evening. In this project, he has to build a Lego NXT robot which is able to navigate in a maze. Johnny calls his robot WallB (because he likes the movie "WallE" very much).
The maze is an MxN rectangular grid. There are digits 0..9 and obstacles placed at some intersections. Starting at some intersection, in each step, WallB can move to one of the four intersections adjacent to its current position. However, WallB cannot step into an obstacle.
A maze intersection with a handwritten digit
Johnny needs to program WallB to be able to do the following tasks. First, WallB has to traverse through all reachable intersections of the maze and recognize the digits written at the intersections. Johnny has already finished this part of the assignment since he is very good at image recognition algorithms.
WallB needs to scan and recognize all the reachable digits.
The second part of the assignment is harder. Prof. Q will announce a number X. Based on the map of the maze obtained in the first part, Johnny needs to program WallB to find a shortest path that passes through digits which sum up to X.
To be more precise, suppose in his route, WallB passes through the digits d1, d2, ..., dk in order; then we should have d1 + d2 + ... + dk = X. WallB could pass through a digit more than once.
Johnny gets stuck in this second part of the assignment. Could you write a program to help him?
Approach -
We use Breadth-First Search (BFS) to explore the maze, starting from the first digit. The robot can move up, down, left, or right, and we track the sum of digits and steps taken. We stop exploring paths where the sum exceeds X. If the sum matches X, we return the number of steps. The visited array prevents revisiting cells with the same sum. BFS ensures the shortest path is found because it explores level by level.
Time Complexity
O(M \times N \times X), where M and N are the maze dimensions, and X is the target sum.
Space Complexity
O(M \times N \times X) due to the storage needed for the visited array and the BFS queue.