欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客网 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

题目描述

牛客网 2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛-	PUBG
最近,喜爱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;
}




















上一篇:

下一篇: