您现在的位置是：首页 >技术交流 >东华大学高级程序设计(DFS和BFS篇)网站首页技术交流
东华大学高级程序设计(DFS和BFS篇)
简介东华大学高级程序设计(DFS和BFS篇)
目录
DFS&BFS
课程表
题目
你必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
struct GraphNode{
int label;
vector<GraphNode*> neighbors;
GraphNode(int x):label(x) {};
};
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<GraphNode*> graph;
vector<int> degree;//入度数组
for(int i =0;i<numCourses;i++){
degree.push_back(0);
graph.push_back(new GraphNode(i));//创建图节点
}
for(int i=0;i<prerequisites.size();i++){//创建每个节点的邻接表
GraphNode *begin=graph[prerequisites[i][1]];
GraphNode *end=graph[prerequisites[i][0]];
begin->neighbors.push_back(end);
degree[prerequisites[i][0]]++;//课程一 的入度+1
}
queue<GraphNode *> Q;
for(int i=0;i<numCourses;i++){//i:0 1
//把 入度为0 的节点先放进Q队列中
if(degree[i]==0){
Q.push(graph[i]);
}
}
while(!Q.empty()){
GraphNode *node =Q.front();
Q.pop();
for(int i=0;i<node->neighbors.size();i++){
degree[node->neighbors[i]->label] = degree[node->neighbors[i]->label]-1;
if(degree[node->neighbors[i]->label]==0){//当前节点入度为0
Q.push(node->neighbors[i]);
}
}
}
//释放节点
for(int i=0;i<graph.size();i++){
delete graph[i];
}
for(int i=0;i<degree.size();i++){//判断入度数组中的点是否全都是0
if(degree[i]) return false;
}
return true;
}
};
int main()
{
vector<vector<int>> prerequisites;
int numCourses,m;
cin>>numCourses>>m;
int c1,c2;
int ch;
for(int i=0; i<m; i++)
{
vector<int> aPrerequisite;
cin>>c1>>c2;
aPrerequisite.push_back(c1);
aPrerequisite.push_back(c2);
prerequisites.push_back(aPrerequisite);
}
bool res=Solution().canFinish(numCourses,prerequisites);
cout<<(res?"true":"false")<<endl;
return 0;
}
重新安排行程
题目
给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。
说明:
如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前
所有的机场都用三个大写字母表示（机场代码）。
假定所有机票至少存在一种合理的行程。
代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<string> result;
vector<bool> used;
bool find = false;
static bool cmp(vector<string>& a, vector<string>& b){
if (a[0] < b[0]) return true;
if (a[0] > b[0]) return false;
return a[1] < b[1];
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
used.resize(tickets.size());
sort(tickets.begin(), tickets.end(), cmp);
result.push_back("JFK");
backtracking(tickets, "JFK");
return result;
}
void backtracking(vector<vector<string>>& tickets, string start){
if (result.size() == tickets.size() + 1){
find = true;
return;
}
for(int i = 0; i < tickets.size(); i++){
if (tickets[i][0] > start) return;
// 使用当前的票
if (!used[i] && (start == tickets[i][0])){
result.push_back(tickets[i][1]);
used[i] = true;
backtracking(tickets, tickets[i][1]);
if (find) return;
used[i] = false;
result.pop_back();
while (i + 1 < tickets.size() && tickets[i + 1][1] == tickets[i][1]) i = i + 1;
}
}
}
};
int main()
{
vector<vector<string>> tickets;
int m;
cin>>m;
string a1,a2;
for(int i=0; i<m; i++)
{
vector<string> aTicket;
cin>>a1>>a2;
aTicket.push_back(a1);
aTicket.push_back(a2);
tickets.push_back(aTicket);
}
vector<string> res=Solution().findItinerary(tickets);
for(int i=0; i<res.size(); i++)
{
if (i>0)
cout<<" ";
cout<<res[i];
}
return 0;
}
递增子序列
题目
给定一个整型数组, 你的任务是找到所有该数组的递增子序列并输出其数量，递增子序列的长度至少是2。
代码
#include <bits/stdc++.h>
using namespace std;
void depthFirstSearch(vector<int>& numbers, int index, set<vector<int>>& uniqueResults, vector<int>& currentSequence) {
// 只有当当前序列长度大于等于2时才加入结果集
if (currentSequence.size() >= 2) {
uniqueResults.insert(currentSequence);
}
// 从当前索引开始遍历数组
for (int j = index; j < numbers.size(); ++j) {
// 跳过不符合递增条件的元素
if (!currentSequence.empty() && currentSequence.back() > numbers[j]) continue;
// 添加当前元素到序列
currentSequence.push_back(numbers[j]);
// 递归调用，注意从下一个元素开始遍历
depthFirstSearch(numbers, j + 1, uniqueResults, currentSequence);
// 回溯，移除当前元素
currentSequence.pop_back();
}
}
vector<vector<int>> findSubarraysWithIncreasingOrder(vector<int>& numbers) {
set<vector<int>> uniqueResults; // 使用set去重
vector<int> currentSequence;
depthFirstSearch(numbers, 0, uniqueResults, currentSequence);
// 将set转换为vector并返回
return vector<vector<int>>(uniqueResults.begin(), uniqueResults.end());
}
int main() {
int n;
cin >> n;
vector<int> numbers(n);
for (int i = 0; i < n; ++i) {
cin >> numbers[i];
}
vector<vector<int>> results = findSubarraysWithIncreasingOrder(numbers);
// 输出结果的数量和具体结果
cout << results.size() << endl;
// for (const auto& seq : results) {
// cout << "{ ";
// for (int num : seq) {
// cout << num << " ";
// }
// cout << "}" << endl;
// }
return 0;
}
大礼包
题目
在商店中， 有许多在售的物品。
然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。
现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。
每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。
任意大礼包可无限次购买。
代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
// price[i] 是第 i 件物品的价格
//数组special表示大礼包，special[i]的长度为n+1
//special[i][j] 表示第 i 个大礼包中内含第 j 件物品的数量，
//且 special[i][n] （也就是数组中的最后一个整数）为第 i 个大礼包的价格
// 整数数组 needs 表示购物清单，needs[i]是需要购买第i件物品的数量
//返回 确切 满足购物清单所需花费的最低价格
//商品不能多买。我们可以先求出不使用任何需要special花的钱数作为结果res的初始值，表示最差需要的钱。
int res = 0;
for (int i = 0; i < needs.size(); i++)
res += needs[i] * price[i];//最差需要的钱
// 我们遍历每一个special
// 尝试使用这个special（如果使用完这个使得结果不合法就跳过）,使用完一个合法special，更新needs，继续dfs搜索下一层。
// 枚举每个special，尝试使用这1个special
for (const auto& sp : special) { // special = [ [3,0,5] , [1,2,10] ] needs = [3,2]
if (canUseThisSp(sp, needs)) {
// 开始尝试这个sp使用一次
vector<int> newNeeds(needs.size());
for (size_t i = 0; i < needs.size(); i++) {
newNeeds[i] = needs[i] - sp[i];
}
// 使用这个sp的花费，继续递归 sp.back()返回sp中的最后一个值
res = min(res, sp.back() + shoppingOffers(price, special, newNeeds));
}
}
return res;
}
private://逐个礼包进行判断
// 检查是否可以使用这个 special[i][j] 表示第 i 个大礼包中内含第 j 件物品的数量
// special = [ [3,0,5] , [1,2,10] ] , sp进行遍历 needs = [3,2] 需要购买第 i 件物品的数量
bool canUseThisSp(const vector<int>& sp, const vector<int>& needs) {
for (size_t i = 0; i < needs.size(); i++) {
if (needs[i] < sp[i]) { //需要的数量<礼包拥有的数量时 不可用 返回false
return false;
}
}
return true;
}
};
int main()
{
vector<int> price;
vector<vector<int>> special;
vector<int> needs;
int n,m;
cin>>n;
int p,need;
for(int i=0; i<n; i++)
{
cin>>p;
price.push_back(p);
}
for(int i=0; i<n; i++)
{
cin>>need;
needs.push_back(need);
}
cin>>m;
for(int i=0; i<m; i++)
{
vector<int> oneSpecial;
int qty;
for(int j=0; j<n; j++)
{
cin>>qty;
oneSpecial.push_back(qty);
}
int amount;
cin>>amount;
oneSpecial.push_back(amount);
special.push_back(oneSpecial);
}
int res=Solution().shoppingOffers(price, special, needs);
cout<<res<<endl;
return 0;
}
金字塔转换矩阵
题目
现在，我们用一些方块来堆砌一个金字塔。 每个方块用仅包含一个字母的字符串表示。
使用三元组表示金字塔的堆砌规则如下：
对于三元组(A, B, C) ，“C”为顶层方块，方块“A”、“B”分别作为方块“C”下一层的的左、右子块。当且仅当(A, B, C)是被允许的三元组，我们才可以将其堆砌上。
初始时，给定金字塔的基层 bottom，用一个字符串表示。一个允许的三元组列表 allowed，每个三元组用一个长度为 3 的字符串表示。
如果可以由基层一直堆到塔尖就返回 true ，否则返回 false 。
代码
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
class Solution {
public:
string currentPath;
vector<char> graph[7][7];
bool dfs(string bottom, string top, int start) {
if (bottom.size() == 1) return true;
if (start == bottom.size() - 1) {
return dfs(top, "", 0);
}
int left = bottom[start] - 'A';
int right = bottom[start + 1] - 'A';
for (int i = 0; i < graph[left][right].size(); i++) {
if (dfs(bottom, top + graph[left][right][i], start + 1)) return true;
}
return false;
}
bool pyramidTransition(string base, vector<string>& rules) {
for (const auto& rule : rules) {
graph[rule[0] - 'A'][rule[1] - 'A'].emplace_back(rule[2]);
}
return dfs(base, "", 0);
}
};
int main() {
string base, rule;
vector<string> rules;
cin >> base;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> rule;
rules.push_back(rule);
}
bool result = Solution().pyramidTransition(base, rules);
cout << (result ? "true" : "false") << endl;
return 0;
}
扫雷游戏
题目
让我们一起来玩扫雷游戏！
给定一个代表游戏板的二维字符矩阵。 ‘M’ 代表一个未挖出的地雷，‘E’ 代表一个未挖出的空方块，‘B’ 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（‘1’ 到 ‘8’）表示有多少地雷与这块已挖出的方块相邻，‘X’ 则表示一个已挖出的地雷。
现在给出在所有未挖出的方块中（‘M’或者’E’）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：
如果一个地雷（‘M’）被挖出，游戏就结束了- 把它改为 ‘X’。
如果一个没有相邻地雷的空方块（‘E’）被挖出，修改它为（‘B’），并且所有和其相邻的未挖出方块都应该被递归地揭露。
如果一个至少与一个地雷相邻的空方块（‘E’）被挖出，修改它为数字（‘1’到’8’），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回面板。
代码
#include <bits/stdc++.h>
#include <unordered_map>
#include <vector>
using namespace std;
// 'M' 代表一个 未挖出的地雷
// 'E' 代表一个 未挖出的空方块
// 'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的 空白方块
// 数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻
// 'X' 则表示一个已挖出的地雷
// 返回相应位置被点击后对应的面板：
/*如果一个地雷（'M'）被挖出，游戏就结束了 - 把它改为 'X'。
如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的未挖出方块都应该被递归地揭露。
如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回面板。*/
class Solution {
public:
// 静态初始化
int moveX[8] = {1, -1, 0, 0, 1, 1, -1, -1};
int moveY[8] = {0, 0, 1, -1, 1, -1, 1, -1};
// 递归探索函数
void dfs(vector<vector<char>>& board, int x, int y, int rows, int cols) {
if (x < 0 || x >= rows || y < 0 || y >= cols || board[x][y] != 'E') {
return;
}
int mines = 0;
for (int i = 0; i < 8; i++) {
int nextX = x + moveX[i];
int nextY = y + moveY[i];
if (nextX >= 0 && nextX < rows && nextY >= 0 && nextY < cols && board[nextX][nextY] == 'M') {
mines++;
}
}
if (mines == 0) {
board[x][y] = 'B';
for (int i = 0; i < 8; i++) {
dfs(board, x + moveX[i], y + moveY[i], rows, cols);
}
} else {
board[x][y] = '0' + mines;
}
}
// 更新棋盘状态
vector<vector<char>> unlockBoard(vector<vector<char>>& board, vector<int>& click) {
int x = click[0];
int y = click[1];
if (board[x][y] == 'M') {
board[x][y] = 'X';
} else {
dfs(board, x, y, board.size(), board[0].size());
}
return board;
}
};
int main()
{
vector<vector<char> > board;
int m,n,x,y;
cin>>m;
cin>>n;
char ch;
for(int i=0; i<m; i++)
{
vector<char> aLine;
for(int j=0; j<n; j++)
{
cin>>ch;
aLine.push_back(ch);
}
board.push_back(aLine);
}
cin>>x>>y;
vector<int> click;
click.push_back(x);
click.push_back(y);
vector<vector<char>> res=Solution().unlockBoard(board,click);
for(int i=0; i<res.size(); i++)
{
vector<char> aLine = res[i];
for(int j=0; j<aLine.size(); j++)
cout<<aLine[j];
cout<<endl;
}
return 0;
}
01 矩阵
题目
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
//输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到 最近的 0 的距离
//多元最短路径
int n=mat.size();
int m=mat[0].size();
vector<vector<int>> distance(n,vector<int>(m,INT_MAX));//大小与mat相同的距离结果矩阵
queue<pair<int,int>> q;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(mat[i][j]==0){
distance[i][j]=0;
q.push({i,j});//把为0的数全部加到队列中
}
}
}
//定义搜索的方向数组 左 右 下 上
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
while(!q.empty()){
int x=q.front().first;
int y=q.front().second;
q.pop();
for(int i=0;i<4;i++){
int newx=x+dx[i];
int newy=y+dy[i];
if(newx>=0&&newy>=0&&newy<m&&newx<n){
if(distance[newx][newy]>distance[x][y]+1){
distance[newx][newy]=distance[x][y]+1;
q.push(make_pair(newx,newy));
}
}
}
}
return distance;
}
};
int main()
{
vector<vector<int> > matrix;
int m,n;
cin>>m;
cin>>n;
char ch;
for(int i=0; i<m; i++)
{
vector<int> aLine;
for(int j=0; j<n; j++)
{
cin>>ch;
aLine.push_back(ch-'0');
}
matrix.push_back(aLine);
}
vector<vector<int>> res=Solution().updateMatrix(matrix);
for(int i=0; i<res.size(); i++)
{
vector<int> aLine = res[i];
for(int j=0; j<aLine.size(); j++)
cout<<aLine[j];
cout<<endl;
}
return 0;
}
被围绕的区域
题目
给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。
找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void solve(vector<vector<char>>& board) {
int m = board.size();
int n = board[0].size();
queue<pair<int, int>> q;
// 处理边界的 'O'
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') {
q.emplace(i, 0);
board[i][0] = 'A';
}
if (board[i][n - 1] == 'O') {
q.emplace(i, n - 1);
board[i][n - 1] = 'A';
}
}
for (int i = 1; i < n - 1; i++) {
if (board[0][i] == 'O') {
q.emplace(0, i);
board[0][i] = 'A';
}
if (board[m - 1][i] == 'O') {
q.emplace(m - 1, i);
board[m - 1][i] = 'A';
}
}
// 方向数组
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int newx = x + dx[i];
int newy = y + dy[i];
if (newx >= 0 && newy >= 0 && newy < n && newx < m && board[newx][newy] == 'O') {
q.push({newx, newy});
board[newx][newy] = 'A';
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'A') {
board[i][j] = 'O';
} else {
board[i][j] = 'X';
}
}
}
}
};
int main() {
int m, n;
cin >> m >> n;
vector<vector<char>> board(m, vector<char>(n));
// 输入矩阵
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> board[i][j];
}
}
Solution solution;
solution.solve(board);
// 输出结果
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cout << board[i][j];
}
cout << endl;
}
return 0;
}
跳跃游戏 III
题目
这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。
请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。
注意，不管是什么情况下，你都无法跳到数组之外。
代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canReach(vector<int>& arr, int start) {
//位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]
//判断自己是否能够跳到对应元素值为 0 的 任一 下标处 下标从0开始的
if(arr[start]==0) return true;
int s=arr.size();
queue<int> q;
vector<bool> used(s);
q.push(start);//将起始位置加入到队列中
used[start]=true;
while(!q.empty()){
int pos=q.front();
q.pop();
if (pos + arr[pos] < s && !used[pos + arr[pos]]) {//当前下标没被搜索过
if (arr[pos + arr[pos]] == 0) {
return true;
}
q.push(pos + arr[pos]);
used[pos + arr[pos]] = true;
}
if (pos - arr[pos] >= 0 && !used[pos - arr[pos]]) {
if (arr[pos - arr[pos]] == 0) {
return true;
}
q.push(pos - arr[pos]);
used[pos - arr[pos]] = true;
}
}
return false;
}
};
int main(){
int n,start,e;
vector<int> arr;
cin>>n;
for(int i=0;i<n;i++){
cin>>e;
arr.push_back(e);
}
cin>>start;
bool res=Solution().canReach(arr,start);
cout<<(res?"true":"false")<<endl;
return 0;
}
跳跃游戏 IV
题目
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标：
i + 1 满足：i + 1 < arr.length
i - 1 满足：i - 1 >= 0
j 满足：arr[i] == arr[j] 且 i != j
请你返回到达数组最后一个元素的下标处所需的最少操作次数 。
注意：任何时候你都不能跳到数组外面。
代码
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <limits>
using namespace std;
class Solution {
public:
int minJumps(vector<int>& arr) {
int n = arr.size();
if (n <= 1) return 0;
unordered_map<int, vector<int>> indicesOfValue;
for (int i = 0; i < n; i++) {
indicesOfValue[arr[i]].push_back(i);
}
vector<bool> visited(n, false);
visited[0] = true;
queue<int> que;
que.push(0);
int level = 0;
while (!que.empty()) {
++level;
for (int i = que.size(); i > 0; --i) {
int index = que.front();
que.pop();
if (index == n - 1) return level - 1;
vector<int>& nextIndices = indicesOfValue[arr[index]];
nextIndices.push_back(index - 1);
nextIndices.push_back(index + 1);
for (int nextIndex : nextIndices) {
if (nextIndex >= 0 && nextIndex < n && !visited[nextIndex])
{
visited[nextIndex] = true;
que.push(nextIndex);
}
}
nextIndices.clear();
}
}
return -1;
}
};
int main() {
int n;
int e;
vector<int> arr;
cin>>n;
for(int i=0;i<n;i++){
cin>>e;
arr.push_back(e);
}
int res=Solution().minJumps(arr);
cout<<res<<endl;
return 0;
}
后续内容持续更新~~~
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。
站长推荐
- U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - 分享几个国内免费的ChatGPT镜像网址(亲测有效)
分享几个国内免费的ChatGPT镜像网址(亲测有效) - QT多线程的5种用法，通过使用线程解决UI主界面的耗时操作代码，防止界面卡死。
QT多线程的5种用法，通过使用线程解决UI主界面的耗时操作代码，防止界面卡死。... - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权