5137最大得分的路径数目

# 执行用时 :120 ms, 在所有 python3 提交中击败了100.00% 的用户
# 内存消耗 :13.9 MB, 在所有 python3 提交中击败了100.00%的用户
from typing import List
class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        l = len(board)
        # 这里实际上是记忆搜索,a用于记录每个路径的最大和,以及最大和的个数.
        a = [[0] * l for i in range(l)]
        # 由于board中的数都为正,所以初始值为可以为0,且路径数必须为1,因为有可能右下角的上边和左边都是X的话,路径数为1才对
        a[-1][-1] = (0,1)
        # 将左上角的‘E‘用字符‘0‘代替
        board[0] = board[0].replace(‘E‘, ‘0‘, 1)
        # 先处理最后一行和最后一列
        # 注意这里用-1代替表示不能走,路径设置为0
        # 这里必须用元组来替代,保持与其他位置的结构一致,这样能使程序更简洁,避免不必要的麻烦
        for i in range(l-2, -1, -1):
            if board[l-1][i] == ‘X‘:
                for j in range(i,-1,-1):
                    a[l-1][j] = (-1,0)
                break
            else:
                # 最右边和最下边的列的路径数都记为1
                a[l-1][i] = (int(board[l-1][i]) + a[l-1][i+1][0], 1)
        for i in range(l-2, -1, -1):
            if board[i][-1] == ‘X‘:
                for j in range(i,-1,-1):
                    a[j][-1] = (-1,0)
                break
            else:
                a[i][-1] = (int(board[i][-1]) + a[i+1][-1][0], 1)
        # 开始逐行遍历
        for i in range(l-2, -1, -1):
            for j in range(l-2, -1, -1):
                if board[i][j] == ‘X‘:
                    a[i][j] = (-1,0)
                # 注意这里要用用于记忆的a来判断,用原先的board判断是错误的
                # elif board[i][j+1] == ‘X‘ and board[i+1][j] == ‘X‘:
                # 如果右边和下边都为‘X‘,则判断右下角是否为‘X‘
                elif a[i][j+1][0] == -1 and a[i+1][j][0] == -1:
                    # 如果右下也为‘X‘,则赋值为-1
                    if a[i+1][j+1][0] == -1:
                        a[i][j] = (-1,0)
                    else:
                        # 否则只能走右下角
                        a[i][j] = (int(board[i][j]) + a[i+1][j+1][0], a[i+1][j+1][1])
                # 如果右边为‘X‘,走下边
                elif a[i][j+1][0] == -1:
                    a[i][j] = (int(board[i][j]) + a[i+1][j][0], a[i+1][j][1])
                # 如果下边为‘X‘,走右边
                elif a[i+1][j][0] == -1:
                    a[i][j] = (int(board[i][j]) + a[i][j+1][0], a[i][j+1][1])
                # 否则下边和右边都不为‘X‘,
                # 这时判断两边的大小,如果大小相等,次数要相加
                else:
                    # 如果右边大于下边
                    if a[i][j+1][0] > a[i+1][j][0]:
                        a[i][j] = (int(board[i][j]) + a[i][j+1][0], a[i][j+1][1])
                    # 如果右边小于下边
                    elif a[i][j+1][0] < a[i+1][j][0]:
                        a[i][j] = (int(board[i][j]) + a[i+1][j][0], a[i+1][j][1])
                    # 如果相等
                    else:
                        a[i][j] = (int(board[i][j]) + a[i+1][j][0], a[i][j+1][1]+a[i+1][j][1])
        # 如果大于等于0,则把左上角的值返回
        if a[0][0][0] >= 0:
            return [a[0][0][0], a[0][0][1] % (10 ** 9 + 7)]
        # 否则必定是(-1,0),说明走不通,返回[0,0]
        else:
            return [0, 0]
if __name__ == ‘__main__‘:
    duixiang = Solution()
    a = duixiang.pathsWithMaxScore(board = [‘EX‘,‘XS‘])
    print(a)