We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I was thinking about transforming the coordinate matrix into a graph where the nodes would be individual sub-rows or sub-columns (defined by K consecutive cells), and the edges between nodes would simply be any two nodes that are directly adjacent to each other in the coordinate matrix. All edge lengths would be 1. From here, we can just use Djikstra's to find the shortest path from the node containing (a,b) to the node containing (c,d). The preprocessing of the graph is the bottleneck and results in an O(n^2) algorithm.
Castle on the Grid
You are viewing a single comment's thread. Return to all comments →
I was thinking about transforming the coordinate matrix into a graph where the nodes would be individual sub-rows or sub-columns (defined by K consecutive cells), and the edges between nodes would simply be any two nodes that are directly adjacent to each other in the coordinate matrix. All edge lengths would be 1. From here, we can just use Djikstra's to find the shortest path from the node containing (a,b) to the node containing (c,d). The preprocessing of the graph is the bottleneck and results in an O(n^2) algorithm.
What are people's thoughts on this approach?