Future Vision
题号:NC232084
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

Kyooma有一把剑,他喜欢使用这把剑与别人击剑。有一天,他的剑突然传送走了,于是Kyooma开始寻找他的剑。
经过长途跋涉,Kyooma终于来到了一个迷宫的门口。他知道自己的剑一定在迷宫的某个地方,但他的剑可以在这个迷宫中瞬移!
现在,Kyooma向你寻求帮助。请告诉他是否能找到剑,因为你可以通过你的特殊能力 未来视 预测在接下来的k分钟内剑会在哪里。
迷宫由nm列的方格组成,Kyooma每分钟可以向上、下、左、右移动到相邻的方格,或者什么也不做。Kyooma在第0分钟处于起始位置。
Kyooma不能穿过墙壁或爬上墙壁, 但他可以到达剑出现的位置并等待剑出现
注意剑可以出现在墙壁上方,并且剑会在第k-1分钟结束后永久传送离开迷宫,这意味着Kyooma将永远无法找到他的剑!

输入描述:

输入的第一行包含一个整数 ,表示接下来有t组测试。
每个测试用例的第一行包含两个整数 nm
接下来 n 行每行包含m个字符,表示Kyooma所在的迷宫。 并且这些迷宫中的字符中的每一个都是以下字符之一:
'#' --- 表示当前格是一堵墙
'.' --- 表示当前格是一个空地
'H' --- 表示Kyooma在迷宫中的初始位置, 而且这是一个空地
题目保证每组测试用例中都有且只有一个 ‘H'。
下一行包含一个整数,即你预测了接下来k分钟剑的位置。
之后k行每行包含两个整数,表示从第0分钟到第k-1分钟剑的位置。

输出描述:

对于每组测试数据单独输出一行。
如果Kyooma可以成功找到他的剑,输出"YES"(不包含引号)和 他最快能找到剑的时刻,用空格分隔。否则,输出"NO"(不包含引号)。
示例1

输入

复制
2
4 4
.H#.
....
.#..
.#.#
1
1 2
5 4
H..#
.#..
.#..
#..#
#...
4
1 2
2 2
3 4
5 2

输出

复制
YES 0
NO

说明

在第一个测试用例中,Kyooma可以在 0 时刻到达位置(1,2)并找到他的剑。
在第二个测试案例中,Kyooma找不到他的剑。