Menu
Red Dot - Represents the initial location
Black Dot - Already occupied
Green - Free to occupy
Destination - Boundry of the matrix [which means either x = 0 or y = 0 or x = 8 or y = 8]
Example:
The red dot can place itself only one move at a time and can move in one of green six circles which are attached to it.
What will be the fastest method to calculate the shortest path in this type of maze.
955
Trémaux's algorithm, invented by Charles Pierre Trémaux, is an efficient method to find the way out of a maze that requires drawing lines on the floor to mark a path, and is guaranteed to work for all mazes that have well-defined passages, but it is not guaranteed to find the shortest route.
Dijkstra's Algorithm and Best-First-Search# Dijkstra's Algorithm is guaranteed to find a shortest path from the starting point to the goal, as long as none of the edges have a negative cost. (I write “a shortest path” because there are often multiple equivalently-short paths.)
Given an n x n binary matrix grid , return the length of the shortest clear path in the matrix. If there is no clear path, return -1 . A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0) ) to the bottom-right cell (i.e., (n - 1, n - 1) ) such that: All the visited cells of the path are 0 .
If there are no negative cycles and there is some path from s to t (t is reachable from s), then there is a shortest path from s to t that is simple (it contains no repeated vertices): deletion of a cycle from the path does not increase the length of the path.
First of all, you don't need Dijkstra, because all values of the edges are the same. You can use a simple BFS or DFS algorithm. Worst case complexities are the same but I would use BFS as it has better average case complexity. However, O(|V|+|E|) is the fastest you can get here and it's proven.
How to have your graph represented? The best way is to keep a list of neighbours for each Node. Black dots from your example aren't counted as a neighbours. So in your example, each node would have 0(fully covered by black dots) to 6 neighbours. Then, you can get anywhere you can get from any node point via these lists.
BFS algorithm has a property that it assigns each node a layer, which means how far it is from a starting node. You start at your starting point and your current layer will be 0. Then you just follow all nodes from a current layer(usually kept at queue) and try to find it's neighbours(from their list of neighbours), which doesn't have layer assigned and you assign them +1 higher layer. Once you find your Node, (which can still have x,y as attributes for border checking (or property bool border)), at the border of your maze, you know it's as far as your layer value is. If you want to print the exact way, you only have to find way back (via your lists of neighbours) which meets the condition that every step is at -1 layer lower. This will print the way from end to start, but I'm sure you'll get your result with a little help from Stack data structure :)
132
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
