def search():
    path = [[' ' for el in line] for line in grid]
    parents = [[' ' for el in line] for line in grid]
    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 complet
    resign = False # flag set if we can't find expand

    while not found and not resign:
        if len(open) == 0:
            resign = True
            return 'fail'
        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:
                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])
                            parents[x2][y2] = [x, y]
                            closed[x2][y2] = 1

    # Get solution back
    x, y = goal
    path[x][y] = '*'
    while x != init[0] or y != init[1]:
        if parents[x][y][0] - x == -1:
            path[parents[x][y][0]][parents[x][y][1]] = 'v'
        elif parents[x][y][0] - x == 1:
            path[parents[x][y][0]][parents[x][y][1]] = '<'
        elif parents[x][y][1] - y == -1:
            path[parents[x][y][0]][parents[x][y][1]] = '>'
        elif parents[x][y][1] - y == 1:
            path[parents[x][y][0]][parents[x][y][1]] = '^'
        x, y = parents[x][y]

    return path