搜索结果
查询Tags标签： bfs，共有 162条记录-
Problem P30. [算法课分支限界法]组合
分支树的思想遍历所有可能性，然后加上限制条件，剪枝掉不符合条件的分支，比如只能选出k个数进行组合，那么curk==k时结束这个分支，还有就是注意边界的问题，curn>n。#include<iostream> #include<bits/stdc++.h> #include<cstdio> #include<st…
2022/9/17 1:18:30 人评论 次浏览 -
【BFS】算法模板与思路
1.BFS算法的基础理论是什么？ BFS算法名叫宽度优先搜索，虽然我能理解深度优先搜索，但我却不是很能理解宽度优先搜索。 一个很关键的点在于：宽度优先搜索是一个迭代的算法，不是递归的算法。 与DFS之间的区别： DFS是利用栈的特性进行搜索的。 而BFS是利用队列的特性进行…
2022/9/3 1:23:37 人评论 次浏览 -
目录
一：基础算法 快速排序（求第k小的数） 归并排序（逆序对数量） 高精度 前缀和&差分 双指针 贪心 递推 递归 二分 倍增 位运算 二：数据结构 链表 单调栈 单调队列 哈夫曼树 堆 ST表 并查集 树状数组 线段树 字典树（trie树） 哈希表 笛卡尔树 基环树 平衡树 三：搜索…
2022/8/6 23:27:09 人评论 次浏览 -
Bfs---flood fill算法
1 1097. 池塘计数2 农夫约翰有一片 N∗M 的矩形土地。3 4 最近，由于降雨的原因，部分土地被水淹没了。5 6 现在用一个字符矩阵来表示他的土地。7 8 每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。9 10 现在，约翰想知道他的土地中形成了多少…
2022/7/5 1:20:47 人评论 次浏览 -
1022 魔法数字 bfs 剪枝
链接：https://ac.nowcoder.com/acm/contest/23156/1022来源：牛客网 题目描述牛妹给牛牛写了一个数字n，然后又给自己写了一个数字m，她希望牛牛能执行最少的操作将他的数字转化成自己的。 操作共有三种，如下： 1.在当前数字的基础上加一，如：4转化为5 2.在当前数字的基…
2022/7/2 23:25:09 人评论 次浏览 -
1018 maze 优先队列+bfs
链接：https://ac.nowcoder.com/acm/contest/23156/1018来源：牛客网 题目描述小明来到一个由n x m个格子组成的迷宫，有些格子是陷阱，用#表示，小明进入陷阱就会死亡，.表示没有陷阱。小明所在的位置用S表示，目的地用T表示。 小明只能向上下左右相邻的格子移动，每移动…
2022/7/2 6:20:20 人评论 次浏览 -
1019 wyh的吃鸡 bfs+优先队列
链接：https://ac.nowcoder.com/acm/problem/15445来源：牛客网 题目描述最近吃鸡游戏非常火，你们wyh学长也在玩这款游戏，这款游戏有一个非常重要的过程，就是要跑到安全区内，否则就会中毒持续消耗血量，我们这个问题简化如下 假设地图为n*n的一个图，图中有且仅有一块…
2022/7/2 6:20:11 人评论 次浏览 -
1091. 二进制矩阵中的最短路径(标准BFS)
1091. 二进制矩阵中的最短路径给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。 二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下…
2022/6/25 23:34:36 人评论 次浏览 -
day1.矩阵距离
BFS证明 多源BFS 求矩阵中每个0到最近的1的距离(有很多源点,求到其他点的到每个源点的最短距离)矩阵距离1.按距离扩展：距离为0的点、为1、为2、为3...的点。 2.建立虚拟源点,求虚拟源点到其他点的最短距离(Dijkstra)上图Dijkstra求从虚拟源点到其他点的最短距离,等价于BF…
2022/5/11 23:17:27 人评论 次浏览 -
算法-岛屿问题-DFS和BFS
岛屿问题解决方案 dfsvoid dfs(int[][] grid, int r, int c) {// 判断 base case，是否在界内if (!inArea(grid, r, c)) {return;}// 如果这个格子不是岛屿，直接返回if (grid[r][c] != 1) {return;}grid[r][c] = 2; // 将格子标记为「已遍历过」// 访问上、下、左、右四个…
2022/5/4 17:12:47 人评论 次浏览 -
429. N 叉树的层序遍历(BFS)
429. N 叉树的层序遍历给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。示例 1：输入：root = [1,null,3,2,4,null,5,6] 输出：[[1],[3,2,4],[5,6]]示例 2：输入：root = [1,…
2022/5/2 6:14:33 人评论 次浏览 -
993. 二叉树的堂兄弟节点(BFS)
993. 二叉树的堂兄弟节点在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。 如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。 我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。 …
2022/5/2 6:13:03 人评论 次浏览 -
695. 岛屿的最大面积(BFS)
695. 岛屿的最大面积给你一个大小为 m x n 的二进制矩阵 grid 。 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。 岛屿的面积是岛上值为 1 的单元格…
2022/5/2 6:12:51 人评论 次浏览 -
java实现图的DFS和BFS
java实现图的DFS和BFS public class GraphDemo {/*** 存储顶点集合*/private ArrayList<String> vertexList;/*** 存储图对应的领结矩阵*/private int[][] edges;/*** 表示边的数目*/private int numOfEdges;/*** 记录是否被访问*/private boolean[] isVisited;publ…
2022/4/24 22:12:38 人评论 次浏览 -
深夜emo，摸了一发bfs，真想闭关了
#include<bits/stdc++.h> #define rep(i,x,n) for(int i=x;i<=n;i++) using namespace std;struct node{ int x,y; };int n; int f[500][500];//记录步长和判重 int g[500][500]; int dx[]={1,0,-1,0},dy[]={0,1,0,-1};void bfs() {queue<node> q;q.push(…
2022/4/8 6:19:03 人评论 次浏览
