3859: 【CSP2022】舞台表演
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：42
解决：8
题目描述
文件读写stage.in/out
小 X 终于找到了自己的舞台，希望进行一次尽兴的表演。
不妨认为舞台是一个n行m列的矩阵，矩阵中的某些方格上堆放了一些装饰物，其他的则是空地。小 X 可以在空地上滑动，但不能撞上装饰物或滑出舞台， 否则表演就失败了。
小 Y 为了让小 X 表演得尽量顺畅，提前为小 X 写好了每一段时间的移动方向。每个时刻，听话的小 X 都会依据小 Y 写好的所在时间段的方向（东、西、南、北）向相邻的方格滑动一格。由于小 Y 之前没有探查过舞台的情况，如果小 X 直接按照小 Y 写好的来移动，很容易表演失败。
不过，小 Y 是个天使，拥有让小 X 停在原地的魔法，也就是某一时刻，小X 以为自己移动了实际上没有移动。为了让小 X 表演得尽量完美，小 Y 想使小X 在舞台上滑行的路程尽量长（当然不能中途表演失败）。可惜小 Y 的智商不足以完成这么复杂的计算，希望你来帮助她决定哪些时刻该使用魔法。当然，她关心的首先是最长的路程是多少。
输入
输入的第一行包含五个整数n,m, x, y和k。(x, y)为小 X 的初始位置， k为时间的段数。
接下来n行每行包含m个字符，描述这个舞台（“.”表示该位置是空地，“x”表示该位置有装饰物）。
接下来k行每行包含三个整数si,ti,di(1 ≤ i≤ k)，表示在时间段[si,ti]内，小 X
的移动方向是di 。di 为1,2,3,4 中的一个，依次表示北、南、西、东（分别对应矩阵中的上、下、左、右）。
输出
输出一行包含一个整数，表示小 X 滑行的最长路程。
样例输入 复制
4 5 4 1 3
..xx.
.....
...x.
.....
1 3 4
4 5 1
6 7 3样例输出 复制
6