PROBLEM LINK:
Author: Tanaeem Moosa
Tester: Jingbo Shang
Editorialist: Jingbo Shang
DIFFICULTY:
Medium
PREREQUISITES:
Dijkstra, Binary Heap
PROBLEM:
Given a R×C matrix and the definition of the distance, you need to answer Q queries of the shortest distance between two nodes.
EXPLANATION:
First of all, if we directly use Dijkstra to calculate the shortest distance, the time complexity is O(QR^2 C^2 ).
Secondly, we should observe that only two adjacent entries have edges. Therefore, there are only O(RC) edges in total.
Combining these two together, we can using Binary Heap to optimize the time complexity of Dijkstra to O(QRC logRC).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
