CF1365D Solve The Maze

Vivek has encountered a problem. He has a maze that can be represented as an n×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)(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.

Input

The first line contains one integer t (1≤t≤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≤n,m≤50)— the number of rows and columns in the maze.

Each of the next n lines contain mm 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.

Output

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).

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
6
1 1
.
1 2
G.
2 2
#B
G.
2 3
G.#
B#.
3 3
#B.
#..
GG.
2 2
#B
B.

output

1
2
3
4
5
6
Yes
Yes
No
No
Yes
Yes

题意：一个网格上有好人有坏人，放置一些墙，使得只有好人能到达 （n,m）

可以观察到：

1、好人G 到达终点的路径上不能出现坏人 B, 显然。

2、坏人旁边不能有好人

所以可以这样处理：

1、先判断所有的好人是否可以不经过坏人到达终点，不可以则输出 “NO”。

2、然后处理所有坏人，将每一个坏人周围为 “.” 的全改为 “#” ，“B” 不处理，但是如果有 “G” 则不可行。因为经过上一步的处理，所有的好人都是不经过坏人到达终点的，所以此坏人B也是可以到达终点。

3、再次判断是否所有的好人能否都到达终点。

需要优化的地方是: 对于已经判断可以到达的点，后续再次经过时，可直接跳出。另 dfs 也需即时跳出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
const int MAX=50+10;
int t,n,m,gx[3000],gy[3000],bx[3000],by[3000],gl,bl;
int vis[MAX][MAX],rev[MAX][MAX];
int aw[4][2]={-1,0,0,1,1,0,0,-1},ok=0;
char a[MAX][MAX];
bool judge(int x,int y){
	if(x<1||x>n||y<1||y>m) return false;
	return true;
} 
void dfs(int x,int y,int key){
	if(ok) return;
	if(x==n && y==m) {
		ok = 1;	return;	
	}
	fi(i,0,4){
		int tx = x + aw[i][0],ty = y + aw[i][1];
		if(judge(tx,ty) && vis[tx][ty] != key&&a[tx][ty]!='#'&&a[tx][ty]!='B'){
			if(rev[tx][ty]) {
				ok =1 ;return;
			}
			vis[tx][ty]=key; 
			dfs(tx,ty,key);
		}
	}
}

int main(){
//	freopen("in","r",stdin);
	sf(t);
	while(t--){
		sf(n);sf(m);
		fi(i,1,n+1) scanf("%s",a[i]+1);
		gl=bl=0;
		fi(i,1,n+1)
			fi(j,1,m+1){
				if(a[i][j]=='G') {
					gx[gl] = i; gy[gl++] = j;
				}else if(a[i][j]=='B'){
					bx[bl] = i;by[bl++] = j;
				}
			} 
		int cnt=0;
		mem(vis,0);mem(rev,0);
		fi(i,0,gl){
			ok=0;
			dfs(gx[i],gy[i],i+1);
			if(ok) {
				cnt++;rev[gx[i]][gy[i]] = 1;
			}
			else break;
		}
		if(cnt!=gl){
			puts("NO");continue;
		}
		if(bl==0){
			puts("YES");continue;
		}
		ok =1;
		fi(i,0,bl){
			ok = 1;
			fi(j,0,4){
				int tx = bx[i] + aw[j][0],ty = by[i] + aw[j][1];
				if(judge(tx,ty) ){
					if(a[tx][ty]=='.') a[tx][ty] = '#';
					else if(a[tx][ty]=='G'){
						ok =0 ;break;
					}
				}
			}
			if(!ok) break;
		}
		if(!ok) {
			puts("NO");continue;
		}
		cnt=0;
		mem(vis,0);mem(rev,0);
		fi(i,0,gl){
			ok=0;
			dfs(gx[i],gy[i],i+1);
			if(ok) {cnt++;rev[gx[i]][gy[i]] = 1;}
			else break;
		}
		if(cnt!=gl){
			puts("NO");continue;
		}else puts("YES");
	}
	return 0;
}