腾讯第五题探险

自己的思路就是先BFS求出所有可能轨迹，再对每条轨迹计算得分，最终返回最大值。
本地用例都没问题，但是提交的时候显示超时，给了20%。。。 想问一下有什么优化或者更好的方法的吗？

def _bfs(n):
    trace_list = []
    for st in range(3):
        trace_list_st = [[st]]
        while len(trace_list_st[0]) < n:
            trace = trace_list_st.pop(0)
            for pos in range(3):
                if abs(pos - trace[-1]) <= 1:
                    trace_list_st.append(trace + [pos])
        trace_list += trace_list_st
    return trace_list


def _cal_score(trace, score_list):
    score = 0
    flag = 1
    for i, pos in enumerate(trace):
        score_cur = score_list[i][pos]
        if score_cur == 0:
            flag *= -1
            continue
        else:
            score += flag * score_cur
    return score


def tanxian(n, score_list):
    ret_score = -float('inf')
    trace_list = _bfs(n)
    for trace in trace_list:
        score= _cal_score(trace, score_list)
        if score > ret_score:
            ret_score = score
    return ret_score