王大锤捡肥皂

Time Limit: 1000 ms

Memory Limit: 65536 KB

Description

我们WanWanMeiXiangDao的王先森也友情加入了我们的题目描述。
王先森在神的指引下,发现每次shower的时候pickup满一定的数量的soap,不用多久,就会升职加薪、当上总经理、出任CEO、迎娶白富美、走上人生巅峰,他想想觉得十分的激动,于是他来到了浴室。
浴室是长条型的,为了简化问题,我们把浴室看做一个2*n矩形图,有些地方没有人,我们用"."表示,有些地方是有障碍的,人不能在那个点,我们用"#"表示,还有些地方是有人的,用"P"来表示,当然只有在人的位置那里的地上才可能有肥皂,不过凑巧的是这一次所有人脚下都有一块肥皂,每个点可以同时站多个人,同时王大锤他不仅能够朝上下左右4个方向走,而且还能够朝斜对角走,前提自然是到达的位置不能有障碍物,现在王大锤想知道,他能否捡满足够的肥皂呢?

Input

第一行输入一个正整数T(T <= 500),表示有T组测试数据。 每组测试数据首先输入两个整数n, m(1 <= n <= 512, 1 <= m <= n * 2),表示浴室是2*n的矩形图和王大锤需要捡的肥皂的数目。 接下来输入2行字符串,仅含有"P","."和"#"三种字符,表示这个浴室。 王大锤一开始在最左上角的点,当然也就是最左上角的点不可能是"#"。

Output

对于每组测试数据,如果王大锤不能捡满足够的肥皂,那么输出一行“Bad Luck”,否则输出王大锤至少需要走的步数。

Sample Input

2
3 2
.#P
#P.
5 3
.P##P
..P#.

Sample Output

2
Bad Luck

Hint

对于第一组样例,他需要捡2个肥皂,先右下斜对角走到第一个P,然后右上斜对角又有一个P,所以只需要走2步。 对于第二组样例,一共要捡3个肥皂,王大锤不能到达最右端上面的点,所以不能达到自己的期望。

Source

“掌赢杯”南京理工大学第六届程序设计大赛

提交代码