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