返回
热门推荐
HDU-ACM程序设计——BFS（宽度优先搜索）
2024-10-31 20:38

        我先讲讲自己对BFS的看法吧。对一个二叉树来说，宽度优先的意思就是遍历树的时候先一边到另一边（左右）再从上到下。

HDU-ACM程序设计——BFS（宽度优先搜索）

 比如这棵二叉树宽度优先遍历得到5 1 7 2 4 6 3很明显，这里出现了三个分层，也就是说下层的节点一定比上层的节点晚出现。那么我们可以借助这种特殊的性质加上队列的先进先出达到搜索的目的，找出层数最小的，符合要求的节点。我们先讲队列。

目录

 队列

        队列的使用

基础队列

HDU_web_DIY_8_3:Knight Moves

HDU_web_DIY_8_1：A strange lift

优先队列——HDU_web-DIY_8_4:Rescue

习题

1.非常可乐

2.胜利大逃亡

可视化BFS

        队列的使用

头文件：<queue>

搭配namespace使用:using namespace std;

定义一个队列:queue<元素的类型>数组名

入队（尾部）:qu.push();

出队（头部）:qu.pop();————没有返回值

判断是否为空:qu.empty();————是空返回真

访问队列头:qu.front()————返回元素类型相同的元素

访问队列尾qu.back()

获取队列大小:qu.size()

看上去队列就像一个通道，进去了就不能掉头，只能按照进的顺序出。那队列对BFS有什么用呢？我们来看一个例题。

A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part.
Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.

你的一个朋友正在研究旅行骑士问题（TKP），在这个问题上，你要找到骑士移动的最短封闭旅程，该旅程恰好访问棋盘上给定的n个方格中的每个方格一次。他认为问题中最困难的部分是确定两个给定方格之间骑士移动的最小数量，一旦你完成了这一点，找到旅程就很容易了。你当然知道反之亦然。所以你让他写一个程序来解决“困难”的部分。

你的工作是写一个程序，以两个方块a和b作为输入，然后确定从a到b的最短路线上的骑士移动次数。(我希望大家都知道骑士是走日字的)

The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.

输入文件将包含一个或多个测试用例。每个测试用例由一行组成，一行包含由一个空格分隔的两个正方形。正方形是由棋盘上代表列的字母（a-h）和代表行的数字（1-8）组成的字符串

For each test case, print one line saying "To get from xx to yy takes n knight moves.".

对于每个测试用例，打印一行“从xx到yy需要n次骑士移动”。

e2 e4 a1 b2 b2 c3 a1 h8 a1 h7 h8 a1 b1 c3 f6 f6

To get from e2 to e4 takes 2 knight moves.

To get from a1 to b2 takes 4 knight moves.

To get from b2 to c3 takes 2 knight moves.

To get from a1 to h8 takes 6 knight moves.

To get from a1 to h7 takes 5 knight moves.

To get from h8 to a1 takes 6 knight moves.

To get from b1 to c3 takes 1 knight moves.

To get from f6 to f6 takes 0 knight moves.

对于骑士的每一个位置，它都最多有八种不同的走法，少于八种的原因有：走到边界了和这个点来过了。所以在进队列的时候需要判断这两种特殊情况，如果不是这两种情况就进队列。

 对于这个蓝色的点，我们枚举它所有的跳法，然后判断是否符合进队列的标准，如果符合就进。那么队列里就是这些红色的位置，他们都是由蓝色的点跳动得到的，所以他们的时间是一样的，在队列中连续排布，对于这个题目，层数就是骑士的步数。

我们可以创建这样的结构体，保存点的位置和所需要的步数。

这可以说是一个超级明显的搜索问题了，非常适合像我这样的新手，看懂这个题，对BFS也算是有一个初步的认识了，接下来看一个稍微抽象一点的BFS。

Total Submission(s) : 99   Accepted Submission(s) : 36

There is a strange lift.The lift can stop can at every floor as you want, and there is a number Ki(0 <= Ki <= N) on every floor.The lift have just two buttons: up and down.When you at floor i,if you press the button "UP" , you will go up Ki floor,i.e,you will go to the i+Ki th floor,as the same, if you press the button "DOWN" , you will go down Ki floor,i.e,you will go to the i-Ki th floor. Of course, the lift can't go up high than N,and can't go down lower than 1. For example, there is a buliding with 5 floors, and k1 = 3, k2 = 3,k3 = 1,k4 = 2, k5 = 5.Begining from the 1 st floor,you can press the button "UP", and you'll go up to the 4 th floor,and if you press the button "DOWN", the lift can't do it, because it can't go down to the -2 th floor,as you know ,the -2 th floor isn't exist.
Here comes the problem: when you are on floor A,and you want to go to floor B,how many times at least he has to press the button "UP" or "DOWN"?

有一个奇怪的电梯。电梯可以随心所欲地停在每一层，每一层都有一个数字Ki（0<=Ki<=N）地板。那个电梯只有两个按钮：向上和向下。当你在第一层时，如果你按下“向上”按钮，你将进入第一层，也就是说，你将进入第一层，同样，如果你按下“向下”按钮，你将进入第一层，也就是说，你将进入第一层。当然，电梯不能上升到高于N的高度，也不能下降到低于1的高度。例如，有一栋楼有5层，k1=3，k2=3，k3=1，k4=2，k5=5。从1楼开始，你可以按“向上”按钮，然后你会上到4楼，如果你按“向下”按钮，电梯就做不到，因为它不能下到-2楼，你知道，-2楼是不存在的。问题来了：当你在a楼，你想去B楼，他至少要按多少次“上”或“下”按钮？

The input consists of several test cases.,Each test case contains two lines. The first line contains three integers N ,A,B( 1 <= N,A,B <= 200) which describe above,The second line consist N integers k1,k2,....kn. A single 0 indicate the end of the input.

输入由几个测试用例组成。，每个测试用例包含两行。第一行包含如上所述的三个整数N，A，B（1<=N，A，B<=200），第二行由N个整数k1，k2，....kn。单个0表示输入结束。

For each case of the input output a interger, the least times you have to press the button when you on floor A,and you want to go to floor B.If you can't reach floor B,printf "-1".

对于输入输出a interger的每种情况，当你在a层，并且你想去B层时，你必须按下按钮的最少次数。如果你不能到达B层，打印f”-1”。

5 1 5 3 3 1 2 5 0

3

  首先我们得分析好状态该该怎么表示。这里比较明显。对于每一层电梯对应着楼层数和操作数，操作数也就是层数，创建一个结构体来保存状态。既然是用BFS解题，那肯定有树的，头节点就是出发的位置，对应这题对于每一楼层有不同的转移方法，转移之后的楼层就是头节点的子节点，对于每一个满足要求的子节点，我们把它压入队列中。对于经过的楼层我们要做标记，我一般使用一个数组来做标记（可以是 int 也可以是 bool）我个人喜欢用 int 类型，毕竟C里面也是没有boll类型的 。

可以看到BFS几乎就是一个模板，只需要找到对应的状态转移方式，对应的标记方式，对应的一些减枝操作，BFS也没什么难的。嘿嘿。

刷完这两题，你差不多可以手搓BFS了。你会发现写BFS会有一种很强的趋向意识————我就该这么写，这是你差不多已经掌握BFS的用法了。接下来介绍一个新朋友——优先队列

假如状态转移的时候，发现同一层的节点的权值不一样？！ 

比如下面这个题目

Total Submission(s) : 57   Accepted Submission(s) : 19

Problem Description

Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison.

Angel's friends want to save Angel. Their task is: approach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.

You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)

安吉尔被莫利皮抓住了！他被莫利皮关进了监狱。监狱被描述为一个N*M（N，M<=200）矩阵。监狱里有围墙、道路和守卫。安吉尔的朋友们想救安吉尔。他们的任务是：接近天使。我们假设“接近天使”是为了到达天使停留的位置。当格子里有守卫时，我们必须杀了他（或她？）进入网格。我们假设我们向上、向下、向右、向左移动需要1个单位时间，杀死一个守卫也需要1个单位时间。我们有足够的力量杀死所有的守卫。你必须计算接近天使的最短时间。（当然，我们只能上、下、左、右移动到边界内的邻居网格。）

First line contains two integers stand for N and M. Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend. Process to the end of the file.

第一行包含两个整数，代表N和M，然后是N行，每行有M个字符。“.”代表路，“A”代表天使，“r”代表天使的每一个朋友。处理到文件末尾。

For each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life."

对于每个测试用例，您的程序应该输出一个整数，代表所需的最小时间。如果这样的数字不存在，您应该输出一行包含“可怜的天使必须在监狱里呆一辈子”。

7 8

#.####

#. #.a#..r.

#..#x...

..#..#.#

#...##..

.#......

........

13

 这里如果我们碰到了警卫，那么杀死警卫需要2s但是走空地只需要1s，也就是说，虽然是同一层的，但是这些节点的权值不一样，这时我们就可以用到优先队列。因为我没学过C++所以我只能给出优先队列的基础用法，想要详细用法的可以上百度。

头文件:<queue>

priority_queue<数据类型>优先队列名

empty( )  ——判断一个队列是否为空

pop( )  ——删除队顶元素

push( )  ——加入一个元素

top( )  ——返回优先队列的队顶元素

size( )  ——返回优先队列中拥有的元素个数

实际上优先队列的参数是有三个的priority_queue<Type, Container, Functional>,这里我不展开说了，推荐一篇文章 ，里面优先队列讲得很好。

优先队列(priority_queue)的原理及用法_子木呀的博客-CSDN博客_prority_queue

这里我只说明如何在BFS中使用优先队列。对于优先队列的创建和队列相差无几。

首先是节点的结构体声明

 然后创建以此结构体为元素类型的优先队列。

 我把比较函数写到了外面，避免写优先队列的容器。

 这个排列是从大到小，所以top的steps是最小的。也就是每次出队列的节点是权值最小的节点。这样就达到了我们的目的。

这段代码里的BFS我用了非常暴力的枚举，甚至没有用数组来记录移动方向，（主要是懒），各位也可以试试用数组移动的方式，通过遍历数组来实现搜索。虽然用到了优先队列，但是还是换汤不换药，BFS依旧如此。

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 41   Accepted Submission(s) : 22

大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升　(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。

三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。

如果能平分的话请输出最少要倒的次数，否则输出"NO"。

7 4 3 4 1 3 0 0 0

NO 3

 AC代码

Time Limit : 4000/2000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 88   Accepted Submission(s) : 27

Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会.

魔王住在一个城堡里,城堡是一个A*B*C的立方体,可以被表示成A个B*C的矩阵,刚开始Ignatius被关在(0,0,0)的位置,离开城堡的门在(A-1,B-1,C-1)的位置,现在知道魔王将在T分钟后回到城堡,Ignatius每分钟能从一个坐标走到相邻的六个坐标中的其中一个.现在给你城堡的地图,请你计算出Ignatius能否在魔王回来前离开城堡(只要走到出口就算离开城堡,如果走到出口的时候魔王刚好回来也算逃亡成功),如果可以请输出需要多少分钟才能离开,如果不能则输出-1.
 

输入数据的第一行是一个正整数K,表明测试数据的数量.每组测试数据的第一行是四个正整数A,B,C和T(1<=A,B,C<=50,1<=T<=1000),它们分别代表城堡的大小和魔王回来的时间.然后是A块输入数据(先是第0块,然后是第1块,第2块......),每块输入数据有B行,每行有C个正整数,代表迷宫的布局,其中0代表路,1代表墙.(如果对输入描述不清楚,可以参考Sample Input中的迷宫描述,它表示的就是上图中的迷宫) 特别注意:本题的测试数据非常大,请使用scanf输入,我不能保证使用cin能不超时.在本OJ上请使用Visual C++提交.

对于每组测试数据,如果Ignatius能够在魔王回来前离开城堡,那么请输出他最少需要多少分钟,否则输出-1.

1 3 3 4 20

0 1 1 1 0 0

1 1 0 1 1 1

1 1 1 1 1 0

0 1 0 1 1 1

0 0 0 0 0 1

1 0 0 1 1 0

11

AC代码

        这里不多说了，就浅浅的给大家展示一下可视化吧，如果觉得有意思的话，我考虑一下，有时间就出一期讲讲可视化的实现。

    以上就是本篇文章【HDU-ACM程序设计——BFS（宽度优先搜索）】的全部内容了，欢迎阅览 ！ 文章地址：http://dfvalve.xrbh.cn/quote/2000.html 
     行业      资讯      企业新闻      行情      企业黄页      同类资讯      网站地图      返回首页 迅博思语资讯移动站 http://keant.xrbh.cn/ , 查看更多