BFS-FloodFill 算法 解决最短路问题 多源 解决拓扑排序

一、FloodFill 算法

洪水灌溉，可以用BFS也可以用DFS

//辅助数组visited中存放所有节点
//初始化为0，访问过后设置为1 
void BFS (Graph G, int v){		//按广度优先非递归遍历连通图Gcout<<v; visited[v] = 1;	//访问第v个顶点queue<int> q;				//辅助队列Q初始化，置空q.push(v);				//v进队while(!q.empty()){ 		//队列非空q.pop();			//队头元素出队并置为ufor (int i = 0; i < G.vexnum; i++) {int w = G.vex[i];if (G.edge[k][i] && !visited[i]) {//v和i有边且没有被访问cout << w;q.push(w);visited[i] = 1;}}}
}
//调用
void BFStraverse(graph) {for (int v = 0; v < G.vexnum; ++v)visited[v] = 0;for (int v = 0; v < G.vexnum; ++v)if (!visited[v])BFS(G, G.vex[v]);
}

733. 图像渲染

- 从初始像素开始，将其颜色改为 `color`。- 对初始坐标的 **上下左右四个方向上** 相邻且与初始像素的原始颜色同色的像素点执行相同操作。- 通过检查与初始像素的原始颜色相同的相邻像素并修改其颜色来继续 **重复** 此过程。- 当 **没有** 其它原始颜色的相邻像素时 **停止** 操作。

2.思路

使用一个队列来存储待处理的像素点，将起始点加入队列并将其颜色替换为目标颜色，然后不断从队列中取出像素点，检查其上下左右相邻的像素点，如果相邻像素点的颜色与起始点的原始颜色相同，则将其颜色替换为目标颜色并加入队列，直到队列为空

3.代码

class Solution {
public:// BFS 函数用于执行广度优先搜索，对图像中与起始点颜色相同且相连通的区域进行颜色替换void BFS(std::vector<std::vector<int>>& image, int sr, int sc, int currColor, int color) {// 定义一个队列，用于存储待处理的像素点，每个像素点用一个 std::pair<int, int> 表示，分别代表行和列std::queue<std::pair<int, int>> q;// 将起始点加入队列q.push({sr, sc});// 立即将起始点的颜色替换为目标颜色，避免后续重复处理该点image[sr][sc] = color;// 当队列不为空时，继续处理队列中的像素点while (!q.empty()) {// 取出队列头部的像素点int x = q.front().first, y = q.front().second;// 将该像素点从队列中移除q.pop();// 检查当前像素点左侧的像素点if (y - 1 >= 0 && image[x][y - 1] == currColor) {// 若左侧像素点存在且颜色与起始点的原始颜色相同// 将其颜色替换为目标颜色image[x][y - 1] = color;// 将该像素点加入队列，以便后续处理其相邻像素点q.push({x, y - 1});}// 检查当前像素点右侧的像素点if (y + 1 < image[0].size() && image[x][y + 1] == currColor) {// 若右侧像素点存在且颜色与起始点的原始颜色相同// 将其颜色替换为目标颜色image[x][y + 1] = color;// 将该像素点加入队列，以便后续处理其相邻像素点q.push({x, y + 1});}// 检查当前像素点上方的像素点if (x - 1 >= 0 && image[x - 1][y] == currColor) {// 若上方像素点存在且颜色与起始点的原始颜色相同// 将其颜色替换为目标颜色image[x - 1][y] = color;// 将该像素点加入队列，以便后续处理其相邻像素点q.push({x - 1, y});}// 检查当前像素点下方的像素点if (x + 1 < image.size() && image[x + 1][y] == currColor) {// 若下方像素点存在且颜色与起始点的原始颜色相同// 将其颜色替换为目标颜色image[x + 1][y] = color;// 将该像素点加入队列，以便后续处理其相邻像素点q.push({x + 1, y});}}}// floodFill 函数是对外提供的接口，用于调用 BFS 函数完成图像填充操作std::vector<std::vector<int>> floodFill(std::vector<std::vector<int>>& image, int sr, int sc, int color) {// 获取起始点的当前颜色int currColor = image[sr][sc];// 若起始点的当前颜色与目标填充颜色不同，则调用 BFS 函数进行填充if (currColor != color) {BFS(image, sr, sc, currColor, color);}// 返回填充后的图像return image;}
};

200. 岛屿数量

**输入：**grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]
]
**输出：**1

**输入：**grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]
]
**输出：**3

2.思路

遍历整个二维数组，返回有多少个完全被0隔开的岛屿1。广度优先搜索的过程，只要队列不为空，就从队列中取出一个位置的坐标。针对这个位置，检查其上下左右四个相邻位置。若相邻位置在网格范围内、值为 '1' 且未被访问过，就将该相邻位置的坐标加入队列，并标记为已访问。通过这种方式，不断扩展当前岛屿所覆盖的范围，直至队列为空，意味着当前岛屿的所有位置都已被访问过。visited默认是 false

3.代码

class Solution {
public:bool visited[301][301];int numIslands(vector<vector<char>>& grid) {queue<pair<int, int>> q;int r = grid.size();int c = grid[0].size();int ret = 0;for (int i = 0; i < r; ++i) {for (int j = 0; j < c; ++j) {if (grid[i][j] == '1' && visited[i][j] == false) {ret++;q.push({i, j});visited[i][j] = true;while (!q.empty()) {int x = q.front().first, y = q.front().second;q.pop();if(y-1>=0 && grid[x][y-1] == '1' && visited[x][y-1] == false){q.push({x, y-1});visited[x][y-1] = true;}if(y+1<grid[0].size() && grid[x][y+1] == '1' && visited[x][y+1] == false){q.push({x, y+1});visited[x][y+1] = true;}if(x-1>=0 && grid[x-1][y] == '1' && visited[x-1][y] == false){q.push({x-1, y});visited[x-1][y] = true;}if(x+1<grid.size() && grid[x+1][y] == '1' && visited[x+1][y] == false){q.push({x+1, y});visited[x+1][y] = true;}}}}}return ret;}
};

LCR 105. 岛屿的最大面积

**输入: **grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
**输出: **6
**解释: **对于上面这个给定矩阵应返回 `6`。注意答案不应该是 `11` ，因为岛屿只能包含水平或垂直的四个方向的 `1` 。

**输入: **grid = [[0,0,0,0,0,0,0,0]]
**输出: **0

2.思路

初始化相关变量：定义一个 visited 二维布尔数组，用于标记网格中每个位置是否已被访问；获取网格的行数和列数；创建一个队列用于 BFS；初始化最大岛屿面积为 0。

遍历网格：使用两层嵌套的 for 循环遍历整个网格。对于每个未被访问且值为 1（表示陆地）的位置，将其标记为已访问，并将其作为一个新岛屿的起始点。

BFS 搜索当前岛屿：将起始点加入队列，开始 BFS 过程。在 BFS 中，从队列中取出一个位置，检查其上下左右四个相邻位置。若相邻位置合法（在网格范围内）、为陆地且未被访问过，则将该相邻位置标记为已访问，岛屿面积加 1，并将其加入队列继续搜索。

更新最大岛屿面积：当当前岛屿的 BFS 搜索结束后，将该岛屿的面积与之前记录的最大岛屿面积进行比较，取较大值更新最大岛屿面积。

3.代码

class Solution {
public:// 用于标记网格中每个位置是否被访问过的二维数组bool visited[51][51];int maxAreaOfIsland(std::vector<std::vector<int>>& grid) {// 获取网格的行数int r = grid.size();// 获取网格的列数int c = grid[0].size();// 定义一个队列，用于广度优先搜索（BFS），存储待处理的网格位置std::queue<std::pair<int, int>> q;// 用于记录最大岛屿面积int ret = 0;// 遍历网格的每一行for (int i = 0; i < r; ++i) {// 遍历网格的每一列for (int j = 0; j < c; ++j) {// 如果当前位置未被访问过且为陆地（值为 1）if (!visited[i][j] && grid[i][j] == 1) {// 标记当前位置为已访问visited[i][j] = true;// 初始化当前岛屿的面积，起始点面积为 1int sum = 1;// 将当前位置加入队列，准备进行 BFSq.push({i, j});// 开始 BFS 过程，只要队列不为空，就继续处理while (!q.empty()) {// 获取队列头部元素的行和列坐标int x = q.front().first, y = q.front().second;// 从队列中移除头部元素q.pop();// 检查当前位置左侧的位置if (y - 1 >= 0 && grid[x][y - 1] == 1 && !visited[x][y - 1]) {// 若左侧位置合法、为陆地且未被访问过，当前岛屿面积加 1sum++;// 标记左侧位置为已访问visited[x][y - 1] = true;// 将左侧位置加入队列q.push({x, y - 1});}// 检查当前位置右侧的位置if (y + 1 < c && grid[x][y + 1] == 1 && !visited[x][y + 1]) {// 若右侧位置合法、为陆地且未被访问过，当前岛屿面积加 1sum++;// 标记右侧位置为已访问visited[x][y + 1] = true;// 将右侧位置加入队列q.push({x, y + 1});}// 检查当前位置上方的位置if (x - 1 >= 0 && grid[x - 1][y] == 1 && !visited[x - 1][y]) {// 若上方位置合法、为陆地且未被访问过，当前岛屿面积加 1sum++;// 标记上方位置为已访问visited[x - 1][y] = true;// 将上方位置加入队列q.push({x - 1, y});}// 检查当前位置下方的位置if (x + 1 < r && grid[x + 1][y] == 1 && !visited[x + 1][y]) {// 若下方位置合法、为陆地且未被访问过，当前岛屿面积加 1sum++;// 标记下方位置为已访问visited[x + 1][y] = true;// 将下方位置加入队列q.push({x + 1, y});}}// 更新最大岛屿面积ret = std::max(ret, sum);}}}// 返回最大岛屿面积return ret;}
};

130. 被围绕的区域

- **连接：**一个单元格与水平或垂直方向上相邻的单元格连接。- **区域：连接所有 **`'O'` 的单元格来形成一个区域。- **围绕：**如果您可以用 `'X'` 单元格 **连接这个区域**，并且区域中没有任何单元格位于 `board` 边缘，则该区域被 `'X'` 单元格围绕。

2.思路

注意是X和O不是数字0，。

找出边界上的 'O'：遍历矩阵的四条边界，将边界上的 'O' 加入队列，并标记为已访问。

广度优先搜索（BFS）：从队列中的边界 'O' 开始进行 BFS 遍历，将与这些边界 'O' 相连的所有 'O' 都标记为已访问。

替换未标记的 'O'：遍历整个矩阵，将未被标记为已访问的 'O' 替换为 'X'。

3.代码

class Solution {
public:// 用于标记矩阵中每个位置是否已被访问bool visited[201][201];void solve(std::vector<std::vector<char>>& board) {// 获取矩阵的行数int r = board.size();// 如果矩阵为空，直接返回if (r == 0) return;// 获取矩阵的列数int c = board[0].size();// 用于进行广度优先搜索（BFS）的队列，存储位置信息std::queue<std::pair<int, int>> q;// 第一步：将边界上的 'O' 加入队列并标记为已访问// 遍历矩阵的左右边界for (int i = 0; i < r; ++i) {// 检查左边界的元素是否为 'O' 且未被访问过if (board[i][0] == 'O' && !visited[i][0]) {// 标记该位置为已访问visited[i][0] = true;// 将该位置加入队列q.push({i, 0});}// 检查右边界的元素是否为 'O' 且未被访问过if (board[i][c - 1] == 'O' && !visited[i][c - 1]) {// 标记该位置为已访问visited[i][c - 1] = true;// 将该位置加入队列q.push({i, c - 1});}}// 遍历矩阵的上下边界for (int j = 0; j < c; ++j) {// 检查上边界的元素是否为 'O' 且未被访问过if (board[0][j] == 'O' && !visited[0][j]) {// 标记该位置为已访问visited[0][j] = true;// 将该位置加入队列q.push({0, j});}// 检查下边界的元素是否为 'O' 且未被访问过if (board[r - 1][j] == 'O' && !visited[r - 1][j]) {// 标记该位置为已访问visited[r - 1][j] = true;// 将该位置加入队列q.push({r - 1, j});}}// 第二步：进行广度优先搜索（BFS），标记与边界 'O' 相连的所有 'O'while (!q.empty()) {// 取出队列的队首元素int x = q.front().first, y = q.front().second;// 将队首元素出队q.pop();// 检查当前位置左侧元素是否为 'O' 且未被访问过if (y - 1 >= 0 && board[x][y - 1] == 'O' && !visited[x][y - 1]) {// 标记该位置为已访问visited[x][y - 1] = true;// 将该位置加入队列q.push({x, y - 1});}// 检查当前位置右侧元素是否为 'O' 且未被访问过if (y + 1 < c && board[x][y + 1] == 'O' && !visited[x][y + 1]) {// 标记该位置为已访问visited[x][y + 1] = true;// 将该位置加入队列q.push({x, y + 1});}// 检查当前位置上方元素是否为 'O' 且未被访问过if (x - 1 >= 0 && board[x - 1][y] == 'O' && !visited[x - 1][y]) {// 标记该位置为已访问visited[x - 1][y] = true;// 将该位置加入队列q.push({x - 1, y});}// 检查当前位置下方元素是否为 'O' 且未被访问过if (x + 1 < r && board[x + 1][y] == 'O' && !visited[x + 1][y]) {// 标记该位置为已访问visited[x + 1][y] = true;// 将该位置加入队列q.push({x + 1, y});}}// 第三步：将未被标记的 'O' 转换为 'X'for (int i = 0; i < r; ++i) {for (int j = 0; j < c; ++j) {// 检查当前位置是否为 'O' 且未被访问过if (board[i][j] == 'O' && !visited[i][j]) {// 将该位置的 'O' 替换为 'X'board[i][j] = 'X';}}}}
};

二、最短路径

边权为1或者边权相同就可以，相当于从起点有多个单位从不同路线同时向终点移动，且每个单位每次移动距离一样

//求顶点u到其他顶点的最短路径
void BFS_Distance(Graph G, int v) {for (i = 0; i < G.vexnum; ++i) {dis[i] = INT_MAX;//初始化路径长度path[i] = -1;//最短路径的前驱}dis[v] = 0;visited[v] = 1;q.push(v);while (!q.empty()) {int tmp = q.front();q.pop();for (int i = 0; i < G.vexnum; i++) {int w = G.vex[i];if (G.edge[tmp][i] && !visited[i]) {dis[w] = dis[tmp] + 1;path[w] = tmp;visited[w] = 1;q.push(w);}}}
}

1926. 迷宫中离入口最近的出口

输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
输出：1
解释：总共有 3 个出口，分别位于 (1,0)，(0,2) 和 (2,3) 。
一开始，你在入口格子 (1,2) 处。
- 你可以往左移动 2 步到达 (1,0) 。
- 你可以往上移动 1 步到达 (0,2) 。
从入口处没法到达 (2,3) 。
所以，最近的出口是 (0,2) ，距离为 1 步。

输入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
输出：2
解释：迷宫中只有 1 个出口，在 (1,2) 处。
(1,0) 不算出口，因为它是入口格子。
初始时，你在入口与格子 (1,0) 处。
- 你可以往右移动 2 步到达 (1,2) 处。
所以，最近的出口为 (1,2) ，距离为 2 步。

输入：maze = [[".","+"]], entrance = [0,0]
输出：-1
解释：这个迷宫中没有出口。

2.思路

初始化：将入口位置加入队列，并标记为已访问，同时初始化步数为 0。

BFS 遍历：

• 当队列不为空时，记录当前队列的大小，这个大小代表当前层的节点数量。
• 遍历当前层的所有节点，对于每个节点，检查它是否为出口（在迷宫边界且不是入口），如果是则返回当前步数。
• 若不是出口，检查该节点的上、下、左、右四个相邻节点，如果相邻节点在迷宫范围内、未被访问过且为通路，则标记为已访问并加入队列。

注意：层遍历的特性来保证首次找到的出口就是距离入口最近的出口，所以每层找完都向外扩张了一层

步数更新：遍历完当前层的所有节点后，步数加 1。

结果判断：如果队列为空还没有找到出口，则返回 -1。

3.代码

class Solution {
public:// 用于标记迷宫中每个位置是否已被访问bool visited[101][101];int nearestExit(std::vector<std::vector<char>>& maze, std::vector<int>& entrance) {// 获取迷宫的行数int r = maze.size();// 获取迷宫的列数int c = maze[0].size();// 用于进行广度优先搜索（BFS）的队列，存储位置信息std::queue<std::pair<int, int>> q;// 将入口位置加入队列q.push({entrance[0], entrance[1]});// 标记入口位置为已访问visited[entrance[0]][entrance[1]] = true;// 初始化步数为 0int ret = 0;// 当队列不为空时，继续进行 BFS 遍历while (!q.empty()) {// 记录当前队列的大小，即当前层的节点数量int size = q.size();// 遍历当前层的所有节点for (int i = 0; i < size; ++i) {// 取出队列的队首元素int x = q.front().first, y = q.front().second;// 将队首元素出队q.pop();// 判断当前位置是否到出口了if ((x == 0 || y == 0 || x == r - 1 || y == c - 1) &&(x != entrance[0] || y != entrance[1])) {// 如果是出口，返回当前步数return ret;}// 检查当前位置左侧元素是否为通路且未被访问过if (y - 1 >= 0 && visited[x][y - 1] == false &&maze[x][y - 1] == '.') {// 标记该位置为已访问visited[x][y - 1] = true;// 将该位置加入队列q.push({x, y - 1});}// 检查当前位置右侧元素是否为通路且未被访问过if (y + 1 < maze[0].size() && visited[x][y + 1] == false &&maze[x][y + 1] == '.') {// 标记该位置为已访问visited[x][y + 1] = true;// 将该位置加入队列q.push({x, y + 1});}// 检查当前位置上方元素是否为通路且未被访问过if (x - 1 >= 0 && visited[x - 1][y] == false &&maze[x - 1][y] == '.') {// 标记该位置为已访问visited[x - 1][y] = true;// 将该位置加入队列q.push({x - 1, y});}// 检查当前位置下方元素是否为通路且未被访问过if (x + 1 < maze.size() && visited[x + 1][y] == false &&maze[x + 1][y] == '.') {// 标记该位置为已访问visited[x + 1][y] = true;// 将该位置加入队列q.push({x + 1, y});}}// 遍历完当前层的所有节点后，步数加 1++ret;}// 如果队列为空还没有找到出口，返回 -1return -1;}
};

433. 最小基因变化

- 例如，`"AACCGGTT" --> "AACCGGTA"` 就是一次基因变化。

**输入：**start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
**输出：**1

**输入：**start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
**输出：**2

**输入：**start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
**输出：**3

2.思路

基因变了之后如果不在bank里就不能这么变。

数据预处理：将基因库 bank 中的所有基因序列存入一个无序集合 set 中，方便后续快速判断某个基因序列是否在基因库内。同时检查目标基因序列 endGene 是否在基因库中，若不在则直接返回 -1，表示无法完成转变。

初始化：把起始基因序列 startGene 加入队列 q 作为 BFS 的起始点，并将其标记为已访问，存入 visited 集合。初始化变化步数 ret 为 0。

BFS 遍历：

• 当队列不为空时，记录当前队列的大小 size，它代表当前层的基因序列数量。
• 遍历当前层的所有基因序列，对于每个基因序列：
  • 检查其是否等于目标基因序列 endGene，若是则返回当前步数 ret，由于是层序遍历，所以都是同时往外扩张，当start 和end 序列相等时，所用的步数最少
  • 遍历该基因序列的每一个位置，尝试将该位置的碱基替换为其他三种可能的碱基（A、C、G、T）。
  • 检查替换后的基因序列是否在基因库中且未被访问过，若是则将其加入队列 q 并标记为已访问。

步数更新：遍历完当前层的所有基因序列后，将步数 ret 加 1。

结果判断：若队列为空仍未找到目标基因序列，则返回 -1，表示无法完成转变。

3.代码

class Solution {
public:int minMutation(std::string startGene, std::string endGene,std::vector<std::string>& bank) {// 定义一个无序集合 set，用于存储基因库中的所有基因序列，方便快速查找// 遍历基因库 bank，将其中的每个基因序列插入到集合 set 中unordered_set<string> set(bank.begin(), bank.end());// 检查目标基因序列 endGene 是否在基因库 set// 中，若不在则无法完成转变，直接返回 -1if (set.find(endGene) == set.end())return -1;// 定义一个队列 q，用于进行广度优先搜索（BFS），将起始基因序列 startGene// 加入队列std::queue<std::string> q;q.push(startGene);// 初始化变化步数 ret 为 0int ret = 0;// 定义一个字符数组 bases，包含所有可能的碱基（A、C、G、T）char base[] = {'A', 'C', 'G', 'T'};// 定义一个无序集合 visited，用于记录已经访问过的基因序列，避免重复处理std::unordered_set<std::string> visited;// 将起始基因序列 startGene 标记为已访问，加入 visited 集合visited.insert(startGene);// 当队列 q 不为空时，继续进行 BFS 遍历while (!q.empty()) {// 记录当前队列的大小 size，即当前层的基因序列数量int size = q.size();// 遍历当前层的所有基因序列for (int i = 0; i < size; ++i) {// 取出队列 q 的队首元素，即当前要处理的基因序列std::string tmp = q.front();// 将队首元素从队列中移除q.pop();// 检查当前基因序列是否等于目标基因序列// endGene，若是则返回当前步数 retif (tmp == endGene) {return ret;}// 遍历当前基因序列的每一个位置for (int j = 0; j < tmp.length(); ++j) {// 保存当前位置的原始碱基char original = tmp[j];// 尝试将当前位置的碱基替换为其他三种可能的碱基for (int k = 0; k < 4; ++k) {// 将当前位置的碱基替换为新的碱基tmp[j] = base[k];// 检查替换后的基因序列是否在基因库 set 中且未被访问过if (set.find(tmp) != set.end() &&visited.find(tmp) == visited.end()) {// 若满足条件，则将替换后的基因序列加入队列 qq.push(tmp);// 并将其标记为已访问，加入 visited 集合visited.insert(tmp);}}// 恢复当前位置的原始碱基，以便继续处理下一个位置tmp[j] = original;}}// 遍历完当前层的所有基因序列后，将步数 ret 加 1ret++;}// 若队列为空仍未找到目标基因序列，返回 -1 表示无法完成转变return -1;}
};

LCR 108. 单词接龙

- 序列中第一个单词是 `beginWord` 。- 序列中最后一个单词是 `endWord` 。- 每次转换只能改变一个字母。- 转换过程中的中间单词必须是字典 `wordList` 中的单词。

**输入：**beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
**输出：**5
**解释：**一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

**输入：**beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
**输出：**0
**解释：**endWord "cog" 不在字典中，所以无法进行转换。

2.思路

和基因题目差不多，数据范围变大了，26的字母。“单词接龙” 无法完成转换时返回 0；“最小基因变化” 无法完成转变时返回 -1。“单词接龙” 中起始单词算一步，所以步数初始值为 1；“最小基因变化” 中步数初始值为 0。

3.代码

class Solution {
public:int ladderLength(string beginWord, string endWord,vector<string>& wordList) {// 定义一个无序集合 wordSet，用于存储字典中的所有单词，方便快速查找// 遍历字典 wordList，将其中的每个单词插入到集合 wordSet 中unordered_set<string> wordSet(wordList.begin(), wordList.end());// 检查目标单词 endWord 是否在字典 wordSet// 中，若不在则无法完成转换，直接返回 0if (wordSet.find(endWord) == wordSet.end())return 0;// 定义一个队列 q，用于进行广度优先搜索（BFS），将起始单词 beginWord// 加入队列queue<string> q;q.push(beginWord);// 初始化转换步数 step 为 1，因为起始单词算一步int step = 1;// 定义一个无序集合 visited，用于记录已经访问过的单词，避免重复处理unordered_set<string> visited;// 将起始单词 beginWord 标记为已访问，加入 visited 集合visited.insert(beginWord);// 定义所有可能的字母char base[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i','j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r','s', 't', 'u', 'v', 'w', 'x', 'y', 'z'};// 当队列 q 不为空时，继续进行 BFS 遍历while (!q.empty()) {// 记录当前队列的大小 size，即当前层的单词数量int size = q.size();// 遍历当前层的所有单词for (int i = 0; i < size; ++i) {// 取出队列 q 的队首元素，即当前要处理的单词string current = q.front();// 将队首元素从队列中移除q.pop();// 检查当前单词是否等于目标单词 endWord，若是则返回当前步数 stepif (current == endWord) {return step;}// 遍历当前单词的每一个位置for (int j = 0; j < current.length(); ++j) {// 保存当前位置的原始字母char tmp = current[j];// 尝试将当前位置的字母替换为其他 25 种可能的字母for (int k = 0; k < 26; k++) {// 将当前位置的字母替换为新的字母current[j] = base[k];// 检查替换后的单词是否在字典 wordSet 中且未被访问过if (wordSet.find(current) != wordSet.end() &&visited.find(current) == visited.end()) {// 若满足条件，则将替换后的单词加入队列 qq.push(current);// 并将其标记为已访问，加入 visited 集合visited.insert(current);}}// 恢复当前位置的原始字母，以便继续处理下一个位置current[j] = tmp;}}// 遍历完当前层的所有单词后，将步数 step 加 1step++;}// 若队列为空仍未找到目标单词，返回 0 表示无法完成转换return 0;}
};

675. 为高尔夫比赛砍树-hard待研究

- `0` 表示障碍，无法触碰- `1` 表示地面，可以行走- `比 1 大的数` 表示有树的单元格，可以行走，数值表示树的高度

**输入：**forest = [[1,2,3],[0,0,4],[7,6,5]]
**输出：**6
**解释：**沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。

**输入：**forest = [[1,2,3],[0,0,0],[7,6,5]]
**输出：**-1
**解释：**由于中间一行被障碍阻塞，无法访问最下面一行中的树。

**输入：**forest = [[2,3,4],[0,0,5],[8,7,6]]
**输出：**6
**解释：**可以按与示例 1 相同的路径来砍掉所有的树。
(0,0) 位置的树，可以直接砍去，不用算步数。

2.思路

砍树要按从矮到高的顺序，路过某棵树不一定非要砍，可以往回走，起点不一定是地面。

1. 找出所有树的位置和高度：遍历二维网格，记录所有树的位置和高度，并按照树的高度进行排序。
2. 计算从当前位置到下一棵树的最短路径：使用广度优先搜索（BFS）算法计算从当前位置到下一棵树的最短移动步数。
3. 依次砍树：按照树的高度从小到大的顺序，依次计算从当前位置到下一棵树的最短路径，并累加步数。如果在某一步无法到达下一棵树，返回 -1。

3.代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>using namespace std;class Solution {
private:vector<vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// BFS 计算从 start 到 end 的最短路径int bfs(const vector<vector<int>>& forest, const pair<int, int>& start, const pair<int, int>& end) {int rows = forest.size();int cols = forest[0].size();vector<vector<bool>> visited(rows, vector<bool>(cols, false));queue<pair<pair<int, int>, int>> q;q.push({start, 0});visited[start.first][start.second] = true;while (!q.empty()) {auto [pos, steps] = q.front();q.pop();if (pos == end) {return steps;}for (const auto& dir : directions) {int newRow = pos.first + dir[0];int newCol = pos.second + dir[1];if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols &&forest[newRow][newCol] > 0 && !visited[newRow][newCol]) {q.push({{newRow, newCol}, steps + 1});visited[newRow][newCol] = true;}}}return -1;}public:int cutOffTree(vector<vector<int>>& forest) {int rows = forest.size();int cols = forest[0].size();vector<pair<int, pair<int, int>>> trees;// 找出所有树的位置和高度for (int i = 0; i < rows; ++i) {for (int j = 0; j < cols; ++j) {if (forest[i][j] > 1) {trees.emplace_back(forest[i][j], make_pair(i, j));}}}// 按树的高度排序sort(trees.begin(), trees.end());pair<int, int> current = {0, 0};int totalSteps = 0;// 依次砍树for (const auto& [_, target] : trees) {int steps = bfs(forest, current, target);if (steps == -1) {return -1;}totalSteps += steps;current = target;}return totalSteps;}
};

三、多源 BFS

单源最短路径：只有一个起点和一个终点，求最短路径。多源最短路径：有多个起点到一个终点的最短路径。多源BFS：用BFS解决边权为1的多源最短路径。

解决：把所有起点当作一个大起点，就变成了单源最短路径，把所有起点放到队列里，一层一层往外扩展

LCR 107. 01 矩阵

**输入：**mat =** **[[0,0,0],[0,1,0],[0,0,0]]
**输出：**[[0,0,0],[0,1,0],[0,0,0]]

**输入：**mat = [[0,0,0],[0,1,0],[1,1,1]]
**输出：**[[0,0,0],[0,1,0],[1,2,1]]

2.思路

用二维矩阵ans存储最短距离，初始值全为0；使用二维矩阵vis存储每个位置是否扩散过，初始值为false。
将所有0加入队列，并将其vis置为true（标记扩散）
只要队列不为空，弹出队首元素，并向四个方向扩散（更新ans）、加入队尾、标记扩散。
注意，扩散更新ans应该与标记vis、加入队尾同步进行。如果是在弹出队列的时候标记扩散，而在扩散的时候不标记，在当前一轮的广度搜索中，可能重复计算。
下面是图示：

初始状态时的mat矩阵

将所有0加入队列，并标记访问

弹出0、扩散四个方向更新ans、标记vis。

弹出1、扩散四个方向更新ans、标记vis。

弹出2…扩散结束，队列为空。

3.代码

注意：这里不需要严格区分不同层次的元素，所以在while后面没有写for，其实按照模板加上for也不会错，具体来说，队列里的元素顺序不会影响最终结果，因为无论元素在队列里的先后顺序如何，只要按照 BFS 的规则不断扩展，每个位置第一次被访问时的距离一定是最短的。

class Solution {
public:vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {// 获取矩阵的行数int rows = mat.size();// 获取矩阵的列数int cols = mat[0].size();// 初始化结果矩阵 ans，用于存储每个位置到最近 0 的距离，初始值都为 0vector<vector<int>> ans(rows, vector<int>(cols, 0));// 初始化访问标记矩阵 vis，用于标记每个位置是否已被访问，初始值都为 falsevector<vector<bool>> vis(rows, vector<bool>(cols, false));// 初始化队列 q，用于 BFS 遍历queue<pair<int, int>> q;// 遍历矩阵 mat，将所有值为 0 的位置加入队列 q，并标记为已访问for (int i = 0; i < rows; ++i) {for (int j = 0; j < cols; ++j) {if (mat[i][j] == 0) {// 值为 0 的位置到最近 0 的距离为 0ans[i][j] = 0;// 标记该位置为已访问vis[i][j] = true;// 将该位置加入队列 qq.push({i, j});}}}// 当队列 q 不为空时，继续进行 BFS 遍历while (!q.empty()) {// 取出队首元素的横坐标int x = q.front().first;// 取出队首元素的纵坐标int y = q.front().second;// 将队首元素从队列中移除q.pop();// 检查当前位置的左侧位置if (y - 1 >= 0 && vis[x][y - 1] == false) {// 将左侧位置加入队列 qq.push({x, y - 1});// 标记左侧位置为已访问vis[x][y - 1] = true;// 左侧位置到最近 0 的距离为当前位置到最近 0 的距离加 1ans[x][y - 1] = ans[x][y] + 1;}// 检查当前位置的右侧位置if (y + 1 < cols && vis[x][y + 1] == false) {// 将右侧位置加入队列 qq.push({x, y + 1});// 标记右侧位置为已访问vis[x][y + 1] = true;// 右侧位置到最近 0 的距离为当前位置到最近 0 的距离加 1ans[x][y + 1] = ans[x][y] + 1;}// 检查当前位置的上方位置if (x - 1 >= 0 && vis[x - 1][y] == false) {// 将上方位置加入队列 qq.push({x - 1, y});// 标记上方位置为已访问vis[x - 1][y] = true;// 上方位置到最近 0 的距离为当前位置到最近 0 的距离加 1ans[x - 1][y] = ans[x][y] + 1;}// 检查当前位置的下方位置if (x + 1 < rows && vis[x + 1][y] == false) {// 将下方位置加入队列 qq.push({x + 1, y});// 标记下方位置为已访问vis[x + 1][y] = true;// 下方位置到最近 0 的距离为当前位置到最近 0 的距离加 1ans[x + 1][y] = ans[x][y] + 1;}}// 返回结果矩阵 ansreturn ans;}
};

1020. 飞地的数量

**输入：**grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
**输出：**3
**解释：**有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。

**输入：**grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
**输出：**0
**解释：**所有 1 都在边界上或可以到达边界。

2.思路

思路参考上面 130. 被围绕的区域，思路差不多。

3.代码

class Solution {
public:// 用于标记网格中每个单元格是否已被访问bool visited[501][501];int numEnclaves(std::vector<std::vector<int>>& grid) {// 获取网格的行数int r = grid.size();// 获取网格的列数int c = grid[0].size();// 用于进行广度优先搜索（BFS）的队列，存储单元格的坐标std::queue<std::pair<int, int>> q;// 遍历网格的左右边界for (int i = 0; i < r; ++i) {// 检查左边界的元素是否为 1 且未被访问过if (!visited[i][0] && grid[i][0] == 1) {// 标记该位置为已访问visited[i][0] = true;// 将该位置加入队列q.push({i, 0});}// 检查右边界的元素是否为 1 且未被访问过if (grid[i][c - 1] == 1 && !visited[i][c - 1]) {// 标记该位置为已访问visited[i][c - 1] = true;// 将该位置加入队列q.push({i, c - 1});}}// 遍历网格的上下边界for (int j = 0; j < c; ++j) {// 检查上边界的元素是否为 1 且未被访问过if (grid[0][j] == 1 && !visited[0][j]) {// 标记该位置为已访问visited[0][j] = true;// 将该位置加入队列q.push({0, j});}// 检查下边界的元素是否为 1 且未被访问过if (grid[r - 1][j] == 1 && !visited[r - 1][j]) {// 标记该位置为已访问visited[r - 1][j] = true;// 将该位置加入队列q.push({r - 1, j});}}// 进行广度优先搜索（BFS）while (!q.empty()) {// 取出队列的队首元素，获取其横坐标int x = q.front().first;// 取出队列的队首元素，获取其纵坐标int y = q.front().second;// 将队首元素从队列中移除q.pop();// 检查当前位置左侧元素是否为 1 且未被访问过if (y - 1 >= 0 && grid[x][y - 1] == 1 && !visited[x][y - 1]) {// 标记该位置为已访问visited[x][y - 1] = true;// 将该位置加入队列q.push({x, y - 1});}// 检查当前位置右侧元素是否为 1 且未被访问过if (y + 1 < c && grid[x][y + 1] == 1 && !visited[x][y + 1]) {// 标记该位置为已访问visited[x][y + 1] = true;// 将该位置加入队列q.push({x, y + 1});}// 检查当前位置上方元素是否为 1 且未被访问过if (x - 1 >= 0 && grid[x - 1][y] == 1 && !visited[x - 1][y]) {// 标记该位置为已访问visited[x - 1][y] = true;// 将该位置加入队列q.push({x - 1, y});}// 检查当前位置下方元素是否为 1 且未被访问过if (x + 1 < r && grid[x + 1][y] == 1 && !visited[x + 1][y]) {// 标记该位置为已访问visited[x + 1][y] = true;// 将该位置加入队列q.push({x + 1, y});}}// 用于存储飞地的数量int ret = 0;// 遍历整个网格for (int i = 0; i < r; ++i) {for (int j = 0; j < c; ++j) {// 如果当前单元格的值为 1 且未被访问过，则它是飞地if (grid[i][j] == 1 && !visited[i][j]) {// 飞地数量加 1ret++;}}}// 返回飞地的数量return ret;}
};

1765. 地图中的最高点

- 如果 `isWater[i][j] == 0` ，格子 `(i, j)` 是一个 **陆地** 格子。- 如果 `isWater[i][j] == 1` ，格子 `(i, j)` 是一个 **水域** 格子。

- 每个格子的高度都必须是非负的。- 如果一个格子是 **水域** ，那么它的高度必须为 `0` 。- 任意相邻的格子高度差 **至多** 为 `1` 。当两个格子在正东、南、西、北方向上相互紧挨着，就称它们为相邻的格子。（也就是说它们有一条公共边）

输入：isWater = [[0,1],[0,0]]
输出：[[1,0],[2,1]]
解释：上图展示了给各个格子安排的高度。
蓝色格子是水域格，绿色格子是陆地格。

输入：isWater = [[0,0,1],[1,0,0],[0,0,0]]
输出：[[1,1,0],[0,1,1],[1,2,2]]
解释：所有安排方案中，最高可行高度为 2 。
任意安排方案中，只要最高高度为 2 且符合上述规则的，都为可行方案。

2.思路

上面图是输出图，0是水，题目中的数值可以转化成，走几步找到最近的水源，也可以理解成，从水源出发，走几步可以遍历所有的陆地。

思路和 LCR 107. 01 矩阵 差不多

地图中的最高点：将矩阵中值为 1 的位置（水域）作为起始点，因为水域高度固定为 0。代码中当 isWater[i][j] == 1 时，将该位置加入队列并标记为已访问，结果矩阵 ans 中该位置的值设为 0，mat[ i ] [ j ] == 0。

3.代码

class Solution {
public:vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {int rows = isWater.size();int cols = isWater[0].size();// 初始化结果矩阵 ans，用于存储每个位置的高度，初始值都为 0vector<vector<int>> ans(rows, vector<int>(cols, 0));// 初始化访问标记矩阵 vis，用于标记每个位置是否已被访问，初始值都为 falsevector<vector<bool>> vis(rows, vector<bool>(cols, false));// 初始化队列 q，用于 BFS 遍历queue<pair<int, int>> q;// 遍历矩阵 isWater，将所有水域（值为 1 的位置）加入队列 q，并标记为已访问for (int i = 0; i < rows; ++i) {for (int j = 0; j < cols; ++j) {if (isWater[i][j] == 1) {// 水域位置高度为 0ans[i][j] = 0;// 标记该位置为已访问vis[i][j] = true;// 将该位置加入队列 qq.push({i, j});}}}// 当队列 q 不为空时，继续进行 BFS 遍历while (!q.empty()) {// 取出队首元素的横坐标int x = q.front().first;// 取出队首元素的纵坐标int y = q.front().second;// 将队首元素从队列中移除q.pop();// 检查当前位置的上方位置if (x - 1 >= 0 && !vis[x - 1][y]) {// 上方位置的高度为当前位置高度加 1ans[x - 1][y] = ans[x][y] + 1;// 标记上方位置为已访问vis[x - 1][y] = true;// 将上方位置加入队列 qq.push({x - 1, y});}// 检查当前位置的下方位置if (x + 1 < rows && !vis[x + 1][y]) {// 下方位置的高度为当前位置高度加 1ans[x + 1][y] = ans[x][y] + 1;// 标记下方位置为已访问vis[x + 1][y] = true;// 将下方位置加入队列 qq.push({x + 1, y});}// 检查当前位置的左侧位置if (y - 1 >= 0 && !vis[x][y - 1]) {// 左侧位置的高度为当前位置高度加 1ans[x][y - 1] = ans[x][y] + 1;// 标记左侧位置为已访问vis[x][y - 1] = true;// 将左侧位置加入队列 qq.push({x, y - 1});}// 检查当前位置的右侧位置if (y + 1 < cols && !vis[x][y + 1]) {// 右侧位置的高度为当前位置高度加 1ans[x][y + 1] = ans[x][y] + 1;// 标记右侧位置为已访问vis[x][y + 1] = true;// 将右侧位置加入队列 qq.push({x, y + 1});}}// 返回结果矩阵 ansreturn ans;}
};

1162. 地图分析

**输入：**grid = [[1,0,1],[0,0,0],[1,0,1]]
**输出：**2
**解释： **
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。

**输入：**grid = [[1,0,0],[0,0,0],[0,0,0]]
**输出：**4
**解释： **
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。

2.思路

3.代码

class Solution {
public:int  maxDistance(vector<vector<int>>& mat) {// 获取矩阵的行数int rows = mat.size();// 获取矩阵的列数int cols = mat[0].size();// 初始化结果矩阵 ans，用于存储每个位置到最近 0 的距离，初始值都为 0vector<vector<int>> ans(rows, vector<int>(cols, 0));// 初始化访问标记矩阵 vis，用于标记每个位置是否已被访问，初始值都为 falsevector<vector<bool>> vis(rows, vector<bool>(cols, false));// 初始化队列 q，用于 BFS 遍历queue<pair<int, int>> q;// 遍历矩阵 mat，将所有值为 0 的位置加入队列 q，并标记为已访问for (int i = 0; i < rows; ++i) {for (int j = 0; j < cols; ++j) {if (mat[i][j] == 1) {// 值为 0 的位置到最近 0 的距离为 0ans[i][j] = 0;// 标记该位置为已访问vis[i][j] = true;// 将该位置加入队列 qq.push({i, j});}}}// 当队列 q 不为空时，继续进行 BFS 遍历while (!q.empty()) {// 取出队首元素的横坐标int x = q.front().first;// 取出队首元素的纵坐标int y = q.front().second;// 将队首元素从队列中移除q.pop();// 检查当前位置的左侧位置if (y - 1 >= 0 && vis[x][y - 1] == false) {// 将左侧位置加入队列 qq.push({x, y - 1});// 标记左侧位置为已访问vis[x][y - 1] = true;// 左侧位置到最近 0 的距离为当前位置到最近 0 的距离加 1ans[x][y - 1] = ans[x][y] + 1;}// 检查当前位置的右侧位置if (y + 1 < cols && vis[x][y + 1] == false) {// 将右侧位置加入队列 qq.push({x, y + 1});// 标记右侧位置为已访问vis[x][y + 1] = true;// 右侧位置到最近 0 的距离为当前位置到最近 0 的距离加 1ans[x][y + 1] = ans[x][y] + 1;}// 检查当前位置的上方位置if (x - 1 >= 0 && vis[x - 1][y] == false) {// 将上方位置加入队列 qq.push({x - 1, y});// 标记上方位置为已访问vis[x - 1][y] = true;// 上方位置到最近 0 的距离为当前位置到最近 0 的距离加 1ans[x - 1][y] = ans[x][y] + 1;}// 检查当前位置的下方位置if (x + 1 < rows && vis[x + 1][y] == false) {// 将下方位置加入队列 qq.push({x + 1, y});// 标记下方位置为已访问vis[x + 1][y] = true;// 下方位置到最近 0 的距离为当前位置到最近 0 的距离加 1ans[x + 1][y] = ans[x][y] + 1;}}int ret = 0;for (int i = 0; i < rows; ++i) {for (int j = 0; j < cols; ++j) {ret = max(ret, ans[i][j]);}}return ret==0?-1:ret;}
};

四、拓扑排序

找到做事情的先后顺序，结果可能不是唯一的。应用：判断有向图中是否有环

1. 找出图中入度为0的点，然后输出
2. 删除与该点的连接边
3. 重复前面操作直到没有入度为0的点为止（可能有环）

207. 课程表

- 例如，先修课程对 `[0, 1]` 表示：想要学习课程 `0` ，你需要先完成课程 `1` 。

**输入：**numCourses = 2, prerequisites = [[1,0]]
**输出：**true
**解释：**总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

**输入：**numCourses = 2, prerequisites = [[1,0],[0,1]]
**输出：**false
**解释：**总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

2.思路

edges用于存储边，indeg用于存储每个节点入度为多少。首先初始化这两个变量，构建边和计算每个节点的入度，之后将入度为0的节点放到队列当中，拓扑排序：判断从a->b是否有边，如果有就将a放到队列当中，并且将b的入度减一，结束时，判断已访问数量是否等于总课程数量。

邻接矩阵：空间： (O(V^2)) 时间：(O(V^2 + E))，其中 (V) 是节点数（课程数），(E) 是边数（依赖关系数）

邻接表：空间： (O(V + E)) 时间：总体时间复杂度为 (O(V + E))

resize：如果新的大小比原来大，在容器末尾添加元素；如果新的大小比原来小，会删除超出部分的元素。可以指定初始值

reserve：它只改变容器的容量（即容器能够容纳的元素数量），而不改变容器的大小（即实际存储的元素数量）。

大小（size），实际存储的元素个数

容量（capacity），容器在不重新分配内存的情况下能够容纳的最大元素个数

3.代码

邻接矩阵：

class Solution {
public:vector<vector<int>> edges; // 存储边bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<int> indeg(numCourses, 0);// 存储每个节点入度为多少edges.resize(numCourses);for (auto& e : edges) {e.resize(numCourses, 0);}// bi->aifor (auto& pair : prerequisites) {int ai = pair[0];int bi = pair[1];edges[bi][ai] = 1;++indeg[ai]; // 入度增加}queue<int> q;for (int i = 0; i < indeg.size(); ++i) {if (indeg[i] == 0)q.push(i);}int visited = 0;while (!q.empty()) {++visited;int tmp = q.front();q.pop();// 遍历当前节点的所有邻接节点for (int i = 0; i<numCourses; ++i) {if(edges[tmp][i] ==  1){--indeg[i];if(indeg[i] == 0){q.push(i);}}}}return visited==numCourses;}
};

邻接表：

class Solution {
public:vector<std::vector<int>> edges; // 存储边vector<int> indeg;         // 存储每个节点入度为多少bool canFinish(int numCourses, std::vector<std::vector<int>>& prerequisites) {// 初始化邻接表edges.resize(numCourses);indeg.resize(numCourses);// 构建邻接表和计算入度for (auto& pair : prerequisites) {int ai = pair[0];int bi = pair[1];edges[bi].push_back(ai); // 将 ai 加入 bi 的邻接表++indeg[ai]; // 入度增加}// 将入度为 0 的节点加入队列std::queue<int> q;for (int i = 0; i < indeg.size(); ++i) {if (indeg[i] == 0)q.push(i);}int visited = 0;while (!q.empty()) {++visited;int tmp = q.front();q.pop();// 遍历当前节点的所有邻接节点（使用邻接表的方式）for (int neighbor : edges[tmp]) {--indeg[neighbor]; // 邻接节点的入度减 1if (indeg[neighbor] == 0) {q.push(neighbor); // 若邻接节点入度变为 0，加入队列}}}return visited == numCourses;}
};

210. 课程表 II

- 例如，想要学习课程 `0` ，你需要先完成课程 `1` ，我们用一个匹配来表示：`[0,1]` 。

**输入：**numCourses = 2, prerequisites = [[1,0]]
**输出：**[0,1]
**解释：**总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 `[0,1] 。`

**输入：**numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
**输出：**[0,2,1,3]
**解释：**总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 `[0,1,2,3]` 。另一个正确的排序是 `[0,2,1,3]` 。

**输入：**numCourses = 1, prerequisites = []
**输出：**[0]

2.思路

初始化数据结构：

• 创建一个 numCourses * numCourses 的邻接矩阵 edges 来表示课程之间的依赖关系，初始时所有元素为 0。
• 创建一个长度为 numCourses 的入度数组 indeg，用于记录每门课程的前置课程数量，初始时所有元素为 0。

构建图和计算入度：

• 遍历 prerequisites 数组，对于每一个依赖关系 [ai, bi]，表示学习课程 ai 之前需要先学习课程 bi。
• 在邻接矩阵 edges 中，将 edges[bi][ai] 设置为 1，表示存在从 bi 到 ai 的边。
• 同时，将课程 ai 的入度（即 indeg[ai]）加 1。

初始化队列：

• 遍历入度数组 indeg，将入度为 0 的课程加入队列 q。入度为 0 的课程表示没有前置课程，可以直接学习。

拓扑排序过程：

• 当队列 q 不为空时，取出队列头部的课程 tmp，将其加入结果数组 ret 中，表示该课程可以开始学习。
• 遍历所有课程，检查与 tmp 存在依赖关系的课程 i（即 edges[tmp][i] == 1）。
• 对于这些课程 i，将其入度减 1。如果减 1 后入度变为 0，说明其所有前置课程都已学习完，将其加入队列 q。

结果判断：

• 拓扑排序结束后，检查结果数组 ret 的长度是否等于 numCourses。
• 如果相等，说明可以完成所有课程的学习，返回 ret 作为课程的学习顺序；否则，说明图中存在环，无法完成所有课程的学习，返回一个空数组。

3.代码

class Solution {
public:// 邻接矩阵，用于存储课程之间的依赖关系std::vector<std::vector<int>> edges;std::vector<int> findOrder(int numCourses, std::vector<std::vector<int>>& prerequisites) {vector<int> indeg(numCourses, 0);// 存储每个节点入度为多少// 调整邻接矩阵的大小，使其为 numCourses 行edges.resize(numCourses);// 对邻接矩阵的每一行进行初始化，使其有 numCourses 列，初始值都为 0for (int i = 0; i < edges.size(); ++i) {edges[i].resize(numCourses, 0);}// 遍历先决条件数组，构建邻接矩阵和更新入度数组for (auto& e : prerequisites) {// 获取当前依赖关系中需要学习的课程int ai = e[0];// 获取当前依赖关系中的前置课程int bi = e[1];// 在邻接矩阵中标记从 bi 到 ai 存在依赖关系edges[bi][ai] = 1;// 增加课程 ai 的入度++indeg[ai];}// 创建一个队列，用于存储入度为 0 的课程std::queue<int> q;// 遍历入度数组，将入度为 0 的课程加入队列for (int i = 0; i < indeg.size(); ++i) {if (indeg[i] == 0) {q.push(i);}}// 用于存储课程的学习顺序std::vector<int> ret;// 当队列不为空时，进行拓扑排序操作while (!q.empty()) {// 取出队列头部的课程int tmp = q.front();// 将队列头部的课程从队列中移除q.pop();// 将该课程添加到学习顺序结果中ret.push_back(tmp);// 遍历所有课程，检查与当前课程存在依赖关系的课程for (int i = 0; i < numCourses; ++i) {// 如果存在从当前课程 tmp 到课程 i 的依赖关系if (edges[tmp][i] == 1) {// 减少课程 i 的入度--indeg[i];// 如果课程 i 的入度变为 0，说明其前置课程都已学习完，可以加入队列if (indeg[i] == 0) {q.push(i);}}}}// 判断是否能完成所有课程if (ret.size() != numCourses) {// 如果学习顺序结果中的课程数量不等于总课程数，说明存在环，无法完成所有课程，返回空数组return {};}// 若能完成所有课程，返回课程的学习顺序return ret;}
};

LCR 114. 火星词典-hard待研究

- 在第一个不同字母处，如果 `s` 中的字母在这门外星语言的字母顺序中位于 `t` 中字母之前，那么 `s` 的字典顺序小于 `t` 。- 如果前面 `min(s.length, t.length)` 字母都相同，那么 `s.length < t.length` 时，`s` 的字典顺序也小于 `t` 。

**输入：**words = ["wrt","wrf","er","ett","rftt"]
**输出：**"wertf"

**输入：**words = ["z","x"]
**输出：**"zx"

**输入：**words = ["z","x","z"]
**输出：**""
**解释：**不存在合法字母顺序，因此返回 ""。

2.思路

示例解释

• 从 "wrt" 和 "wrf" 这两个单词来看，它们的前两个字母 "wr" 相同，而第三个字母不同，一个是 "t" 一个是 "f"，并且 "wrt" 在 "wrf" 前面，这就表明在火星语言的字典序里，'t' 排在 'f' 前面。
• 从 "wrf" 和 "er" 来看，因为 "wrf" 在前，"er" 在后，而 "w" 和 "e" 是第一个不同的字母，所以 'w' 排在 'e' 前面。
• 从 "er" 和 "ett" 来看，"er" 在前，"ett" 在后，'e' 相同，第二个字母不同，所以 'r' 排在 't' 前面。
• 从 "ett" 和 "rftt" 来看，"ett" 在前，"rftt" 在后，第一个字母不同，所以 'e' 排在 'r' 前面。

3.代码

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>class Solution {
public:std::string alienOrder(std::vector<std::string>& words) {// 邻接表，graph[i] 存储字母 i 指向的字母集合std::vector<std::vector<char>> graph(26);// 合并入度和出现标记，值为 -1 表示出现过但未统计入度，非负表示入度std::unordered_map<char, int> states;// 遍历所有单词，统计出现的字母for (const auto& word : words) {for (char c : word) {if (states.find(c) == states.end()) {states[c] = -1; // 标记字母出现过}}}// 构建图和计算入度for (int i = 0; i < words.size() - 1; ++i) {const std::string& word1 = words[i];const std::string& word2 = words[i + 1];int minLen = std::min(word1.length(), word2.length());bool foundDifference = false;for (int j = 0; j < minLen; ++j) {if (word1[j] != word2[j]) {char u = word1[j];char v = word2[j];bool edgeExists = false;for (char neighbor : graph[u - 'a']) {if (neighbor == v) {edgeExists = true;break;}}if (!edgeExists) {graph[u - 'a'].push_back(v);if (states[v] == -1) {states[v] = 1; // 初始化入度为 1} else {++states[v]; // 入度加 1}}foundDifference = true;break;}}// 如果一个单词是另一个单词的前缀，且长单词在前，顺序不合理if (!foundDifference && word1.length() > word2.length()) {return "";}}// 将入度为 0 的字母加入队列std::queue<char> q;for (const auto& pair : states) {if (pair.second == 0 || pair.second == -1) {q.push(pair.first);}}// 存储拓扑排序的结果std::string result;while (!q.empty()) {char u = q.front();q.pop();result += u;// 遍历当前字母的所有邻接字母for (char v : graph[u - 'a']) {--states[v];if (states[v] == 0) {q.push(v);}}}// 如果结果的长度不等于出现过的字母数量，说明存在环，无法得到有效字典序if (result.length() != states.size()) {return "";}return result;}
};