牛客网 2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛- PUBG
程序员文章站
2023-12-24 16:25:33
...
链接:https://www.nowcoder.com/acm/contest/118/A
来源:牛客网
题目链接:点击打开链接
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld
题目描述
最近,喜爱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
分析:
BFS+优先队列。
得多练,太马虎。具体分析看代码。
在这里要分享一个小东西,因为本人平时不怎么用Dev,所以刚才写题的时候,本来本题的变量定义的有 y1 ,然后给我提示错误,我查了一下,解释如下:
因为"y1"在gcc(mingw)里面是一个内置函数,不能把它声明成函数之外的东西。
Dev-C++是一个C&C++开发工具,使用 Delphi/Kylix 开发, 它是一款*软件,遵守GPL协议。它集合了GCC、MinGW等众多*软件,并且可以从工具支持网站上取得最新版本的各种工具支持,而这一切工作都是来自全球的*者所做的工作,并且你拥有对这一切工具*使用的权利,包括取得源代码等,前提是你也必 须遵守GNU协议。它使用 MinGW/GCC/Cygwin 编译器,遵循C/C++标准。
#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
int s[105][105];
int vis[105][105];
int xx,yy,ss,ee;
int zb[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
int n;
struct book{
int x,num,y;
///定义结构体的优先队列,按照走到该点所遇见的总人数的数量进行排列,人数少的先出队
friend bool operator<(book a, book b)
{
return a.num > b.num;
}
};
bool check(int x,int y)///检查该点是否出边界
{
if(x>=0&&x<n&&y>=0&&y<n)
return true;
return false;
}
void BFS()
{
priority_queue<book>q;///定义优先队列
book u,v;
u.x=xx;
u.y=yy;
u.num=0;
q.push(u);
vis[u.x][u.y]=1;///将起始点做标记
while(!q.empty())
{
u=q.top();///注意优先队列的取队首元素和栈的用法是一样的
q.pop();
for(int i=0;i<4;i++)
{
v.x=u.x+zb[i][0];
v.y=u.y+zb[i][1];
v.num=u.num;///暂时先不要加上自身所遇见的人数
if(check(v.x,v.y)&&!vis[v.x][v.y])///如果该点可以走
{
vis[v.x][v.y]=1;///将其标记
if(v.x==ss&&v.y==ee)///如果是终点,则输出结束
{
printf("%d\n",v.num);
return ;
}
v.num=u.num+s[v.x][v.y];///不是终点的话,加上自身的人数入队
q.push(v);
}
}
}
return ;
}
int main()
{
while(~scanf("%d",&n))
{
memset(vis,0,sizeof(vis));///标记数组初始化
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>s[i][j];
if(s[i][j]==-1)///将起点位置做记录
{
xx=i;
yy=j;
s[i][j]=0;
}
if(s[i][j]==-2)///将终点位置做记录
{
ss=i;
ee=j;
s[i][j]=0;
}
}
}
BFS();
}
return 0;
}
推荐阅读
-
牛客网 2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛- PUBG
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 D 打篮球(java)
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 C 颜料的混合(java)
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛--I郊游(数学题)
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 E 233(java)
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 F 扫雷(java)
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 H-程序员的好印象【LIS】
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 程序员的好印象
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 C 颜料的混合 (计算几何)