fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
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
https://ideone.com/heJHCG
language:
C++ 4.3.2 (gcc-4.3.2)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!