| 题目名称 | 798. [APIO2012] 苦无 |
|---|---|
| 输入输出 | kunai.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 57 |
| 题目来源 |
 王者自由
于2012-05-21加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：4， 提交：16， 通过率：25% | ||||
 ATM |
100 | 7.379 s | 25.42 MiB | C++ |
 bbsh |
100 | 9.317 s | 93.75 MiB | C++ |
 ztx |
100 | 14.617 s | 92.10 MiB | C++ |
 My_love |
100 | 14.963 s | 99.68 MiB | C++ |
|
bbsh |
68 | 8.367 s | 19.40 MiB | C++ |
|
ztx |
21 | 14.660 s | 93.75 MiB | C++ |
|
ztx |
8 | 13.495 s | 78.87 MiB | C++ |
 王者自由 |
1 | 57.232 s | 0.19 MiB | C++ |
 szkzyc |
0 | 0.000 s | 0.00 MiB | C++ |
|
szkzyc |
0 | 0.000 s | 0.00 MiB | C++ |
| 关于 苦无 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
真是太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了太弱了
| ||||
|
转大神题解于此，造福后人
http://vfleaking.blog.163.com/blog/static/17480763420124259021839/  Ezio
2014-07-27 12:30
1楼
| ||||
-
【问题描述】
苦无(Kunai)是一种忍者使用的形状像刀的武器，忍者通过投掷苦无攻击对
手。
现在有N名忍者聚集在一块H行W列的棋盘式的广场上。每个忍者都站在
其所在方块的中心处，任何两个忍者都不在同一个方块上。每个忍者都拿着一个
苦无，面朝上、下、左、右四个方向中的一个方向站着。在时刻0，所有忍者同
时向其所朝向的方向投掷苦无。
每个苦无将会一直保持其初始的方向，并以单位速度飞行。如果某个时刻一
个位置上多于一个的苦无，它们将会相撞并且消失。苦无特别小，可以看成质点。
同时，由于忍者的移动速度特别快，他们不会被苦无击中。
在下面的例子中，我们用箭头来表示苦无，而箭头的方向即为苦无的方向。
在这些图中，所有的苦无都会相撞后消失。
在下面的图中，两个粗线箭头表示的苦无不会相撞。其中在第二个和第三个
图中，其中一个粗线表示的苦无会与细线表示的苦无相撞后消失，因此不会撞上
另一个粗线表示的苦无。
你的任务是计算经过足够长的时间之后，在这个W × H的广场中有多少格
子被苦无经过。
【数据范围】
1 ≤ N ≤ 100,000 忍者数；
1 ≤ W ≤ 1,000,000,000 列数；
1 ≤ H ≤ 1,000,000,000 行数；
1 ≤ Xi ≤ W，1 ≤ Yi ≤ H 坐标范围。
在10%的数据中，N ≤ 1000, W ≤ 1000, H ≤ 1000。
在40%的数据中，N ≤ 1000。
【输入格式】
从标准输入读入数据。
第一行包含两个被空格隔开的整数W, H，表示广场的尺寸为W列H行。
第二行包含一个整数N，表示忍者的数量。
接下来N行中，第i行有三个以空格分隔的整数Xi, Yi, Di
, 表示第i个忍者
处在从左往右的Xi 列、从上往下的第Yi 行，任何两个忍者不在同一个位置。第
i个忍者面向的方向由Di 表示，分别为：
Di = 0，表示忍者向右；
Di = 1，表示忍者向上；
Di = 2，表示忍者向左；
Di = 3，表示忍者向下。
【输出格式】
输出到标准输出。
输出一个整数，表示经过足够长的时间之后，在这个W × H的广场中被苦
无经过被苦无经过的格子数量。
【样例输入1】
5 4
5
3 3 2
3 2 0
4 2 2
5 4 1
1 1 3
【样例输出1】
11
【样例说明】
在时刻0，苦无的情况如下图所示
在下面的描述中，忍者i投掷的苦无将用苦无i表示。
在时刻0.5，苦无2和苦无3相撞后消失。
下图为时刻1的情况，加深的格子表示已经被苦无经过。
在时刻2，苦无1和苦无5相撞后消失，此时的广场如下图所示。
之后没有苦无相撞。再经过足够时间后的广场如下图所示。
共有11个格子被苦无经过，因此输出11。
【样例输入2】
7 6
12
3 2 3
6 3 2
7 1 3
1 5 0
3 6 1
6 6 1
4 5 2
1 3 0
6 5 2
5 1 2
6 4 3
4 1 3
【样例输出2】
29