def search(grid,init,goal,cost):
    # ----------------------------------------
    # insert code here
    # ----------------------------------------
    closed = [[0 for _ in range(len(grid[0]))] for bar in range(len(grid))]
    closed[init[0]][init[1]] = 1

    x, y = init
    g = 0
    search = [[g, x, y]]
    path = [[' ' for col in range(len(grid[0]))] for row in range(len(grid))]

    found = False
    done = False
    while not found and not done:
        if len(search) == 0:
            done = True
            return 'fail'
        else:
            search.sort(reverse = True)
            oldx, oldy = x, y
            g, x, y = search.pop()
            if oldx == x and oldy < y: # right
                path[oldx][oldy] = '>'
            elif oldx == x and oldy > y: # left
                path[oldx][oldy] = '<'
            elif oldy == y and oldx < x: # down
                path[oldx][oldy] = 'v'
            elif oldy == y and oldx > x: # up
                path[oldx][oldy] = '^'
            if [x,y] == goal:
                found = True
                path[x][y] = '*'
            else:
                for move in delta:
                    tmpx = x + move[0]
                    tmpy = y + move[1]
                    if tmpx >= 0 and tmpx < len(grid) and tmpy >= 0 and tmpy < len(grid[0]):
                        if (not closed[tmpx][tmpy]) and (not grid[tmpx][tmpy]):
                            tmpg = g + cost
                            search.append([tmpg, tmpx, tmpy])
                            closed[tmpx][tmpy] = 1

    return path