PUBG（bfs+优先队列）

朴灿烈づ我的快乐病毒、 2022-05-25 02:14 161阅读 0赞

链接：https://www.nowcoder.com/acm/contest/118/A

来源：牛客网

Problem Description：

最近，喜爱ACM的PBY同学沉迷吃鸡，无法自拔，于是又来到了熟悉的ERANGEL。经过一番搜寻，PBY同学准备动身前往安全区，但是，地图中埋伏了许多LYB，PBY的枪法很差，希望你能够帮他找到一条路线，每次只能向上、下、左、右移动，尽可能遇到较少的敌人。

Input：

题目包含多组测试，请处理到文件结束；  
第一行是一个整数n，代表地图的大小；  
接下来的n行中，每行包含n个整数a，每个数字a代表当前位置敌人的数量；

1 < n <= 100，1 <= a <= 100，-1代表当前位置，-2代表安全区。

Output：

对于每组测试数据，请输出从当前位置到安全区所遇到最少的敌人数量，每个输出占一行。

Sample Input：

5  
6 6 0 -2 3  
4 2 1 2 1  
2 2 8 9 7  
8 1 2 1 -1  
9 7 2 1 2  
5  
62 33 18 -2 85  
85 73 69 59 83  
44 38 84 96 55  
\-1 11 90 34 50

19 73 45 53 95

Sample Output：

173

思路：这道题用了广搜bfs的知识点，还有一个知识点是优先队列，要注意的是访问优先队列的队首元素要用 q.top（），而且队列中元素排序默认的是从大到小的顺序，因此要利用重载“<”操作符来重新定义排序规则。

My DaiMa：

#include<stdio.h>
    #include<iostream>
    #include<queue>
    #include<string.h>
    using namespace std;
    int n,flag[105][105];
    struct position
    {
        int x,y,step;
        bool operator < (const position &p) const{
            return step>p.step;
        }
    }start,eend;
    int dir[4][2]={
       {1,0},{-1,0},{0,-1},{0,1}};
    int bfs()
    {
        priority_queue<position>Q;
        position cur,nxt;
        start.step=0;
        Q.push(start);
        while(!Q.empty())
        {
            cur=Q.top();
            Q.pop();
            if(cur.x==eend.x&&cur.y==eend.y) return cur.step+2;//加2是因为end的地方的敌人是-2
            for(int i=0;i<4;i++)
            {
                nxt.x=cur.x+dir[i][0];
                nxt.y=cur.y+dir[i][1];
                if(nxt.x<0||nxt.x>=n||nxt.y<0||nxt.y>=n||flag[nxt.x][nxt.y]==-1) continue;
                nxt.step=cur.step+flag[nxt.x][nxt.y];
                flag[nxt.x][nxt.y]=-1;//走过的地方要进行标记
                Q.push(nxt);
            }
        }
        return -1;
    }
    int main()
    {
        while(~scanf("%d",&n))
        {
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    scanf("%d",&flag[i][j]);
                    if(flag[i][j]==-1)
                    {
                        start.x=i;
                        start.y=j;
                    }
                    if(flag[i][j]==-2)
                    {
                        eend.x=i;
                        eend.y=j;
                    }
                }
            }
            printf("%d\n",bfs());
        }
        return 0;
    }