← 返回题目列表

Codeforces · 1365/D

D. 解决迷宫

中文机器翻译题面 查看原题

Vivek 遇到了问题。他有一个迷宫,可以表示为 $$$n \times m$$$ 网格。每个网格单元可以代表以下内容:

- 空 — '.'
- 墙 — '#'
- 好人 — 'G'
- 坏人 — 'B'

逃离迷宫的唯一出口是在单元格$$$(n, m)$$$处。

仅当某个单元格与当前单元格共享一侧且不包含墙壁时,人员才能移动到该单元格。维韦克想用墙壁来封锁一些空的牢房,这样所有的好人都能够逃脱,而坏人则无法逃脱。最初包含“G”或“B”的单元格不能被阻挡并且可以穿过。

帮助他确定是否存在一种方法可以用墙壁替换一些(零个或更多)空单元格来满足上述条件。

保证单元格 $$$(n,m)$$$ 为空。 Vivek 也可以阻止该单元格。

输入

第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 100)$$$ — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$、$$$m$$$ $$$(1 \le n, m \le 50)$$$ — 迷宫中的行数和列数。

接下来的 $$$n$$$ 行包含 $$$m$$$ 个字符。他们描述了迷宫的布局。如果一行上的字符等于“.”,则相应的单元格为空。如果它等于“#”,则单元格有墙。 “G”对应好人,“B”对应坏人。

输出

对于每个测试用例,如果存在用墙壁替换某些空单元格以满足给定条件的方法,则打印“Yes”。否则打印“否”

您可以以任何大小写方式打印每个字母(大写或小写)。

示例

输入 #1

6
1 1
.
1 2
G.
2 2
#B
G.
2 3
G.#
B#.
3 3
#B.
#..
GG.
2 2
#B
B.

输出 #1

Yes
Yes
No
No
Yes
Yes

注意

对于第一个和第二个测试用例,所有条件都已满足。

对于第三个测试用例,只有一个空单元格$$$(2,2)$$$,如果用墙替换它,那么$$$(1,2)$$$处的好人将无法逃脱。

对于第四个测试用例,$$$(1,1)$$$ 的好人无法逃脱。

对于第五个测试用例,Vivek 可以阻止单元格 $$$(2,3)$$$ 和 $$$(2,2)$$$。

对于最后一个测试用例,Vivek 可以阻止目标单元格 $$$(2, 2)$$$。