距离之和
【问题描述】
想象一个机器人位于二维空间。初始时,机器人在(0,0)。有4个命令S,J,I,Z。
具体的,如果机器人在(x,y),在收到S命令之后,移动到(x,y+1),收到J之后,移动到(x,y-1),I命令之后移动到(x+1,y),Z命令之后移动到(x-1,y)。
在这个二维空间有n个固定的点,在每个命令之后,每个固定点会计算自己与机器人的曼哈顿距离,然后返回这些距离的总和。
ps:两个点(x1,y1)和(x2,y2)的曼哈顿|x1-x2|+|y1-y2|。
【输入格式】
第一行是正整数n和m。
接下来n行,每行两个整数,表示控制点的坐标,有些控制点坐标可能相同。
接下来一行,一个长度为m的字符串,表示机器人依次接受到的命令。
【输出格式】
输出m行,每行一个整数,第i行表示第i个命令执行以后所有控制点到机器人的曼哈顿距离之和。
【输入样例】
3 5
0 0
1 1
1 -1
SIJJZ
【输出样例】
5
4
3
4
5
【数据范围与约定】
对于40%的数据:n<=1000,m<=5000。
对于100%的数据:n <= 100000, m <= 300000。
信息
- 难度
- 7
- 分类
- (无)
- 标签
- 递交数
- 45
- 已通过
- 8
- 通过率
- 18%
- 上传者