sferer
unknown
plain_text
2 years ago
1.5 kB
6
Indexable
This code is a Python implementation of breadth-first search (BFS) algorithm, used to find the shortest path between two points on a map represented by a two-dimensional array of characters. The input map, "lava_map2", is a list of strings, where each string represents a row of the map. "*" represents an obstacle, "s" represents the starting point, and "D" represents the target diamond. The "minu_otsing" function takes in two arguments, the "lava_map2" and the "start" position. It starts by finding the start location and the diamond location using two nested for loops. It then uses another two nested for loops to build a graph representation of the map, where each node is represented by a tuple of its (row, column) index, and each edge represents a valid path between two neighboring nodes. After building the graph, the function starts the search by initializing a queue, "frontier", and adding the start location to it. It also initializes a dictionary, "came_from", to keep track of the previous node in the path for each node. The function then repeatedly takes the next node from the queue, checks if it is the target, and if not, adds its neighbors to the queue and updates the "came_from" dictionary. The search continues until the queue is empty or the target node is found. Finally, the function constructs the path by following the "came_from" pointers from the target node to the start node, and returns the path. It also prints out the number of steps taken to reach the target.
Editor is loading...