http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1338. 苦无
时间限制:3.0s   内存限制:256.0MB  
总提交次数:18   AC次数:5   平均分:38.00
将本题分享到:
   
 
问题描述
  苦无(Kunai)是一种忍者使用的形状像刀的武器,忍者通过投掷苦无攻击对手。
  现在有N名忍者聚集在一块HW列的棋盘式的广场上。每个忍者都站在其所在方块的中心处,任何两个忍者都不在同一个方块上。每个忍者都拿着一个苦无,面朝上、下、左、右四个方向中的一个方向站着。在时刻0,所有忍者同时向其所朝向的方向投掷苦无。
  每个苦无将会一直保持其初始的方向,并以单位速度飞行。如果某个时刻一个位置上多于一个的苦无,它们将会相撞并且消失。苦无特别小,可以看成质点。同时,由于忍者的移动速度特别快,他们不会被苦无击中。
  在下面的例子中,我们用箭头来表示苦无,而箭头的方向即为苦无的方向。在这些图中,所有的苦无都会相撞后消失。

  在下面的图中,两个粗线箭头表示的苦无不会相撞。其中在第二个和第三个图中,其中一个粗线表示的苦无会与细线表示的苦无相撞后消失,因此不会撞上另一个粗线表示的苦无。

  你的任务是计算经过足够长的时间之后,在这个W × H的广场中有多少格子被苦无经过。
数据规模和约定
  1 ≤ N ≤ 100,000 忍者数;
  1 ≤ W ≤ 1,000,000,000 列数;
  1 ≤ H ≤ 1,000,000,000 行数;
  1 ≤ XiW,1 ≤ YiH 坐标范围。

  在10%的数据中,N ≤ 1000, W ≤ 1000, H ≤ 1000。
  在40%的数据中,N ≤ 1000。
输入格式
  从标准输入读入数据。
  第一行包含两个被空格隔开的整数W, H,表示广场的尺寸为WH行。
  第二行包含一个整数N,表示忍者的数量。
  接下来N行中,第i行有三个以空格分隔的整数Xi, Yi, Di, 表示第i个忍者处在从左往右的Xi列、从上往下的第Yi行,任何两个忍者不在同一个位置。第i个忍者面向的方向由Di表示,分别为:
  Ÿ Di = 0,表示忍者向右;
  Ÿ Di = 1,表示忍者向上;
  Ÿ Di = 2,表示忍者向左;
  Ÿ Di = 3,表示忍者向下。
输出格式
  输出到标准输出。
  输出一个整数,表示经过足够长的时间之后,在这个W × H的广场中被苦无经过的格子数量。
样例输入
5 4
5
3 3 2
3 2 0
4 2 2
5 4 1
1 1 3
样例输出
11
样例说明
  在时刻0,苦无的情况如下图所示

  在下面的描述中,忍者i投掷的苦无将用苦无i表示。
  在时刻0.5,苦无2和苦无3相撞后消失。
  下图为时刻1的情况,加深的格子表示已经被苦无经过。

  在时刻2,苦无1和苦无5相撞后消失,此时的广场如下图所示。

  之后没有苦无相撞。再经过足够时间后的广场如下图所示。

  共有11个格子被苦无经过,因此输出11。
样例输入
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
样例输出
29