bfs

Getting Zero time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Suppose you have an integer ......

## BFS ### 目录 Content - 概述 - 问题思考与性质 - 典型应用 - 优化与扩展 ## Part 1 概述 ### I.什么是BFS？ >广度优先搜索(breadth first search)，是以同层可达状态优先，一层层向外扩展的搜索算法。一般以队列实现 ### II.算法 ......

https://www.acwing.com/problem/content/1102/ 数据范围为1e5 实际上还可以再继续细分,加入特判来优化耗时,但是意义不大 #include<iostream> #include<cstring> #include<cstdio> #include<queu ......

题目描述 有一个 n×m 的棋盘，在某个点 (x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。 输入格式 输入只有一行四个整数，分别为 n,m,x,y。 输出格式 一个 n×m 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 −1）。 输入输出样例 输入 #1复制 3 3 ......

# 算法 in Golang：Breadth-first search # （BFS、广度优先搜索） ## 最短路径问题 Shortest-path problem - 从 A 到 F 点有多条路径 ## 解决问题的算法 Breadth-first Search（广度优先搜索） 1. 将问题建模为图 ......

#include <iostream> #include <queue> using namespace std; struct node { int x,y; int step; }st,ed; const int maxn=100; int n,m;//图的边界 int gx,gy;//终点位置 ......

# 图Graph ## 1. 图的基本介绍 ### 1.1 为什么要有图 众所周知，数据结构中已经有线性表和树结构，但是线性表局限于一个直接前驱和一个直接后继的关系（eg.链表），树也只能有一个直接前驱（即父节点），当我们需要表示**多对多的关系**时，就需要用到图这个数据结构。 ### 1.2 举 ......

核心就是利用队列 Q: 如何区分下一层? A: 将当前队列中的所有节点进形扩散 # 框架 ```java // 计算从起点 start 到终点 target 的最近距离 int BFS(Node start, Node target) { Queue q; // 核心数据结构 Set visited ......

给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。 输入格式: 输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每 ......

八数码 题目 在一个 $3×3$ 的网格中，$1∼8$ 这 $8$ 个数字和一个 $X$ 恰好不重不漏地分布在这 $3×3$ 的网格中。 例如： 1 2 3 X 4 6 7 5 8 在游戏过程中，可以把 X 与其上、下、左、右四个方向之一的数字交换（如果存在）。 我们的目的是通过交换，使得网格变为如 ......

起火迷宫 ↑ 题目链接 题目 一个迷宫可以看作一个 $R$ 行 $C$ 列的方格矩阵。 其中一些方格是空地，用 . 表示，其他方格是障碍，用 # 表示。 开始时，乔位于一块空地之中。 迷宫中一些空地已经起火了，幸运的是火还没有蔓延至乔所在的位置。 为了避免被火烧伤，乔需要尽快逃离迷宫。 已知，乔每单 ......

找路 ↑ 题目链接 题目 给定一个 $n$ 行 $m$ 列的方格矩阵。其中有些方格是空地（可以进入），有些方格是餐厅（可以进入），有些方格是障碍（不可进入）。开始时，小 $Y$ 和小 $M$ 各自位于一个空地方格中。每个人都可以沿上下左右四个方向进行移动，移动一格距离需要花费 $11$ 分钟时间。他 ......

石油储备 题目 一片土地可以看作是一个 $n$ 行 $m$ 列的方格矩阵。其中一些方格藏有石油，用 @ 表示，其余方格没有石油，用 * 表示。 每个方格都与其上、下、左、右、左上、右上、左下、右下八个方格视为相邻。 如果两个藏有石油的方格相邻，则它们被认为是处于同一片油田，否则它们被认为是处于不同油 ......

迷宫问题 ↑ 题目链接 题目 给定一个 $n×n$ 的二维数组，如下所示： int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫，其中的1表示墙 ......

非常可乐 题目 大家一定觉的运动以后喝可乐是一件很惬意的事情，但是 seeyou 却不这么认为。 因为每次当 seeyou 买了可乐以后，阿牛就要求和 seeyou 一起分享这一瓶可乐，而且一定要喝的和 seeyou 一样多。 但 seeyou 的手中只有两个杯子，它们的容量分别是 $N$ 毫升和 ......

点火游戏 ↑ 题目链接 题目 给定一个 $N$ 行 $M$ 列的方格矩阵。其中一部分方格是草地，其余部分是空地。草地能够被燃烧，空地不会。当某个草地在 $t$ 时刻被点燃时，其上下左右四个方向的相邻方格中的草地方格也会在 $t+1$ 时刻被点燃。 注意，空地方格无论如何都不可能被点燃。 现在，你可以 ......

罐子 ↑ 题目链接 题目 给你两个罐子，容积分别为 $A$ 升和 $B$ 升。 现在，你可以进行如下三种操作： FILL(i)，将罐子 $i（1≤i≤2）$ 灌满水。 DROP(i)，将罐子 $i（1≤i≤2）$ 清空。 POUR(i,j)，将罐子 $i$ 中的水倒向罐子 $j$ ，直到罐子 $i$ ......

洗牌 ↑ 题目链接 题目 给定两叠纸牌 $S1$ 和 $S2$，每叠恰好有 $C$ 张牌。 每张牌的尺寸大小都完全相同，但是颜色可能不同。 下面介绍洗牌规则。 不妨设 $S1$ 中纸牌从上到下编号依次为 $a_1,a_2,…,a_C$ ，$S_2$ 中纸牌从上到下编号依次为 $b_1,b_2,…,b ......

质数路径 ↑ 题目链接 题目 给定两个四位质数 $A$ 和 $B$ ，你需要通过最少的操作次数将 $A$ 变为 $B$ 。每次操作只能改变当前数的其中一位数字，并且每次操作过后，当前数必须仍然是一个质数。例如，将 $1033$ 变为 $8179$ ，最少需要进行 $6$ 次操作，具体操作为： 103 ......

找倍数 ↑ 题目链接 题目 给定一个正整数 $n$ ，请你找到一个它的非零倍数 $m$ 。要求 $m$ 中只包含数字 $0$ 或 $1$ ，并且总位数不超过 $100$ 位。 输入格式 输入包含多组测试数据。 每组数据占一行，包含一个正整数 $n$ 当输入 $n=0$ 时，表示输入结束。 输出格式 ......

抓住那头牛 ↑ 题目链接 题目 农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点 $N$ ，牛位于点 $K$。农夫有两种移动方式：从 $X$ 移动到 $X−1$ 或 $X+1$ ，每次移动花费一分钟从 $X$ 移动到 $2∗X$，每次移动花费一分钟假设牛没有意识到农夫的行动，站 ......

地牢大师 ↑ 题目链接 题目 你现在被困在一个三维地牢中，需要找到最快脱离的出路！ 地牢由若干个单位立方体组成，其中部分不含岩石障碍可以直接通过，部分包含岩石障碍无法通过。 向北，向南，向东，向西，向上或向下移动一个单元距离均需要一分钟。 你不能沿对角线移动，迷宫边界都是坚硬的岩石，你不能走出边界范 ......

前言： BFS 即广度优先搜索（或宽度优先搜索），具体定义和实现不在赘述。 本文所有代码前的开头头文件，宏定义和命名空间如下（只是一些常用的 define 和一个快读）： #include <bits/stdc++.h> #define Tp template<typename Ty> #defin ......

最短时间 有若干个城市，它们之间有道路连通，可以互相到达，从一个城市到另一个城市时间为1。现在给出起点城市A,终点城市B，和N条道路。问从A到B最短时间。 输入 第一行A，B，N（A,B,N<=30），B为最大城市标号 接下来N行，每行两个数x,y，表示城市x和城市y有道路相连。 输出 输出最短时间 ......

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。 大家好，欢迎来到小彭的 LeetCode 周赛解题报告。 昨晚是 LeetCode 双周赛第 102 场，你参加了吗？这场比赛比较简单，拼的是板子手速，继上周掉大分后算是回了一口血 😁。 2618. 查询网 ......

https://pintia.cn/problem-sets/994805046380707840/exam/problems/994805050709229568 输入样例： 7 5 4 1 2 2 3 3 1 4 5 5 6 1 4 5 7 输出样例： 2 6 4 0 #include<bits ......

https://pintia.cn/problem-sets/994805046380707840/exam/problems/994805052626026496 输入样例： 3 4 5 2 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 ......

重建序列 题目 给定一个长度为 n 的整数数组 nums ，其中 nums 是范围为 [1，n] 的整数的排列。还提供了一个 2D 整数数组 sequences ，其中 sequences[i] 是 nums 的子序列。 检查 nums 是否是唯一的最短 超序列 。最短 超序列 是 长度最短 的序列 ......

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

课程顺序 题目 现在总共有 numCourses 门课需要选，记为 0 到 numCourses-1。 给定一个数组 prerequisites ，它的每一个元素 prerequisites[i] 表示两门课程之间的先修顺序。 例如 prerequisites[i] = [ai, bi] 表示想要学 ......