# udacity373_code / unit4 / u4-9_expansiongrid.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 80 81 82 83 84``` ```# ----------- # User Instructions: # # Modify the function search() so that it returns # a table of values called expand. This table # will keep track of which step each node was # expanded. # # For grading purposes, please leave the return # statement at the bottom. # ---------- grid = [[0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 1, 0], [0, 0, 1, 0, 1, 0], [0, 0, 1, 0, 1, 0]] init = [0, 0] goal = [len(grid)-1, len(grid[0])-1] delta = [[-1, 0 ], # go up [ 0, -1], # go left [ 1, 0 ], # go down [ 0, 1 ]] # go right delta_name = ['^', '<', 'v', '>'] cost = 1 # ---------------------------------------- # modify code below # ---------------------------------------- def init_expand(grid): val = [] for row in grid: val.append([-1 for col in grid[0]]) return val def search(): expand= init_expand(grid) step = 0 closed = [[0 for row in range(len(grid[0]))] for col in range(len(grid))] closed[init[0]][init[1]] = 1 x = init[0] y = init[1] g = 0 open = [[g, x, y]] found = False # flag that is set when search is complete resign = False # flag set if we can't find expand while not found and not resign: if len(open) == 0: resign = True else: open.sort() open.reverse() next = open.pop() x = next[1] y = next[2] g = next[0] expand[x][y] = step step += 1 if x == goal[0] and y == goal[1]: found = True else: for i in range(len(delta)): x2 = x + delta[i][0] y2 = y + delta[i][1] if x2 >= 0 and x2 < len(grid) and y2 >=0 and y2 < len(grid[0]): if closed[x2][y2] == 0 and grid[x2][y2] == 0: g2 = g + cost open.append([g2, x2, y2]) closed[x2][y2] = 1 return expand #Leave this line for grading purposes! print search() ```