Solve The Maze

题意翻译

### 题目描述 给出一个 $n$ 行 $m$ 列的网格，每个格子上有四种情况： - `.` 表示这个格子是空地。 - `#` 表示这个格子是墙。 - `G` 表示这个格子是好人。 - `B` 表示这个格子是坏人。 `G`，`B`格子都可以认为是空地。 你需要判断能否 `.` 格子上放任意数量的墙，保证所有好人可以通过在空地间移动到达点 $(n,m)$ 而所有坏人都不行。 ### 输入格式 **本题有多组数据** 第一行有一个正整数 $T$，表示有 $T$ 组数据。 每组数据的第一行有两个正整数 $n, m$，表示网格图的行数和列数。 之后 $n$ 行，每行一个长度为 $m$ 的字符串，描述了这张网格图。 保证 $1\le t\le100$，$1\le n, m\le50$。 ### 输出格式 每组数据输出一行 `yes` 或 `no`，大小写任意。

题目描述

Vivek has encountered a problem. He has a maze that can be represented as an $ n \times m $ grid. Each of the grid cells may represent the following: - Empty — '.' - Wall — '\#' - Good person — 'G' - Bad person — 'B' The only escape from the maze is at cell $ (n, m) $ . A person can move to a cell only if it shares a side with their current cell and does not contain a wall. Vivek wants to block some of the empty cells by replacing them with walls in such a way, that all the good people are able to escape, while none of the bad people are able to. A cell that initially contains 'G' or 'B' cannot be blocked and can be travelled through. Help him determine if there exists a way to replace some (zero or more) empty cells with walls to satisfy the above conditions. It is guaranteed that the cell $ (n,m) $ is empty. Vivek can also block this cell.

输入输出格式

输入格式

The first line contains one integer $ t $ $ (1 \le t \le 100) $ — the number of test cases. The description of the test cases follows. The first line of each test case contains two integers $ n $ , $ m $ $ (1 \le n, m \le 50) $ — the number of rows and columns in the maze. Each of the next $ n $ lines contain $ m $ characters. They describe the layout of the maze. If a character on a line equals '.', the corresponding cell is empty. If it equals '\#', the cell has a wall. 'G' corresponds to a good person and 'B' corresponds to a bad person.

输出格式

For each test case, print "Yes" if there exists a way to replace some empty cells with walls to satisfy the given conditions. Otherwise print "No" You may print every letter in any case (upper or lower).

输入输出样例

输入样例 #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

说明

For the first and second test cases, all conditions are already satisfied. For the third test case, there is only one empty cell $ (2,2) $ , and if it is replaced with a wall then the good person at $ (1,2) $ will not be able to escape. For the fourth test case, the good person at $ (1,1) $ cannot escape. For the fifth test case, Vivek can block the cells $ (2,3) $ and $ (2,2) $ . For the last test case, Vivek can block the destination cell $ (2, 2) $ .