在 染色的时候统计面积即可

visited[next_x][next_y] = true;
++area;

两个步骤：

• 从地图周边出发，将 ‘O’ 都做上标记，visited = true
• 然后再遍历一遍地图，遇到 ‘O’ 且没做过标记的，那么都是地图中间的 ‘O’ ，全部改成 ‘X’ 就行

class Solution {
public:// 太平洋：i == 0 || j == 0// 大西洋：i == m-1 || j == n-1// 方式1：从每个节点出发，如果可以到达太平洋且大西洋，记录结果// 方式2：从四周出发，逆向找可达节点int direction[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};// array<array<int, 2>, 4> direction = {-1, 0, 0, -1, 1, 0, 0, 1};void dfs(const vector<vector<int>>& heights, vector<vector<bool>>& visited, int x, int y) {for (int i = 0; i < 4; ++i) {int next_x = x + direction[i][0], next_y = y + direction[i][1];if (next_x < 0 || next_x >= heights.size() || \next_y < 0 || next_y >= heights[0].size() || \visited[next_x][next_y] == true ||heights[next_x][next_y] < heights[x][y]) {continue;}visited[next_x][next_y] = true;dfs(heights, visited, next_x, next_y);}}vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {int m = heights.size(), n = heights[0].size();vector<vector<bool>> pacific_visited(m, vector<bool>(n, false));vector<vector<bool>> atlantic_visited(m, vector<bool>(n, false));for (int i = 0; i < n; ++i) {if (pacific_visited[0][i] == false) {pacific_visited[0][i] = true;dfs(heights, pacific_visited, 0, i);}}for (int i = 1; i < m; ++i) {if (pacific_visited[i][0] == false) {pacific_visited[i][0] = true;dfs(heights, pacific_visited, i, 0);}}for (int i = 0; i < n; ++i) {if (atlantic_visited[m-1][i] == false) {atlantic_visited[m-1][i] = true;dfs(heights, atlantic_visited, m-1, i);}}for (int i = 0; i < m - 1; ++i) {if (atlantic_visited[i][n-1] == false) {atlantic_visited[i][n-1] = true;dfs(heights, atlantic_visited, i, n-1);}}vector<vector<int>> result;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (pacific_visited[i][j] && atlantic_visited[i][j]) {result.push_back({i,j});}}}return result;}
};

class Solution {
public:int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {int m = maze.size(), n = maze[0].size();int x = entrance[0], y = entrance[1];queue<pair<int, int>> que;maze[x][y] = '+';que.push({x, y});// 定义四个方向：上、下、左、右const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int steps = 0;// 广度优先搜索while (!que.empty()) {int q_size = que.size();for (int i = 0; i < q_size; ++i) {auto [cur_x, cur_y] = que.front();que.pop();for (int d = 0; d < 4; ++d) {int next_x = cur_x + dir[d][0];int next_y = cur_y + dir[d][1];// 检查边界条件if (next_x < 0 || next_x >= m || \next_y < 0 || next_y >= n || \maze[next_x][next_y] == '+') {continue;}// 如果到达边界并且不是入口，返回步数if (next_x == 0 || next_x == m - 1 ||\next_y == 0 || next_y == n - 1) {return steps + 1;}// 标记为已访问，并将其加入队列maze[next_x][next_y] = '+';que.push({next_x, next_y});}}++steps;}// 如果没有找到出口，返回 -1return -1;}
};

class Solution {
public:bool canConvert(const string& s1, const string& s2) {int diffCount = 0;for (int i = 0; i < s1.size(); ++i) {if (s1[i] != s2[i]) {if (++diffCount > 1) return false;}}return true;}int minMutation(string startGene, string endGene, vector<string>& bank) {if (startGene == endGene) return 0;int n = bank.size();int startIndex = -1, endIndex = -1;// 查找 startGene 和 endGene 在 bank 中的位置for (int i = 0; i < n; ++i) {if (bank[i] == endGene) endIndex = i;else if (bank[i] == startGene) startIndex = i;}// 如果终止基因不在 bank 中，直接返回 -1if (endIndex == -1) return -1;// 如果起始基因不在 bank 中，则将其作为附加节点处理if (startIndex == -1) startIndex = n;// 构建邻接表vector<list<int>> adj(n + 1);// 如果 startGene 不在 bank 中，构造与它相邻的节点if (startIndex == n) {for (int i = 0; i < n; ++i) {if (canConvert(startGene, bank[i])) {adj[n].push_back(i);}}}// 构造 bank 中基因的邻接关系for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {if (canConvert(bank[i], bank[j])) {adj[i].push_back(j);adj[j].push_back(i);}}}// BFS 进行最短路径搜索queue<int> q;vector<bool> visited(n + 1, false);q.push(startIndex);visited[startIndex] = true;int steps = 0;while (!q.empty()) {int que_size = q.size();while (que_size--) {int node = q.front();q.pop();// 找到终止基因，返回步数if (node == endIndex) return steps;// 遍历邻居节点for (int neighbor : adj[node]) {if (!visited[neighbor]) {visited[neighbor] = true;q.push(neighbor);}}}++steps; // 每一轮BFS增加一步}// 如果找不到转换路径，返回 -1return -1;}
};

和最小基因变化基本没区别

• 本题为有向无环图，如果存在环的话需要加一个 visited 数组
• 时间复杂度：O(2^n)，最坏情况下可能有 2 的 n 次方条路径，其中 n 是图的节点数。
• 空间复杂度：O(n)，递归深度最深为 n（即从 0 到目标节点的最长路径长度），以及存储路径所需的空间。

// 有向无环图求所有可行路径
// 如果存在环的话需要加一个 visited 数组
class Solution {
public:vector<vector<int>> result;vector<int> path;void dfs(vector<vector<int>>& graph, int start) {if (start == graph.size() - 1) {result.push_back(path);}for (auto& next : graph[start]) {path.push_back(next);dfs(graph, next);path.pop_back();}}vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {path.push_back(0);dfs(graph, 0);return result; }
};

如果边的两个节点已经出现在同一个集合里，说明这条边的两个节点已经连在一起了，再加入这条边一定就出现环了。

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {int n = edges.size();UnionSet union_set(n + 1);for (auto& edge : edges) {int u = edge[0], v = edge[1];if (union_set.IsConnected(u, v)) {return {u, v};} else {union_set.Join(u, v);}}return {};}

参考链接：【困难题简单做】分类讨论+并查集，击破hard

class Solution {
public:// 查找冗余的有向边vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {int n = edges.size();vector<int> parent(n + 1, 0);vector<int> edge_to_remove1, edge_to_remove2;int two_in_node = -1;// 检测入度为2的情况for (auto& edge : edges) {int u = edge[0], v = edge[1];if (parent[v] == 0) {parent[v] = u;} else {// 发现入度为2的节点 vtwo_in_node = v;edge_to_remove1 = {parent[v], v}; // 之前的边edge_to_remove2 = {u, v}; // 当前的边break;}}// 重建并查集，处理有环的情况UnionSet union_set(n + 1);for (auto& edge : edges) {int u = edge[0], v = edge[1];if (edge == edge_to_remove2) {// 跳过第二条边，先验证第一条边continue;}if (union_set.IsConnected(u, v)) {// 出现环//  + 如果不存在入度为2的节点，只需要考虑环的问题//  + 说明正是[u,v]导致环的出现，删除 [u, v] 即可    if (two_in_node == -1) return edge;//  + 存在入度为 2 的节点//  + edge_to_remove1 必然属于这个环的一部分//  + 否则就会出现两条不合法的边了，不合题意//  + 因此我们删除两个不合法的交集，也即 edge_to_remove1return edge_to_remove1;}union_set.Join(u, v);}// 循环正常结束，说明没有出现环// 说明异常情况为：存在入度为 2 的节点// 删除最后一条导致入度为 2 的边，也即 edge_to_remove2return edge_to_remove2;}
};

• 遍历所有边，记录所有节点的入度，将入度为 0 的节点加入队列和结果数组
• 当队列不为空时，从队列中弹出节点，遍历节点的所有邻居，将邻居的入度减1，如果此时邻居的入度为0，则将该邻居加入队列和结果数组
• 队列为空，若结果数组的长度不等于节点个数，说明存在环，否则返回结果数组

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<int> indegrees(numCourses, 0);vector<list<int>> adj(numCourses);for (const auto& pre : prerequisites) {++indegrees[pre[0]];adj[pre[1]].push_back(pre[0]);}int count = 0;queue<int> que;for (int i = 0; i < numCourses; ++i) {if (indegrees[i] == 0) {que.push(i);++count;}}while (!que.empty()) {int cur = que.front();que.pop();for (auto next : adj[cur]) {if (--indegrees[next] == 0) {que.push(next);++count;}}}return (count == numCourses);}
};

• 使用 堆来存储当前最短路径节点 {节点到起点的距离, 节点索引}
• 每次从优先队列中选择当前距离最小的未处理节点

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <list>
using namespace std;int dijkstra(vector<list<pair<int, int>>>& adj_list) {int n = adj_list.size() - 1; int start = 1, end = n;vector<int> costs(n + 1, INT_MAX);	// 记录距离vector<int> visited(n + 1, false);	// 标记是否找到最短路		// 堆存储 {节点到起点的距离，节点索引}priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;// 初始化costs[start] = 0;pq.push({0, start});while (!pq.empty()) {// 每次从优先队列中选择当前距离最小的未处理节点int cost = pq.top().first;int cur = pq.top().second;pq.pop();if (visited[cur]) continue;	// 节点已经访问过，跳过visited[cur] = true;			// 未访问过，标记为访问过if (cur == end) return costs[end];	// 到达终点// 遍历相邻节点for (auto& [next, time] : adj_list[cur]) {if (!visited[next] && costs[cur] + time < costs[next]) {// 找到更短的路径了   costs[next] = costs[cur] + time;pq.push({costs[next], next});}}}return -1;  // 如果没有路径到达终点
}int main(int argc, char* argv[]) {if (argc == 1) return -1;freopen(argv[1], "r", stdin);int n, m;cin >> n >> m;  // n 个 车站 m 条公路vector<list<pair<int, int>>> adj_list(n + 1);for (int i = 0; i < m; ++i) {   // 输入 m 条边：起点 终点 和 时间int start, end, time;cin >> start >> end >> time;adj_list[start].push_back({end, time});}cout << dijkstra(adj_list) << endl;return 0;
}

#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;int main() {int n, m, p1, p2, val;cin >> n >> m;vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, INT_MAX)));  // 因为边的最大距离是10^4for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid[p1][p2][0] = val;grid[p2][p1][0] = val; // 注意这里是双向图}// 开始 floydfor (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (grid[i][k][k-1] == INT_MAX || grid[k][j][k-1] == INT_MAX) {grid[i][j][k] = grid[i][j][k-1];} else {grid[i][j][k] = min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1]);}      }}}// 输出结果int z, start, end;cin >> z;while (z--) {cin >> start >> end;if (grid[start][end][n] == INT_MAX) cout << -1 << endl;else cout << grid[start][end][n] << endl;}
}

空间优化

#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;int main() {int n, m, p1, p2, val;cin >> n >> m;vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));  // 因为边的最大距离是10^4for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid[p1][p2] = val;grid[p2][p1] = val; // 注意这里是双向图}// 开始 floydfor (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (grid[i][k] != INT_MAX && grid[k][j] != INT_MAX) {grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);}      }}}// 输出结果int z, start, end;cin >> z;while (z--) {cin >> start >> end;if (grid[start][end] == INT_MAX) cout << -1 << endl;else cout << grid[start][end] << endl;}
}

图-最小生成树-Prim(普里姆)算法和Kruskal(克鲁斯卡尔)算法

#include<iostream>
#include<vector>
#include <climits>using namespace std;int main() {int v, e;   // 顶点数和边数cin >> v >> e;vector<vector<int>> grid(v + 1, vector<int>(v + 1, INT_MAX));int x, y, k;    // 起点，终点和权值while (e--) {cin >> x >> y >> k;grid[x][y] = k;grid[y][x] = k;   // 无向图}// Prim算法部分vector<int> minDist(v + 1, INT_MAX);        // 所有节点到最小生成树的最小距离vector<bool> isInTree(v + 1, false);        // 是否已经在最小生成树中minDist[1] = 0;                             // 从第1个节点开始int result = 0;for (int i = 1; i <= v; i++) {int cur = -1;int minVal = INT_MAX;// 找到距离当前生成树最近的节点for (int j = 1; j <= v; j++) {if (!isInTree[j] && minDist[j] < minVal) {minVal = minDist[j];cur = j;}}// 如果没有找到合适的节点，则图不连通if (cur == -1) {cout << "Graph is not connected" << endl;return -1;}isInTree[cur] = true;result += minVal;  // 把该点与生成树相连的最小边的权值加入结果// 更新其他节点到生成树的最短距离for (int j = 1; j <= v; j++) {if (!isInTree[j] && grid[cur][j] != INT_MAX && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];}}}// 输出最小生成树的权重cout << result << endl;return 0;
}