0741. Cherry Pickup ======================================================================================================================== 题目信息 -------- :题号: 0741 :难度: Hard :主题: 矩阵、往返路径、樱桃收集 :原题: `LeetCode 0741 `_ :重点: 去程只能向右或向下,返程只能向左或向上;荆棘不可经过,樱桃被采摘后不再重复计数,无有效起终点路径时返回 ``0`` 题目重述 -------- 给定一个 ``n x n`` 方格 ``grid``。每个格子的值为:``0`` 表示可经过但没有樱桃,``1`` 表示可经过且有一颗樱桃,``-1`` 表示荆棘,不能进入。 先从左上角 ``(0, 0)`` 出发,只能向右或向下移动,通过合法格子到达右下角 ``(n - 1, n - 1)``;随后从右下角返回左上角,只能向左或向上移动。每次经过值为 ``1`` 的格子时采走其中的樱桃,该格子随后视为 ``0``,因此同一颗樱桃最多计数一次。 返回一次完整往返能够采到的最大樱桃数。若左上角到右下角不存在任何合法路径,则无法完成往返,返回 ``0``。 ``1 <= n <= 50``,每个格子值只可能为 ``-1``、``0`` 或 ``1``,且起点和终点都不是荆棘。 自建示例 -------- 去程与返程覆盖不同路径: .. code-block:: text 输入:grid = [[1,1],[1,1]] 输出:4 解释:去程可沿上边和右边到达终点,采走 3 颗樱桃;返程再经过左下角尚未采走的樱桃,最终四个格子的樱桃都被收集。 起点与终点之间没有合法路径: .. code-block:: text 输入:grid = [[0,-1],[-1,1]] 输出:0 解释:起点向右和向下都会遇到荆棘,无法到达终点,因此按题意返回 0。