【模拟】蚂蚁（jzoj 1508）

2024-01-30 00:32

文章标签 模拟蚂蚁 jzoj 1508

本文主要是介绍【模拟】蚂蚁（jzoj 1508），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

蚂蚁

题目大意：

有n只蚂蚁，他们各往一个方向走（上北，下南，左西和有东四个方向），他们如果撞到一起就会直接消失，每个单位时间走一格，但有一种情况：两只蚂蚁相距一格，两只蚂蚁相向而行，就会在0.5秒后相撞消失，求最后有多少只蚂蚁活着

数据范围限制

1 ≤ N ≤ 50

-1000 ≤ x,y ≤ 1000

对于50%的数据，蚂蚁的坐标范围【-100，100】

提示

在这里插入图片描述

解题思路：

这道题就是一道模拟题，一般会想到枚举每一个单位时间，但这里要0.5地加，因为有可能两个相向而行的蚂蚁距离为一，如果是每次加一就会直接传过去

然后判断他们有没有相撞时，因为有可能是多个蚂蚁相撞，所以我们要先枚举一次所有蚂蚁，然后再枚举一次所有蚂蚁，要判断是否不是同一只，位置是否相同，是否都活着，如果满足，就说明碰撞，先将第二次枚举到的蚂蚁清除，然后将结果+1，再记录下来，等第二次枚举结束后，再来判断第一次枚举到的蚂蚁有没有撞到其他蚂蚁，撞到了就清除，在结果+1，最后输出n-结果即可

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
const double dx[5]={0,0.5,-0.5,0,0};//四个方向的行的变化
const double dy[5]={0,0,0,0.5,-0.5};//四个方向的列的变化
int n,p[55],ans;
bool pd;
double maxx,minn;
string str;
struct
{int to;double x,y;
}a[55];
int main()
{scanf("%d",&n);cin>>str;str=' '+str;for (int i=1;i<=n;++i){scanf("%lf %lf",&a[i].y,&a[i].x);//输入maxx=max(maxx,max(a[i].x,a[i].y));//求最大minn=min(minn,min(a[i].x,a[i].y));//求最小if (str[i]=='N') a[i].to=1;//四个方向if (str[i]=='S') a[i].to=2;if (str[i]=='E') a[i].to=3;if (str[i]=='W') a[i].to=4;}for (double t=minn;t<=maxx;t+=0.5)//用最大和最小来枚举，可以使最远的两个相撞完后结束，因为有题意中的情况{for (int i=1;i<=n;++i)if (!p[i])a[i].x+=dx[a[i].to],a[i].y+=dy[a[i].to];//移动for (int i=1;i<=n;++i)if (!p[i])//判断是否还在{pd=false;//预处理for (int j=1;j<=n;++j)//枚举其他点if (!p[j]&&a[i].x==a[j].x&&a[i].y==a[j].y&&i!=j)//判断是否还在，是否不同，是否在同一个位置{pd=true;记录p[j]=1;//记录ans++;//结果加一}if (pd) p[i]=1,ans++;//如果有和其他蚂蚁碰撞，就记录+结果加一}}printf("%d",n-ans);//输出剩下的return 0;
}