fork download
  1. #include <map>
  2. #include <set>
  3. #include <vector>
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9. typedef pair<int, int>pii;
  10.  
  11. const int MOD = 1e9 + 7;
  12. const int MXN = 200005;
  13.  
  14. int dx[] = {-1, 0, 1};
  15.  
  16. bool withingRange(int x, int y, int N, int M) {
  17. if((x >= 0 && x < N) && (y >= 0 && y < M)) {
  18. return true;
  19. }
  20. return false;
  21. }
  22.  
  23. void demarcate(vector<string> &mat, int x, int y, int N, int M) {
  24. for(int i = 0; i < 3; i++) {
  25. for(int j = 0; j < 3; j++) {
  26. if(abs(dx[i]) == abs(dx[j])) {
  27. continue;
  28. }
  29. int newX = x + dx[i];
  30. int newY = y + dx[j];
  31.  
  32. if(withingRange(newX, newY, N, M) && mat[newX][newY] == '.') {
  33. mat[newX][newY] = '#';
  34. }
  35. }
  36. }
  37. }
  38.  
  39. void demarcateAdjacentToB(vector<string>& mat, int N, int M) {
  40. for(int i = 0; i < N; i++) {
  41. for(int j = 0; j < M; j++) {
  42. if(mat[i][j] == 'B') {
  43. demarcate(mat, i, j, N, M);
  44. }
  45. }
  46. }
  47. }
  48.  
  49. bool check(vector<string>& mat, int x, int y, int N, int M) {
  50. for(int i = 0; i < 3; i++) {
  51. for(int j = 0; j < 3; j++) {
  52. if(abs(dx[i]) == abs(dx[j])) {
  53. continue;
  54. }
  55. int newX = x + dx[i];
  56. int newY = y + dx[j];
  57.  
  58. if(withingRange(newX, newY, N, M)) {
  59. if(mat[newX][newY] == 'G') {
  60. return false;
  61. }
  62. }
  63. }
  64. }
  65. return true;
  66. }
  67.  
  68. bool checkAdjacent(vector<string>& mat, int N, int M) {
  69. bool res = true;
  70. for(int i = 0; i < N; i++) {
  71. for(int j = 0; j < M; j++) {
  72. if(mat[i][j] == 'B') {
  73. res = res & check(mat, i, j, N, M);
  74. }
  75. }
  76. }
  77. return res;
  78. }
  79.  
  80. bool checkPath(vector<string>& mat, int x, int y, int N, int M) {
  81. bool vis[N][M];
  82. vector<pii> myq;
  83.  
  84. for(int i = 0; i < N; i++) {
  85. for(int j = 0; j < M; j++) {
  86. vis[i][j] = false;
  87. }
  88. }
  89.  
  90. myq.push_back(make_pair(x, y));
  91. int siz = 1;
  92. while(siz > 0) {
  93. pii cell = myq[siz-1];
  94. x = cell.first;
  95. y = cell.second;
  96. vis[x][y] = true;
  97.  
  98. myq.pop_back();
  99.  
  100. // cout<<"x: "<<x<<" y: "<<y<<endl;
  101. siz--;
  102.  
  103. for(int i = 0; i < 3; i++) {
  104. for(int j = 0; j < 3; j++) {
  105. if(abs(dx[i]) == abs(dx[j])) {
  106. continue;
  107. }
  108.  
  109. // cout<<"dx: "<<dx[i]<<" dy: "<<dx[j]<<endl;
  110. int newX = x + dx[i];
  111. int newY = y + dx[j];
  112.  
  113. // cout<<"newX: "<<newX<<" newY: "<<newY<<endl;
  114. if(withingRange(newX, newY, N, M) && mat[newX][newY] != '#' && !vis[newX][newY]) {
  115. myq.push_back(make_pair(newX, newY));
  116. siz++;
  117. }
  118. }
  119.  
  120. }
  121. }
  122. if(vis[N-1][M-1]) {
  123. return true;
  124. }
  125. return false;
  126. }
  127.  
  128. void solve() {
  129. int N, M;
  130. vector<string>mat;
  131. string s;
  132.  
  133. cin>>N >>M;
  134.  
  135. for(int i = 0; i < N; i++) {
  136. cin>>s;
  137. mat.push_back(s);
  138. }
  139.  
  140. if(!checkAdjacent(mat, N, M)) {
  141. cout<<"No"<<endl;
  142. return;
  143. }
  144.  
  145. demarcateAdjacentToB(mat, N, M);
  146.  
  147. bool res = true;
  148. for(int i = 0; i < N; i++) {
  149. for(int j = 0; j < M; j++) {
  150. if(mat[i][j] == 'G') {
  151. // cout<<"i: "<<i<<" j: "<<j<<" "<<checkPath(mat, i, j, N, M)<<endl;
  152. res = res & checkPath(mat, i, j, N, M);
  153. }
  154. }
  155. }
  156.  
  157. if(res) {
  158. cout<<"Yes"<<endl;
  159. } else {
  160. cout<<"No"<<endl;
  161. }
  162.  
  163. return;
  164.  
  165. }
  166.  
  167. int main() {
  168. int t;
  169.  
  170. cin>>t;
  171.  
  172. while(t--) {
  173. solve();
  174. }
  175. }
  176.  
Success #stdin #stdout 0s 4496KB
stdin
100
2 3
.#.
.B.
2 3
#G#
BB.
2 3
G.#
B#.
2 3
##.
GB.
2 3
#G.
.B.
2 3
...
B#.
2 3
#GG
...
2 3
#.B
GB.
2 3
B.G
.G.
2 3
BB#
##.
2 3
#G.
G#.
2 3
B.B
##.
2 3
BBB
GG.
2 3
BBG
##.
2 3
BB#
GB.
2 3
GG.
G#.
2 3
#.#
G#.
2 3
G..
...
2 3
GG.
.#.
2 3
B.#
B..
2 3
#GB
#G.
2 3
##G
#G.
2 3
G#B
#..
2 3
.B.
B..
2 3
.#.
#B.
2 3
G#.
B..
2 3
G#.
#B.
2 3
G..
#B.
2 3
.B#
GG.
2 3
G##
#B.
2 3
#G#
G#.
2 3
.B#
#..
2 3
GBG
#G.
2 3
BGB
#...
stdout
Yes
No
No
No
No
Yes
Yes
No
Yes
Yes
No
Yes
No
No
No
Yes
No
Yes
Yes
Yes
No
Yes
No
Yes
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No