# alexband/Udacity-373

Fetching contributors…
Cannot retrieve contributors at this time
83 lines (64 sloc) 2.07 KB
 # ----------- # 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 search(): count = 0 closed = [[0 for row in range(len(grid[0]))] for col in range(len(grid))] closed[init[0]][init[1]] = 1 expand = [[-1 for row in range(len(grid[0]))] for col in range(len(grid))] expand[init[0]][init[1]] = 0 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] if x == goal[0] and y == goal[1]: found = True else: count += 1 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 expand[x2][y2] = count return expand #Leave this line for grading purposes! print search()