首页 > 其他分享 >hdu1026 Ignatius and the Princess I --BFS & 记录路径 & 与DFS的比较

hdu1026 Ignatius and the Princess I --BFS & 记录路径 & 与DFS的比较

时间:2022-12-06 19:36:40浏览次数:65  
标签:node Ignatius cur -- DFS int time my mx


原题链接: ​​ http://acm.hdu.edu.cn/showproblem.php?pid=1026​


一:题意

一个n*m的矩阵代表一个迷宫,(0,0)是起点,(n-1)(m-1)是终点,每移动一步一秒。

迷宫每点意义是:

.   该点可以走

X 该点不可以走

n  在该点停留n秒(其中1<=n<=9)

若可以到达终点,求起点到终点的最小秒,并输出路径。


二:分析

一般来说,广搜常用于找单一的最短路线,或者是规模小的路径搜索,它的特点是"搜到就是最优解", 而深搜用于找多个解或者是"步数已知(比如3步就必须达到条件)"的问题,它的空间效率高,但是找到的不一定是最优解,必须记录并完成整个搜索,故一般情况下,深搜需要非常高效的剪枝(优化).

像搜索最短路径这些的很明显要是用广搜,因为广搜的特性就是一层一层往下搜的,保证当前搜到的都是最优解,当然,最短路径只是一方面的应用,像什么最少状态转换也是可以应用的。深搜就是优先搜索一棵子树,然后是另一棵,它和广搜相比,有着内存需要相对较少的优点,八皇后问题就是典型的应用,这类问题很明显是不能用广搜去解决的。或者像图论里面的找圈的算法,数的前序中序后序遍历等,都是深搜

深搜和广搜的不同之处是在于搜索顺序的不同。

深搜的实现类似于栈,每次选择栈顶元素去扩展,

广搜则是利用了队列,先被扩展的的节点优先拿去扩展。

搜索树的形态:深搜层数很多,广搜则是很宽。

深搜适合找出所有方案,广搜则用来找出最佳方案

深搜和广搜的区别:

深搜并不能保证第一次遇到目标点就是最短路径,因此要搜索所有可能的路径,因此要回溯,标记做了之后还要取消掉,因此同一个点可能被访问很多很多次。而广搜由于它的由近及远的结点扩展顺序,结点总是以最短路径被访问。一个结点如果第二次被访问,第二次的路径肯定不会比第一次的短,因此就没有必要再从这个结点向周围扩展――第一次访问这个结点的时候已经扩展过了,第二次再扩展只会得到更差的解。因此做过的标记不必去掉。因此同一个点至多只可能被访问一次。每访问一个结点,与它相连的边就被检查一次。因此最坏情况下,所有边都被检查一次,因此时间复杂度为O(E)。


三:AC代码

#define _CRT_SECURE_NO_DEPRECATE 
#define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1

#include<iostream>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>

using namespace std;

int n, m;
int dir[4][2] = { { 0,1 },{ 0,-1 },{ 1,0 },{ -1,0 } };
struct Node
{
int time;
int x, y;
int prex, prey;
char ch;

bool operator>(const Node & node) const
{
return time > node.time;
}

}node[105][105];

bool BFS()
{
int i;
int mx, my;
Node cur;
priority_queue<Node, vector<Node>, greater<Node> > pq;

node[0][0].time = 0;
pq.push(node[0][0]);

while (!pq.empty())
{
cur = pq.top();
pq.pop();
if (cur.x == n - 1 && cur.y == m - 1)
return true;
for (i = 0; i < 4; i++)
{
mx = cur.x + dir[i][0];
my = cur.y + dir[i][1];
if (mx >= 0 && mx < n&&my >= 0 && my < m)
{
if (node[mx][my].ch == '.'&&node[mx][my].time > cur.time + 1)
{
node[mx][my].time = cur.time + 1;
node[mx][my].prex = cur.x;
node[mx][my].prey = cur.y;
pq.push(node[mx][my]);
}
else if (node[mx][my].ch >= '1'&&node[mx][my].ch <= '9'&&node[mx][my].time > cur.time + node[mx][my].ch - '0'+1)//注意这里加1
{
node[mx][my].time = cur.time + node[mx][my].ch - '0' + 1;//注意这里加1
node[mx][my].prex = cur.x;
node[mx][my].prey = cur.y;
pq.push(node[mx][my]);
}
}
}
}

return false;
}

void printPath(int x, int y)
{
if (x == 0 && y == 0)
return;

int prex = node[x][y].prex;
int prey = node[x][y].prey;

printPath(prex, prey);

int prelength = node[prex][prey].time;
int length = node[x][y].time;
printf("%ds:(%d,%d)->(%d,%d)\n", prelength + 1, prex, prey, x, y);
for (int i = prelength + 2; i <= length; i++)
{
printf("%ds:FIGHT AT (%d,%d)\n", i, x, y);
}
}

int main()
{

int i, j;
while (~scanf("%d%d", &n, &m))
{
for (i = 0; i < n; i++)
{
getchar();
for (j = 0; j < m; j++)
{
scanf("%c", &node[i][j].ch);
node[i][j].time = INT_MAX;
node[i][j].x = i;
node[i][j].y = j;
}
}


bool state = BFS();
if (!state)
{
printf("God please help our poor hero.\n");
printf("FINISH\n");
continue;
}
printf("It takes %d seconds to reach the target position, let me show you the way.\n", node[n - 1][m - 1].time);
printPath(n - 1, m - 1);
printf("FINISH\n");
}


return 0;
}







标签:node,Ignatius,cur,--,DFS,int,time,my,mx
From: https://blog.51cto.com/u_11937443/5916551

相关文章

  • Angular 表单
    表单中的重要概念1:FormControl:表单控件,封装了表单中的输入,并提供了一些可供操纵的对象2:Validator:验证器,对表单的输入根据自己的需要添加一些限制3:Observer:观察者,......
  • 5.3.1 (2) 函数的单调性(含参函数)
    \({\color{Red}{欢迎到学科网下载资料学习}}\)[【基础过关系列】高二数学同步精品讲义与分层练习(人教A版2019)](https://www.zxxk.com/docpack/2875423.html)\({\col......
  • hdu1010 Tempter of the Bone --DFS & 奇偶剪枝
    原题链接:​​http://acm.hdu.edu.cn/showproblem.php?pid=1010​​一:题意一个n*m的迷宫,给定一个出发点,一个结束点,一条小狗需要在恰好第k秒走到结束点,如果可以输出YES,不然输......
  • k1s 工具使用教程
    .1.k1s是kubectl辅助工具soeasy,sofast.___/\/\/\(k|1|s)\_/\_/\_/by百里(github.com/yezihack/k1s)soeasy,s......
  • 判断是否是完全二叉树
     对于一棵二叉树,判断是否是一棵完全二叉树。typedefstructNode{intkey;Node*lChild;Node*rChild;}*PNode;boolis(PNode&p){boolflag=false;queue<PN......
  • 概率分布相关概念
    伯努利试验(Bernoulliexperiment)伯努利试验是在同样的条件下重复地、相互独立地进行的一种随机试验,其特点是该随机试验只有两种可能结果:发生或者不发生。我们假设该项试......
  • pop_heap 源码剖析
    一:用法示例一共两个重载:default(1)   template<classRandomAccessIterator> voidpop_heap(RandomAccessIteratorfirst, RandomAccessIteratorlast);cu......
  • 触发器
        ......
  • make_heap 源码剖析
    一:用法示例一共两个重载:default(1)   template<classRandomAccessIterator> voidmake_heap(RandomAccessIteratorfirst, RandomAccessIteratorlast);c......
  • Taro vs React Native 的八大差异
    TarovsReactNative的八大差异桂子Web开发,深圳​关注他 11人赞同了该文章API风格Taro与RN的一些组件及字段并不完全一致,以RN为主......