代码如诗

1368. 使网格图至少有一条有效路径的最小代价

给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字，对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：

• 1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1]

• 2 ，下一步往左走，也就是你会从 grid[i][j] 走到 grid[i][j - 1]

• 3 ，下一步往下走，也就是你会从 grid[i][j] 走到 grid[i + 1][j]

• 4 ，下一步往上走，也就是你会从 grid[i][j] 走到 grid[i - 1][j]

注意网格图中可能会有 无效数字 ，因为它们可能指向 grid 以外的区域。

一开始，你会从最左上角的格子 (0,0) 出发。我们定义一条 有效路径 为从格子 (0,0) 出发，每一步都顺着数字对应方向走，最终在最右下角的格子 (m - 1, n - 1) 结束的路径。有效路径 不需要是最短路径 。

你可以花费 cost = 1 的代价修改一个格子中的数字，但每个格子中的数字 只能修改一次 。

请你返回让网格图至少有一条有效路径的最小代价。

示例 1：

```txt

输入：grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]

输出：3

解释：你将从点 (0, 0) 出发。

到达 (3, 3) 的路径为： (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) 花费代价 cost = 1 使方向向下 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) 花费代价 cost = 1 使方向向下 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) 花费代价 cost = 1 使方向向下 --> (3, 3)

总花费为 cost = 3.

```

示例 2：

```txt

输入：grid = [[1,1,3],[3,2,2],[1,1,4]]

输出：0

解释：不修改任何数字你就可以从 (0, 0) 到达 (2, 2) 。

```

示例 3：

```txt

输入：grid = [[1,2],[4,3]]

输出：1

```

示例 4：

```txt

输入：grid = [[2,2,2],[2,2,2]]

输出：3

```

示例 5：

```txt

输入：grid = [[4]]

输出：0

```

提示：

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 100

2290. 到达角落需要移除障碍物的最小数目

给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n 。每个单元格都是两个值之一：

• 0 表示一个 空 单元格，

• 1 表示一个可以移除的 障碍物 。

你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。

现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1) ，返回需要移除的障碍物的 最小 数目。

示例 1：

```txt

输入：grid = [[0,1,1],[1,1,0],[1,1,0]]

输出：2

解释：可以移除位于 (0, 1) 和 (0, 2) 的障碍物来创建从 (0, 0) 到 (2, 2) 的路径。

可以证明我们至少需要移除两个障碍物，所以返回 2 。

注意，可能存在其他方式来移除 2 个障碍物，创建出可行的路径。

```

示例 2：

```txt

输入：grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]

输出：0

解释：不移除任何障碍物就能从 (0, 0) 到 (2, 4) ，所以返回 0 。

```

提示：

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 10^5

• 2 <= m * n <= 10^5

• grid[i][j] 为 0 或 1

• grid[0][0] == grid[m - 1][n - 1] == 0

1263. 推箱子

「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。

游戏地图用大小为 m x n 的网格 grid 表示，其中每个元素可以是墙、地板或者是箱子。

现在你将作为玩家参与游戏，按规则将箱子 'B' 移动到目标位置 'T' ：

• 玩家用字符 'S' 表示，只要他在地板上，就可以在网格中向上、下、左、右四个方向移动。

• 地板用字符 '.' 表示，意味着可以自由行走。

• 墙用字符 '#' 表示，意味着障碍物，不能通行。 

• 箱子仅有一个，用字符 'B' 表示。相应地，网格上有一个目标位置 'T'。

• 玩家需要站在箱子旁边，然后沿着箱子的方向进行移动，此时箱子会被移动到相邻的地板单元格。记作一次「推动」。

• 玩家无法越过箱子。

返回将箱子推到目标位置的最小 推动 次数，如果无法做到，请返回 -1。

示例 1：

```txt

输入：grid = [["#","#","#","#","#","#"],

         ["#","T","#","#","#","#"],

["#",".",".","B",".","#"],

["#",".","#","#",".","#"],

["#",".",".",".","S","#"],

["#","#","#","#","#","#"]]

输出：3

解释：我们只需要返回推箱子的次数。

```

示例 2：

```txt

输入：grid = [["#","#","#","#","#","#"],

         ["#","T","#","#","#","#"],

["#",".",".","B",".","#"],

["#","#","#","#",".","#"],

["#",".",".",".","S","#"],

["#","#","#","#","#","#"]]

输出：-1

```

示例 3：

```txt

输入：grid = [["#","#","#","#","#","#"],

["#","T",".",".","#","#"],

["#",".","#","B",".","#"],

["#",".",".",".",".","#"],

["#",".",".",".","S","#"],

["#","#","#","#","#","#"]]

输出：5

解释：向下、向左、向左、向上再向上。

```

提示：

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 20

• grid 仅包含字符 '.', '#',  'S' , 'T', 以及 'B'。

• grid 中 'S', 'B' 和 'T' 各只能出现一个。

1824. 最少侧跳次数

给你一个长度为 n 的 3 跑道道路 ，它总共包含 n + 1 个 点 ，编号为 0 到 n 。一只青蛙从 0 号点第二条跑道 出发 ，它想要跳到点 n 处。然而道路上可能有一些障碍。

给你一个长度为 n + 1 的数组 obstacles ，其中 obstacles[i] （取值范围从 0 到 3）表示在点 i 处的 obstacles[i] 跑道上有一个障碍。如果 obstacles[i] == 0 ，那么点 i 处没有障碍。任何一个点的三条跑道中 最多有一个 障碍。

• 比方说，如果 obstacles[2] == 1 ，那么说明在点 2 处跑道 1 有障碍。

这只青蛙从点 i 跳到点 i + 1 且跑道不变的前提是点 i + 1 的同一跑道上没有障碍。为了躲避障碍，这只青蛙也可以在 同一个 点处 侧跳 到 另外一条 跑道（这两条跑道可以不相邻），但前提是跳过去的跑道该点处没有障碍。

• 比方说，这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。

这只青蛙从点 0 处跑道 2 出发，并想到达点 n 处的 任一跑道 ，请你返回 最少侧跳次数 。

注意：点 0 处和点 n 处的任一跑道都不会有障碍。

示例 1：

```txt

输入：obstacles = [0,1,2,3,0]

输出：2

解释：最优方案如上图箭头所示。总共有 2 次侧跳（红色箭头）。

注意，这只青蛙只有当侧跳时才可以跳过障碍（如上图点 2 处所示）。

```

示例 2：

```txt

输入：obstacles = [0,1,1,3,3,0]

输出：0

解释：跑道 2 没有任何障碍，所以不需要任何侧跳。

```

示例 3：

```txt

输入：obstacles = [0,2,1,0,3,0]

输出：2

解释：最优方案如上图所示。总共有 2 次侧跳。

```

提示：

• obstacles.length == n + 1

• 1 <= n <= 5 * 10^5

• 0 <= obstacles[i] <= 3

• obstacles[0] == obstacles[n] == 0

6365. 最少翻转操作数

给你一个整数 n 和一个在范围 [0, n - 1] 以内的整数 p ，它们表示一个长度为 n 且下标从 0 开始的数组 arr ，数组中除了下标为 p 处是 1 以外，其他所有数都是 0 。

同时给你一个整数数组 banned ，它包含数组中的一些位置。banned 中第 i 个位置表示 arr[banned[i]] = 0 ，题目保证 banned[i] != p 。

你可以对 arr 进行 若干次 操作。一次操作中，你选择大小为 k 的一个 子数组 ，并将它 翻转 。在任何一次翻转操作后，你都需要确保 arr 中唯一的 1 不会到达任何 banned 中的位置。换句话说，arr[banned[i]] 始终 保持 0 。

请你返回一个数组 ans ，对于 [0, n - 1] 之间的任意下标 i ，ans[i] 是将 1 放到位置 i 处的 最少 翻转操作次数，如果无法放到位置 i 处，此数为 -1 。

• 子数组 指的是一个数组里一段连续 非空 的元素序列。

• 对于所有的 i ，ans[i] 相互之间独立计算。

• 将一个数组中的元素 翻转 指的是将数组中的值变成 相反顺序 。

示例 1：

```txt

输入：n = 4, p = 0, banned = [1,2], k = 4

输出：[0,-1,-1,1]

解释：k = 4，所以只有一种可行的翻转操作，就是将整个数组翻转。一开始 1 在位置 0 处，所以将它翻转到位置 0 处需要的操作数为 0 。

我们不能将 1 翻转到 banned 中的位置，所以位置 1 和 2 处的答案都是 -1 。

通过一次翻转操作，可以将 1 放到位置 3 处，所以位置 3 的答案是 1 。

```

示例 2：

```txt

输入：n = 5, p = 0, banned = [2,4], k = 3

输出：[0,-1,-1,-1,-1]

解释：这个例子中 1 一开始在位置 0 处，所以此下标的答案为 0 。

翻转的子数组长度为 k = 3 ，1 此时在位置 0 处，所以我们可以翻转子数组 [0, 2]，但翻转后的下标 2 在 banned 中，所以不能执行此操作。

由于 1 没法离开位置 0 ，所以其他位置的答案都是 -1 。

```

示例 3：

```txt

输入：n = 4, p = 2, banned = [0,1,3], k = 1

输出：[-1,-1,0,-1]

解释：这个例子中，我们只能对长度为 1 的子数组执行翻转操作，所以 1 无法离开初始位置。

```

提示：

• 1 <= n <= 10^5

• 0 <= p <= n - 1

• 0 <= banned.length <= n - 1

• 0 <= banned[i] <= n - 1

• 1 <= k <= n 

• banned[i] != p

• banned 中的值 互不相同 。

1617. 统计子树中城市之间最大距离

给你 n 个城市，编号为从 1 到 n 。同时给你一个大小为 n-1 的数组 edges ，其中 edges[i] = [ui, vi] 表示城市 ui 和 vi 之间有一条双向边。题目保证任意城市之间只有唯一的一条路径。换句话说，所有城市形成了一棵 树 。

一棵 子树 是城市的一个子集，且子集中任意城市之间可以通过子集中的其他城市和边到达。两个子树被认为不一样的条件是至少有一个城市在其中一棵子树中存在，但在另一棵子树中不存在。

对于 d 从 1 到 n-1 ，请你找到城市间 最大距离 恰好为 d 的所有子树数目。

请你返回一个大小为 n-1 的数组，其中第 d 个元素（下标从 1 开始）是城市间 最大距离 恰好等于 d 的子树数目。

请注意，两个城市间距离定义为它们之间需要经过的边的数目。

示例 1：

```txt

输入：n = 4, edges = [[1,2],[2,3],[2,4]]

输出：[3,4,0]

解释：

子树 {1,2}, {2,3} 和 {2,4} 最大距离都是 1 。

子树 {1,2,3}, {1,2,4}, {2,3,4} 和 {1,2,3,4} 最大距离都为 2 。

不存在城市间最大距离为 3 的子树。

```

示例 2：

```txt

输入：n = 2, edges = [[1,2]]

输出：[1]

```

示例 3：

```txt

输入：n = 3, edges = [[1,2],[2,3]]

输出：[2,1]

```

提示：

• 2 <= n <= 15

• edges.length == n-1

• edges[i].length == 2

• 1 <= ui, vi <= n

• 题目保证 (ui, vi) 所表示的边互不相同。

6353. 网格图中最少访问的格子数

给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在 左上角 格子 (0, 0) 。

当你在格子 (i, j) 的时候，你可以移动到以下格子之一：

• 满足 j < k <= grid[i][j] + j 的格子 (i, k) （向右移动），或者

• 满足 i < k <= grid[i][j] + i 的格子 (k, j) （向下移动）。

请你返回到达 右下角 格子 (m - 1, n - 1) 需要经过的最少移动格子数，如果无法到达右下角格子，请你返回 -1 。

示例 1：

```txt

输入：grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]

输出：4

解释：上图展示了到达右下角格子经过的 4 个格子。

```

示例 2：

```txt

输入：grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]

输出：3

解释：上图展示了到达右下角格子经过的 3 个格子。

```

示例 3：

```txt

输入：grid = [[2,1,0],[1,0,0]]

输出：-1

解释：无法到达右下角格子。

```

提示：

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 10^5

• 1 <= m * n <= 10^5

• 0 <= grid[i][j] < m * n

• grid[m - 1][n - 1] == 0