广度优先搜索（图 BFS）练手题

水深无声 2024-02-17 18:53 38阅读 0赞

1.  ### 追赶妖怪 ###
    
    ### Description ###
    
    一身正气的钟馗四处降妖，一天他发现一只狐妖正在祸害百姓，他连忙追赶上去准备除妖，可是狐妖很聪明，她自知敌不过钟馗，便逃入山林，企图消耗钟馗的体力。钟馗在树林里面可以自由移动，而且他有一个法术：可以从当前坐标(x,y)直接移动到(2x,2y)的位置。钟馗为了不枉送性命，找到人称"人间诸葛亮"的你，希望你能帮他判断他能否在体力未耗尽到达狐妖的藏匿地点（如果到达狐妖藏身之处还剩余0点体力也是可以的）。
    
    注意：钟馗一开始拥有n点体力，每次普通移动或者使用法术移动会消耗1点体力值，当体力消耗完毕(n<=0)便无法再进行移动。
    
    现在给钟馗移动方式一个规定：
    
    a.如果钟馗不使用法术，他可以从(x,y)移动到(x-1,y),(x+1,y),(x,y-1),(x,y+1)中的任意一个位置.
    
    b.如果钟馗使用法术，他可以从当前坐标(x,y)直接移动到(2x,2y)的位置.
    
    ### Input ###
    
    输入包含3行。
    
    第一行包含一个数字n，表示钟馗的初始体力值。1<n<=500
    
    第二行两个整数表示钟馗初始坐标。
    
    第三行两个整数表示狐妖藏匿坐标。
    
    注意：狐妖不会移动。树林可以看做一个矩形，四个角的坐标分别为(0,0),(0,500),(500,0),(500,500)。钟馗移动的位置不能超出树林的范围。
    
    ### Output ###
    
    输出只有一行。
    
    如果钟馗能够到达狐妖藏匿位置输出"YES",如果钟馗无法到达狐妖藏匿位置输出"NO"
    
    ### Sample Input ###
    
        50
        4 4
        9 9
        5
        0 0
        0 5
        1
        0 0
        1 0
        1
        0 0
        2 2
        1
        0 0
        500 500
    
    ### Sample Output ###
    
        YES
        YES
        YES
        NO
        NO
    
        程序如下：
2.  \#include<cstdio>
3.  \#include<queue>
4.  \#include<vector>
5.  \#include<cstring>
6.  using namespace std;
7.  const int maxn=500+10;
8.  struct note\{ 
9.   int x,y;
10.  note(int x1=0,int y1=0):x(x1),y(y1)\{\}
11.  \};
12.  note n2;
13.  int X,Y,N;
14. int d\[maxn\]\[maxn\]; //记录初始位置到当前位置走过的步数
15. int dir\[\]\[2\]=\{ \{1,0\},\{-1,0\},\{0,-1\},\{0,1\},\{X,Y\}\};
16. void print(note u)\{ 
17.  if(d\[u.x\]\[u.y\]>N)printf("NO\\n");
18.  else printf("YES\\n");
19. \}
20.   
    
21. bool isValid(const note &v)\{ 
22.  return v.x>=0 && v.x<=500 && v.y>=0 &&v.y<=500;
23. \}
24. void bfs()\{ 
25.  queue<note>q;
26.  q.push(note(X,Y));
27.  while(!q.empty())\{ 
28.  note u=q.front();q.pop();
29.  if(u.x==n2.x && u.y==n2.y)\{ 
30.  print(u);
31.  return ; 
32.  \}
33.  X=u.x;Y=u.y;
34.  for(int i=0;i<5;i++)\{ 
35.  note v;
36.  if(i<4)v=note(u.x+dir\[i\]\[0\],u.y+dir\[i\]\[1\]);
37.  else v=note(X\*2,Y\*2);
38.  if(isValid(v) && d\[v.x\]\[v.y\]==0)\{ 
39.  d\[v.x\]\[v.y\]=d\[u.x\]\[u.y\]+1;
40.  q.push(v);
41.  \}
42.  \}
43.  \}
44. \}
45. int main()\{ 
46.  while(scanf("%d",&N)==1)\{ 
47.  scanf("%d%d",&X,&Y);
48.  scanf("%d%d",&n2.x,&n2.y);
49.  memset(d,0,sizeof(d));
50.  bfs();
51.  \}
52.  return 0;
53. \}

本题不需要记录路径，是一道相对简单的BFS类型题目。如果对广度优先搜索（BFS)不是很熟悉的话可以访问 [http://rapheal.iteye.com/blog/1526861][http_rapheal.iteye.com_blog_1526861] 这个网址，感觉写的不错。

[http_rapheal.iteye.com_blog_1526861]: http://rapheal.iteye.com/blog/1526861