首页 > 胖胖的牛牛
头像 ZZZYM
发表于 2022-02-21 21:20:28
胖胖的牛牛(优先队列BFS) 思路 优先队列BFS, 按照起点到每个点的转弯次数从小到大排序 每次取出队头元素, 令st[x][y] = true;,代表每次出队的元素的转弯次数已经确定 每次入队的点的转弯次数未必是最少的, 可能从别的路径走到该点的转弯次数更少, 所以入队的时候不要令st[a][ 展开全文
头像 CallmeChallenger
发表于 2020-06-30 11:29:14
题意:求在地图中从A到B的最小转弯次数题解:很明显的一个搜索题,这里我的做法采用dfs,dfs里面保存状态x,y,t,fa,分别代表当前位置的x,y,已经转弯次数,上次行走的方式。然后从A dfs到B,详细步骤可查看代码注释 #include <bits/stdc++.h> using 展开全文
头像 cheeserish
发表于 2020-07-11 23:23:55
#include<bits/stdc++.h> using namespace std; const int maxn=400; int head[maxn],mp[200][200],cnt,tx,ty,n,dis[maxn][maxn],vis[maxn][maxn]; int d[ 展开全文
头像 在刷题的单身狗很开心
发表于 2023-11-06 20:32:48
因为正在练习图论,所以建图来做吧。 可以假设某个各种的上下左右方向都有一个点,那么这些点的道路里面方向改变的,也就是某个格子上下左右相邻直接的道路的长度是1,其余是0。 那么就可以转化成起点的四个方向点到终点的四个方向点的求解。 那么直接套Dijkstra算法即可。就是建图有那么亿 展开全文
头像 |Crisp|
发表于 2020-06-30 17:22:52
题意: 给你一个迷宫,求出从A到B最少需要多少次90度转弯。 思路: 这题和普通迷宫的区别在于:普通迷宫求的是最少走的步数,而这题要我们求的是最少的转弯数,这就导致了dfs的方式对于这题是优于bfs的,因为dfs的状态记录更加方便,而bfs还得专门开数组来记录方向和判重。 既然确定了解法,就可以开 展开全文
头像 微澜尛雨
发表于 2021-11-19 12:14:35
题目考点:bfs or dfs or dijkstra(蒟蒻优先想到bfs,就先粘上bfs吧,日后有时间补上其他的) 题目大意:走迷宫起点到终点至少需要转90度弯共几次 题目分析:优先队列按照转弯次数从小到大,基于贪心思想得到最优解。在bfs版子的基础上,在结点中多加一个该点是从哪个方向走来的即可。 展开全文