题目描述
最近，喜爱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
输入
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 <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <stack> #include <cstdlib> #include <iomanip> #include <cmath> #include <cassert> #include <ctime> #include <map> #include <set> using namespace std; #pragma comment(linker, "/stck:1024000000,1024000000") #define lowbit(x) (x&(-x)) #define max(x,y) (x>=y?x:y) #define min(x,y) (x<=y?x:y) #define MAX 100000000000000000 #define MOD 1000000007 #define pi acos(-1.0) #define ei exp(1) #define PI 3.1415926535897932384626433832 #define ios() ios::sync_with_stdio(true) #define INF 0x3f3f3f3f #define mem(a) ((a,0,sizeof(a))) typedef long long ll; int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int dp[106][106],vis[106][106]; int g[106][106]; int n,sx,sy,tx,ty; struct node { int x; int y; int value; bool operator<(const node &a) const { return a.value<value; } }ans,pos; void dfs(int u,int v,int A,int B) { priority_queue<node>q; memset(dp,62,sizeof(dp)); memset(g,0,sizeof(g)); ans.x=u; ans.y=v; ans.value=0; dp[u][v]=0; g[u][v]=1; q.push(ans); while(!q.empty()) { pos=q.top(); q.pop(); if(pos.x==A && pos.y==B) { printf("%d ",pos.value); return ; } for(int i=0;i<4;i++) { int xx=pos.x+dir[i][0]; int yy=pos.y+dir[i][1]; if(xx>=1 && xx<=n && yy>=1 && yy<=n && dp[xx][yy]>pos.value+vis[xx][yy] && !g[xx][yy]) { g[xx][yy]=1; ans.x=xx; ans.y=yy; ans.value=pos.value+vis[xx][yy]; dp[xx][yy]=pos.value+vis[xx][yy]; q.push(ans); } } } } int main() { while(scanf("%d",&n)!=EOF) { memset(vis,0,sizeof(vis)); memset(dp,62,sizeof(dp)); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { scanf("%d",&vis[i][j]); if(vis[i][j]==-1) {sx=i;sy=j;} if(vis[i][j]==-2) {tx=i;ty=j;} } } vis[tx][ty]=vis[sx][sy]=0; dfs(sx,sy,tx,ty); } return 0; }