题意

给定一个 $nm$ 的权值矩阵，求从左上角走到右下角。$(n, m \in [1, 100], w \in [1, 1e6])$

一条路径耗费的体力值是路径上相邻格子之间 高度差绝对值的最大值 决定的。

Solution

1. 二分答案：由于答案具有单调性，所以可以二分答案，然后通过 $bfs$ 进行验证。
2. 并查集：类似于最小生成树，将所有的边都建出来，然后贪心的将当前权值最小的边加入集合，判断起点和终点是否联通即可。
3. 最短路：将所有的边建出来，做一次起点到终点的最短路径即可。

题意

给你一个字符串 $s$，以及该字符串中的一些「索引对」数组 $pairs$，其中 $pairs[i] = [a, b]$ 表示字符串中的两个索引（编号从 $0$ 开始）。

你可以 任意多次交换 在 $pairs$ 中任意一对索引处的字符。

返回在经过若干次交换后，$s$ 可以变成的按字典序最小的字符串。

Solution

边带权

银河英雄传说

有 $T$ 条指令，每条指令格式为以下两种之一：

1. $M-i-j$，表示让第 $i$ 号战舰所在列的全部战舰保持原有顺序，接在第 $j$ 号战舰所在列的尾部。

题目

问二维矩阵中是否存在相同字母构成的环。

Solution

判环问题，显然可以想到并查集。遍历矩阵，若该点与之前遍历过的相邻点字符相同且是同一个根的话，说明存在环，否则合并这两个点。