求指导,这道题用搜索解决的边界条件
  • 板块学术版
  • 楼主D_Birth
  • 当前回复14
  • 已保存回复14
  • 发布时间2025/1/21 14:22
  • 上次更新2025/1/21 16:19:15
查看原帖
求指导,这道题用搜索解决的边界条件
1080508
D_Birth楼主2025/1/21 14:22

1. 蚂蚁

时间限制: 1000ms 空间限制: 262144kB

题目描述

在二维平面坐标轴里面,有N只蚂蚁,第i只蚂蚁所在的点的坐标是(xi, yi),坐标都是整数。所有蚂蚁的移动速度都相等,都是每秒移动1个单位。每只蚂蚁都有一个固定的移动方向,是如下4种方向之一,都是平行于坐标轴的:

  • N表示向北(即朝上), 则y坐标正方向。
  • E表示向东(即朝右), 则x坐标正方向。
  • S表示向南(即向下), 则y坐标负方向。
  • W表示向西(即向左), 则x坐标负方向。

当2只或多只蚂蚁在某个时刻碰(不一定是整数时刻)撞到一起,那么这些蚂蚁都会立即消失。 例如蚂蚁A的初始位置是(0, 0)且方向是向东,蚂蚁B的初始位置是(1, 0)且方向是向西,那么0.5秒后,两只蚂蚁会在点(0.5, 0)处碰撞,两只蚂蚁瞬间都消失。当所有的碰撞结束后,还有多少只蚂蚁存在?不管蚂蚁最终移动到哪里,只要没有消失,都算是存在。

输入格式

第一行,一个整数N(1 ≤ N ≤ 50)。 第二行,一个长度是N的字符串,第i个字符表示第i只蚂蚁的移动方向。 接下来有N行,每行两个整数,表示蚂蚁的横坐标x和纵坐标y。 -1000 ≤ x,y ≤ 1000。输入数据保证,一开始没有两只蚂蚁具有相同的位置。 对于50%的数据, 蚂蚁的坐标范围【-100,100】。

输出格式

一个整数,表示当所有的碰撞结束后,存在的蚂蚁的数量。

样例

Input 1
4
NWNE
0 0
10 10
20 20
30 30
Output 1
2

Input 2
9
EENWWSWSE
-1 0
1 0
0 0
-1 -1
1 -1
0 1
0 -1
-1 1
1 1
Output 2
5

2025/1/21 14:22
加载中...