ZZZYM

题解

知识整理(2)

/ 注册

全部文章 / 题解（共8篇）

题解 | #胖胖的牛牛#

胖胖的牛牛(优先队列BFS) 思路优先队列BFS, 按照起点到每个点的转弯次数从小到大排序每次取出队头元素, 令st[x][y] = true;，代表每次出队的元素的转弯次数已经确定每次入队的点的转弯次数未必是最少的, 可能从别的路径走到该点的转弯次数更少, 所以入队的时候不要令st[a][...

广度优先搜索

2022-02-21

5 753

题解 | #神经网络#

神经网络思路算法：BFS 注意：题目描述错误，数据范围n开20是不够的，我开了1000才过；最后输出的不是非零状态，而是大于0的状态代码 #include <bits/stdc++.h> using namespace std; typedef long long LL; ty...

广度优先搜索

2022-02-21

2 546

题解 | #[NOIP2002]字串变换#

字串变换参考题解思路由于字符串变换的状态很多，空间复杂度和时间复杂度过大，所以采用双向广搜代码 #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, i...

广度优先搜索

2022-02-21

0 482

题解 | #迷宫#

迷宫类似的一道题的题解参考博客思路思路与上面那道类似的题目基本一致，唯一需要注意的是：对当前出队结点ttt，如果ttt的四个方向上有传送门，不仅要把ttt的四个方向中合法方向加入队列，还需要把所有传送门所在的点加入队列，而不是等到出队的点是传送门时再将所有传送门加入队列。具体地，可以参考...

广度优先搜索

2022-02-21

0 429

题解 | #maze#

maze 思路将每个点上的入口到对应出口也看成一条路径, 只不过从这条路径走距离一次+3 然后就是普通的bfs，注意队列要使用优先队列, 因为此时的队列不再具备步数的单调性，需要人为保证步数单调性。优先队列元素定义如下，注意优先队列的重载，可以参考《算法笔记》P223 struct Node ...

广度优先搜索

2022-02-20

0 386

题解 | #送外卖#

送外卖思路(反向建图+bfs) 注意本题所求的是最小字典序的字符串，而不是最小长度的字符串，所以需要反向建图，求出state[i]=truestate[i]=truestate[i]=true表示点iii可以到达点nnn(反向建图的bfs1函数中结点编号1-n，求最小字典序的bfs函数中结点编号...

广度优先搜索

2022-02-20

8 524

题解 | #寻找道路#

寻找道路思路建两个图, 一个图是原图，一个图是将原图的边全部反向后的图，在反向图中以终点ed为起点进行bfs遍历，标记所有遍历到的点state[i]=true 在原图上进行bfsbfsbfs遍历，在原本bfs将点加入队列的条件的基础上，增加一个条件：如果一个点jjj的所有邻接点的statest...

广度优先搜索

2022-02-20

0 484

题解 | #模拟战役#

模拟战役思路 Flood Fill 代码 #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef pair<doub...

广度优先搜索

2022-02-20

0 376