#P1686. [Usaco2005 Open]Waves 波纹
[Usaco2005 Open]Waves 波纹
[USACO 2005 Open] Waves 波纹
题目描述
水面由整数坐标格表示,非河堤格的初始深度为 。石子在位置 、时刻 落水时,会产生一个深度贡献为 的上凸波。这个波在第 秒位于落水格,随后每秒沿菱形外圈扩展一格。在第 秒,同一位置又产生一个以同样方式传播、深度贡献为 的下凹波。没有河堤阻挡时,波在产生后第 秒覆盖与起点的曼哈顿距离恰好为 的格子。
有两条贯穿整个水面的竖直河堤,位于 和 两列,波不能穿过河堤。沿水平方向传播的波碰到河堤时会反射,反射轴位于河堤列和其相邻水面列之间。也就是说,如果一次水平传播本应进入河堤,它会消耗这一秒,留在同一水面列并改变之后的水平方向。河堤不改变波在竖直方向上的传播。
波相遇时互不改变方向。把同一时刻到达同一格子的所有波的贡献相加,得到这一格的深度。
- 河堤所在格输出
X。 - 深度为正、为零、为负的水面格,分别输出
*、-、o。
反射示意图 · 波的产生和传播示意图 · 叠加示意图
输入格式
第一行四个整数 ,表示石子数、两条河堤的横坐标和要观察的时刻。,,。
接下来 行,每行三个整数 ,表示一颗石子的落水坐标和落水时刻,三个整数均在 内。
保证两条河堤的横坐标不同,石子不会落在河堤上,也不会有两颗石子在同一时刻落到同一格。
输出格式
输出第 秒水面的 字符矩阵。第 1 行对应 ,最后一行对应 。每行从左到右依次对应 。
样例
2 4 100 4
-3 0 1
0 0 2
--------X
-*------X
*-*-*---X
-o-*-*--X
o-----*-X
-o-*-*--X
*-*-*---X
-*------X
--------X