fork()==0世界线变动

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

864. 获取所有钥匙的最短路径

给定一个二维网格 grid ，其中：

• '.' 代表一个空房间

• '#' 代表一堵墙

• '@' 是起点

• 小写字母代表钥匙

• 大写字母代表锁

我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。

假设 k 为 钥匙/锁 的个数，且满足 1 <= k <= 6，字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。

返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。

示例 1：

```txt

输入：grid = ["@.a.#","###.#","b.A.B"]

输出：8

解释：目标是获得所有钥匙，而不是打开所有锁。

```

示例 2：

```txt

输入：grid = ["@..aA","..B#.","....b"]

输出：6

```

示例 3:

```txt

输入: grid = ["@Aa"]

输出: -1

```

提示：

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 30

• grid[i][j] 只含有 '.', '#', '@', 'a'-``'f``' 以及 'A'-'F'

• 钥匙的数目范围是 [1, 6] 

• 每个钥匙都对应一个 不同 的字母

• 每个钥匙正好打开一个对应的锁

2867. 统计树中的合法路径数目

给你一棵 n 个节点的无向树，节点编号为 1 到 n 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示节点 ui 和 vi 在树中有一条边。

请你返回树中的 合法路径数目 。

如果在节点 a 到节点 b 之间 恰好有一个 节点的编号是质数，那么我们称路径 (a, b) 是 合法的 。

注意：

• 路径 (a, b) 指的是一条从节点 a 开始到节点 b 结束的一个节点序列，序列中的节点 互不相同 ，且相邻节点之间在树上有一条边。

• 路径 (a, b) 和路径 (b, a) 视为 同一条 路径，且只计入答案 一次 。

示例 1：

```txt

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

输出：4

解释：恰好有一个质数编号的节点路径有：

• (1, 2) 因为路径 1 到 2 只包含一个质数 2 。

• (1, 3) 因为路径 1 到 3 只包含一个质数 3 。

• (1, 4) 因为路径 1 到 4 只包含一个质数 2 。

• (2, 4) 因为路径 2 到 4 只包含一个质数 2 。

只有 4 条合法路径。

```

示例 2：

```txt

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

输出：6

解释：恰好有一个质数编号的节点路径有：

• (1, 2) 因为路径 1 到 2 只包含一个质数 2 。

• (1, 3) 因为路径 1 到 3 只包含一个质数 3 。

• (1, 4) 因为路径 1 到 4 只包含一个质数 2 。

• (1, 6) 因为路径 1 到 6 只包含一个质数 3 。

• (2, 4) 因为路径 2 到 4 只包含一个质数 2 。

• (3, 6) 因为路径 3 到 6 只包含一个质数 3 。

只有 6 条合法路径。

```

提示：

• 1 <= n <= 10^5

• edges.length == n - 1

• edges[i].length == 2

• 1 <= ui, vi <= n

• 输入保证 edges 形成一棵合法的树。

1240. 铺瓷砖

你是一位施工队的工长，根据设计师的要求准备为一套设计风格独特的房子进行室内装修。

房子的客厅大小为 n x m，为保持极简的风格，需要使用尽可能少的 正方形 瓷砖来铺盖地面。

假设正方形瓷砖的规格不限，边长都是整数。

请你帮设计师计算一下，最少需要用到多少块方形瓷砖？

示例 1：

```txt

输入：n = 2, m = 3

输出：3

解释：3 块地砖就可以铺满卧室。

 2 块 1x1 地砖 1 块 2x2 地砖

```

示例 2：

```txt

输入：n = 5, m = 8

输出：5

```

示例 3：

```txt

输入：n = 11, m = 13

输出：6

```

提示：

• 1 <= n <= 13

• 1 <= m <= 13