链接：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：

9

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;
}