# udacity373_code / unit4 / u4-8_firstmaze.py

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79``` ```# ---------- # User Instructions: # # Define a function, search() that takes no input # and returns a list # in the form of [optimal path length, x, y]. For # the grid shown below, your function should output # [11, 4, 5]. # # If there is no valid path from the start point # to the goal, your function should return the string # 'fail' # ---------- # Grid format: # 0 = Navigable space # 1 = Occupied space grid = [[0, 0, 1, 0, 0, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 0], [0, 0, 1, 1, 1, 0], [0, 0, 0, 0, 1, 0]] init = [0, 0] goal = [len(grid)-1, len(grid[0])-1] # Make sure that the goal definition stays in the function. delta = [[-1, 0 ], # go up [ 0, -1], # go left [ 1, 0 ], # go down [ 0, 1 ]] # go right delta_name = ['^', '<', 'v', '>'] cost = 1 def get_neighbors(depth, x, y): neighbors = [] for direction in delta: row, col = x + direction[0], y + direction[1] if 0 <= row < len(grid)\ and 0 <= col < len(grid[0])\ and (grid[row][col] != 1): #if neighbor is out of grid,then skip this step neighbors.append([depth, row, col]) return neighbors def get_next_spot(frontier): '''return spot with minimal depth and frontier where result is with removed''' spot = min(frontier) while spot in frontier: frontier.remove(spot) #remove values from frontier grid[spot[1]][spot[2]] = 1 #mark as visited return frontier, spot def search(): # ---------------------------------------- # insert code here and make sure it returns the appropriate result # ---------------------------------------- val = "fail" depth = 1 frontier = get_neighbors(depth, init[0], init[1]) while len(frontier) != 0: frontier, spot = get_next_spot(frontier) #print "frontier: ", frontier #print "loc: ", spot if goal == spot[1:]: #print "finish:", spot val = spot break new_nodes = get_neighbors(spot[0] + 1, spot[1], spot[2]) if new_nodes is not None and len(new_nodes) > 0: frontier.extend(new_nodes) return val print search() ```