链接：https://www.nowcoder.com/acm/contest/118/A
来源：牛客网
题目描述
最近，喜爱ACM的PBY同学沉迷吃鸡，无法自拔，于是又来到了熟悉的ERANGEL。经过一番搜寻，PBY同学准备动身前往安全区，但是，地图中埋伏了许多LYB，PBY的枪法很差，希望你能够帮他找到一条路线，每次只能向上、下、左、右移动，尽可能遇到较少的敌人。
输入描述:
题目包含多组测试，请处理到文件结束；
第一行是一个整数n，代表地图的大小；
接下来的n行中，每行包含n个整数a，每个数字a代表当前位置敌人的数量；
1 < n <= 100，1 <= a <= 100，-1代表当前位置，-2代表安全区。输出描述:
对于每组测试数据，请输出从当前位置到安全区所遇到最少的敌人数量，每个输出占一行。示例1
输入
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输出
9示例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输出
173#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int Map[105][105];
bool vis[105][105];
struct Node{int x,y,step;bool operator < (const Node&t) const{return step > t.step;}
}S,E;int n;
int dir[4][2] = {1,0,-1,0,0,1,0,-1};
void bfs()
{memset(vis, false,sizeof(vis));Node now;now.x = S.x, now.y = S.y;now.step = 0;priority_queue<Node> q;vis[S.x][S.y] = true;q.push(now);while(!q.empty()){Node Now = q.top();q.pop();if(Now.x == E.x && Now.y == E.y){cout << Now.step + 2<<endl;return;}for (int i = 0; i < 4; i++){Node next;next.x = Now.x + dir[i][0];next.y = Now.y + dir[i][1];if( next.x >= 1 && next.x <= n && next.y >= 1 && next.y <= n && vis[next.x][next.y] == false){next.step = Now.step + Map[next.x][next.y];vis[next.x][next.y] =true;q.push(next);}}}}
int main()
{while(scanf("%d", &n) != EOF){for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){cin >> Map[i][j];if(Map[i][j] == -1){S.x = i;S.y = j;}if(Map[i][j] == -2){E.x = i;E.y = j;}}}bfs();}
}
/*
链接：https://www.nowcoder.com/acm/contest/118/A
来源：牛客网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
*/