HDU 1728 逃离迷宫

By NodeKey in ACM on

真特么蛋疼 一开始我也是把这道题当成常规的 BFS 求最短路径 来写 WA了3发 百思不得其姐 bug怎么找都找不出来 无奈看了一下题解才恍然大悟 这么说吧 题目要求的是 从一个点到另一个点的最小拐弯数 假如说是常规的BFS 从一点到另一点 只能保证路径最短 拐弯数的多少和路径长短是毫无联系的 所以我们每次查找四个方向的时候 直接把一整条直线的grid全都压进队列 因为他们的拐弯数相同 优先级相同 AC Code 感觉时间略长 有待优化 只能助于理解用 #include #include #include #include #include #include using namespace std; int row,col,limit; int st_x,st_y,en_x,en_y; char mat[110]…

HDU 1180 诡异的楼梯

By NodeKey in ACM on

集训第二天练习宽搜 写的最郁闷的一题 一个晚上的时间都花在这里了 题目是最普通的宽搜加一个 会变换的楼梯 竖着只能上下走 横着只能左右走 允许停留 跨越楼梯不需要时间 对我来说 题目最大的坑点在于 停留的时候 其他结点都在扩散 如果这时候 直接把结点加入队列 会打散扩散顺序 最后我用了优先队列 还是太辣鸡了啊 唉 AC Code #include #include #include #include #include #include #include using namespace std; struct node { int x,y; int step; node(int a,int b,int c):x(a),y(b),step(…