SP15242 VPL2_AB - Betos Quest

Ethan 被困在一个 $N*M$ 的迷宫中，他位于 $(x_1,y_1)$，终点位于 $(x_2,y_2)$。他每秒钟可以向上下左右任意方向走 $1$ 格，迷宫中的格子分为平地和墙，Ethan 不能通过墙的区域。 有 $K$ 个位置上还有摄像头，坐标已知，它们会监视到它们面前 $R_i$ 范围内的事物（但它们不会监视到自己所在的格子，这些格子 Ethan 同样可以通过），它们每 $1$ 秒会顺时针旋转 $90\degree$。Ethan 不能通过它们正在监视的格子。 但 Ethan 可以使用 $C$ 次隐身技能。技能使用时的那 $1$ 秒，摄像头不会发现他的存在。

第一行输入正整数 $T$，表示数据组数。 每组数据的第一行为四个整数 $N,M,K,C$，意义如上所述。 接下来是一个 $N*M$ 的矩阵表示迷宫地形，其中 `#` 表示墙， `.` 表示平地。 接下来 $K$ 行，第 $i$ 行有四个整数 $X_i,Y_i,R_i,D_i$，分别表示摄像头的 $x$ 和 $y$ 坐标、摄像头的监视范围和摄像头的初始方向。（注：坐标以 $0$ 为起点） 最后两行共四个整数 $x_1,y_1,x_2,y_2$，表示起点坐标和终点坐标。

对于每组数据，先输出一行 `Scenario#i:`，其中 $i$ 表示当前数据组数。接下来一行输出 Ethan 逃出迷宫所用的最短时间；若不能逃脱，请输出 $-1$。 Translated by @此用户无昵称