搜索算法之坦克大战（bfs+优先队列）

电玩女神 2022-06-01 04:53 216阅读 0赞

# 优先队列：（来自一位大佬的） #

首先，你需要

#include<queue>
    using namespace std;

这两个头文件。

其次，一个优先队列声明的基本格式是：   
**priority\_queue<结构类型> 队列名;**   
比如：

priority_queue <int> i;
    priority_queue <double> d;

`不过，我们最为常用的是这几种：`

priority_queue <node> q;
    //node是一个结构体
    //结构体里重载了‘<’小于符号
    priority_queue <int,vector<int>,greater<int> > q;
    //不需要#include<vector>头文件
    //注意后面两个“>”不要写在一起，“>>”是右移运算符
    priority_queue <int,vector<int>,less<int> >q;

我们将在下文来讲讲这几种声明方式的不同。

## 优先队列的基本操作 ##

与队列的基本操作如出一辙。

以一个名为q的优先队列为例。

q.size();//返回q里元素个数
    q.empty();//返回q是否为空，空则返回1，否则返回0
    q.push(k);//在q的末尾插入k
    q.pop();//删掉q的第一个元素
    q.top();//返回q的第一个元素
    q.back();//返回q的末尾元素

## 优先队列的特性 ##

上文已经说过了，**自动排序**。   
怎么个排法呢？   
在这里介绍一下：

### 默认的优先队列（非结构体结构） ###

priority_queue <int> q;

这样的优先队列是怎样的？让我们写程序验证一下。

#include<cstdio>
    #include<queue>
    using namespace std;
    priority_queue <int> q;
    int main()
    {
        q.push(10),q.push(8),q.push(12),q.push(14),q.push(6);
        while(!q.empty())
            printf("%d ",q.top()),q.pop();
    }

程序大意就是在这个优先队列里依次插入10、8、12、14、6，再输出。   
结果是什么呢？   
`14 12 10 8 6`   
也就是说，它是按从大到小排序的！

### 默认的优先队列（结构体，重载小于） ###

先看看这个结构体是什么。

struct node
    {
        int x,y;
        bool operator < (const node & a) const
        {
            return x<a.x;
        }
    };

这个node结构体有两个成员，x和y，它的小于规则是x小者小。   
再来看看验证程序：

#include<cstdio>
    #include<queue>
    using namespace std;
    struct node
    {
        int x,y;
        bool operator < (const node & a) const
        {
            return x<a.x;
        }
    }k;
    priority_queue <node> q;
    int main()
    {
        k.x=10,k.y=100; q.push(k);
        k.x=12,k.y=60; q.push(k);
        k.x=14,k.y=40; q.push(k);
        k.x=6,k.y=80; q.push(k);
        k.x=8,k.y=20; q.push(k);
        while(!q.empty())
        {
            node m=q.top(); q.pop();
            printf("(%d,%d) ",m.x,m.y);
        }
    }

程序大意就是插入(10,100),(12,60),(14,40),(6,20),(8,20)这五个node。   
再来看看它的输出：   
`(14,40) (12,60) (10,100) (8,20) (6,80)`

它也是按照**重载后的小于规则**，从大到小排序的。

### less和greater优先队列 ###

还是以int为例，先来声明：

priority_queue <int,vector<int>,less<int> > p;
    priority_queue <int,vector<int>,greater<int> > q;

话不多说，上程序和结果：

#include<cstdio>
    #include<queue>
    using namespace std;
    priority_queue <int,vector<int>,less<int> > p;
    priority_queue <int,vector<int>,greater<int> > q;
    int a[5]={10,12,14,6,8};
    int main()
    {
        for(int i=0;i<5;i++)
            p.push(a[i]),q.push(a[i]);
    
        printf("less<int>:")
        while(!p.empty())
            printf("%d ",p.top()),p.pop();  
    
        pritntf("\ngreater<int>:")
        while(!q.empty())
            printf("%d ",q.top()),q.pop();
    }

结果：   
  
`less<int>:14 12 10 8 6  greater<int>:6 8 10 12 14`

所以，我们可以知道，**less是从大到小，greater是从小到大**。

### 作个总结 ###

为了装13方便，在平时，建议大家写：

priority_queue<int,vector<int>,less<int> >q;
    priority_queue<int,vector<int>,greater<int> >q;

平时如果用从大到小不用后面的`vector<int>,less<int>`，可能到时候要改成从小到大，你反而会搞忘怎么写`greater<int>`，反而得不偿失。

## 总结 ##

优先队列到此就作了个小结。   
其实不管是队列，还是优先队列，都不仅仅只有我讲的这些，还有更多可以探索。

## 坦克大战 ##

时间限制：1000 ms  |  内存限制：65535 KB

难度：3

描述

Many of us had played the game "Battle city" in our childhood, and some people (like me) even often play it on computer now.   
What we are discussing is a simple edition of this game. Given a map that consists of empty spaces, rivers, steel walls and brick walls only. Your task is to get a bonus as soon as possible suppose that no enemies will disturb you (See the following picture).

![20110504202029_28920.jpg][]

Your tank can't move through rivers or walls, but it can destroy brick walls by shooting. A brick wall will be turned into empty spaces when you hit it, however, if your shot hit a steel wall, there will be no damage to the wall. In each of your turns, you can choose to move to a neighboring (4 directions, not 8) empty space, or shoot in one of the four directions without a move. The shot will go ahead in that direction, until it go out of the map or hit a wall. If the shot hits a brick wall, the wall will disappear (i.e., in this turn). Well, given the description of a map, the positions of your tank and the target, how many turns will you take at least to arrive there?

输入

The input consists of several test cases. The first line of each test case contains two integers M and N (2 <= M, N <= 300). Each of the following M lines contains N uppercase letters, each of which is one of 'Y' (you), 'T' (target), 'S' (steel wall), 'B' (brick wall), 'R' (river) and 'E' (empty space). Both 'Y' and 'T' appear only once. A test case of M = N = 0 indicates the end of input, and should not be processed.

输出

For each test case, please output the turns you take at least in a separate line. If you can't arrive at the target, output "-1" instead.

样例输入

3 4
    YBEB
    EERE
    SSTE
    0 0

样例输出

来源

[POJ][]

上传者

[sadsad][]

代码实现：

#include <queue>
    #include <stdio.h>
    #include <string.h>
    #include<stdlib.h>
    #include <algorithm>
    using namespace std;
    int st_x,st_y,end_x,end_y;//起点、终点
    char map[311][311];//原地图
    char vis_map[311][311];//扫描地图
    int move_x[4]={0,0,1,-1};
    int move_y[4]={1,-1,0,0};//移动
    int H,W;
    int check(int x,int y)//检查该点是否能够移动
    {
        if (x<0||y<0||x>=H||y>=W||vis_map[x][y]||map[x][y]=='S'||map[x][y]=='R')//S为铁墙R为河流均不能过
            return 1;//不能移动到此
        else
            return 0;
    }
    struct tank
    {
        int x,y,stp;
        bool friend operator<(tank num1,tank num2)
        {
            return num1.stp>num2.stp;
        }
    } a,next;
    int bfs()//搜索
    {
        priority_queue<tank> move;//创建tank结构体优先队列
        a.x=st_x;
        a.y=st_y;
        a.stp=0;
        move.push(a);//添加一个元素
        vis_map[st_x][st_y]=1;
        while (!move.empty())
        {
            a=move.top();//返回队列中优先级最高的一个元素
            move.pop();// 删除队列的第一个元素
            if (a.x==end_x && a.y==end_y)
                return a.stp;
            for (int i=0; i<4; i++)
            {
                next.x=a.x+move_x[i];
                next.y=a.y+move_y[i];
                next.stp=a.stp;
                if (check(next.x,next.y))		//移动是否合法
                    continue;
                if (map[next.x][next.y]=='B')		//是否为软墙，是则多花一步
                    next.stp+=2;
                else
                    next.stp++;
                vis_map[next.x][next.y]=1;
                move.push(next);
            }
        }
        return -1;
    }
    int main()
    {
        while(scanf("%d %d",&H,&W)!=EOF)
        {
            if(H==0&&W==0)
                break;
            memset(vis_map,0,sizeof(vis_map));
            for(int i=0; i<H; i++)		//输入并寻找起点终点
            {
                scanf("%s",map[i]);
                for(int j=0; j<W; j++)
                {
                    if(map[i][j]=='Y')//起点
                    {
                        st_x=i;
                        st_y=j;
                    }
                    else if(map[i][j]=='T')//终点
                    {
                        end_x=i;
                        end_y=j;
                    }
                }
            }
            int ans;
            ans=bfs();
            printf ("%d\n",ans);
        }
    }

[20110504202029_28920.jpg]: http://acm.nyist.edu.cn/JudgeOnline/admin/kind/attached/20110504202029_28920.jpg
[POJ]: http://acm.nyist.edu.cn/JudgeOnline/search_result.php?source=POJ
[sadsad]: http://acm.nyist.edu.cn/JudgeOnline/profile.php?userid=sadsad