Problem Link - Treasure Hunting
Problem Statement
Treasure Hunting is a great computer game that has attracted generations of Bytelandian children.
In the game, there is a maze divided into N \times N squares.
- Dave starts in the top-left corner, which is square (1,1), and needs to go to the bottom-right corner, which is square (N,N).
- Some of the squares are blocked and some of the squares contain treasures.
- Dave needs to capture all the treasures in the maze before going to square (N,N).
- In each second, Dave can go to one of its four adjacent squares (if the destination is not blocked).
Find the earliest time that Dave can reach the destination (N,N) after collecting all the treasures in the maze.
Approach
The approach starts by scanning the maze to find all treasure positions and storing their coordinates. Each treasure is represented by a unique bit in a binary bitmask to track the treasures Dave has collected. Once all treasures are located, a target bitmask is defined to represent the state where all treasures are collected.
The solution uses Breadth-First Search (BFS), starting from the top-left corner. BFS explores the maze level by level, ensuring the shortest path to collect all treasures and reach the destination. At each step, we check if Dave collects a treasure and update the bitmask accordingly. A 3D visited array tracks each cell’s state to avoid reprocessing.
BFS continues until Dave reaches the bottom-right corner with all treasures collected, returning the time taken. If no valid path exists, the result is -1.
Time Complexity
The time complexity is O(N^2×2^T), where 𝑁 is the size of the maze and T is the number of treasures. This accounts for the BFS search across each cell with different treasure collection states.
Space Complexity
The space complexity is O(N^2×2^T ), for the 3D visited array to store each cell’s visited states and the BFS queue.