深度优先搜索(dfs)问题集合

迷宫(dfs)一天Extense在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由 n∗n 的格点组成,每个格点只有2种状态,.和#,前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上,Extense想要从点A走


宽度优先搜索(BFS)问题集合

池塘计数(bfs)农夫约翰有一片 N∗M 的矩形土地。最近,由于降雨的原因,部分土地被水淹没了。现在用一个字符矩阵来表示他的土地。每个单元格内,如果包含雨水,则用”W”表示,如果不含雨水,则用”.”表示。现在,约翰想知道他的土地中形成了多少片池塘。每组相连的积水单元格集合可以看作是一片池塘。每个单元


prim算法和kruskal算法求最小生成树

prim算法给定一个 n 个点 m 条边的无向图,图中可能存在重边和自环,边权可能为负数。求最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible。给定一张边带权的无向图 G=(V,E),其中 V 表示图中点的集合,E 表示图中边的集合,n=|V|,m=|E|。由 V 中的全部


spfa算法及Floyd算法

spfa适用范围:存在负权边求最短路给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 impossible。数据保证不存在负权回路。输入格式第一行包含整数 n 和 m。接下来 m 行每


01背包、完全背包、多重背包问题

01背包问题有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi,价值是 wi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。输入格式第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。接下来有 N 行,每行


2022.3.26 动态规划,迪杰斯特拉算法题目

1. 小红杀怪题目描述小红在一个游戏里杀怪。这是个回合制游戏,小红和两只怪物相遇了。第一只怪物有a血量,第二只怪物有b血量。小红有两个技能:第一个技能叫火球术,效果是对单体怪物造成x伤害。第二个技能叫烈焰风暴,效果是对每只怪物造成y伤害。小红想知道,自己最少使用多少次技能,可以击杀这两只怪物?(当怪


迪杰斯特拉(dijkstra)算法

迪杰斯特拉算法适用范围:处理权值为正的最短路问题步骤:初始化d[1]=0,其他d[n]=INT_MAXs中放入已经确定最短路的点遍历,把不在s中的距离最近的点,加入到s更新所有点的距离给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为正值。请你求出 1 号点到 n 号点的最短


Bellman-Ford算法

Bellman-Ford算法适用范围:处理权值带负数的,且有边数限制的最短路问题给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离,如果无法从 1 号点走到 n 号点,输出 impossible。注意:图中可


并查集

并查集作用:将两个集合合并查询两个元素是否在同一个集合内一共有 n 个数,编号是 1∼n,最开始每个数各自在一个集合中。现在要进行 mm 个操作,操作共有两种:M a b,将编号为 a 和 b 的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;Q a b,询问编号为 a 和 b


字典树(前缀树)

字典树用于快速查询字符串字典树的几种操作:把字符串插入字典树void insert(string s){ int p=0; for(int i=0;i<s.size();i++) { int q=s[i]-'a'; if(