Advertisement
WayKillerZ

D - Solve The Maze

May 16th, 2022
641
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define int long long
  4. #define II pair<int, int>
  5. #define III pair<int, pair<int, int>>
  6. #define DI pair<double, int>
  7. #define fs first
  8. #define sc second
  9. #define mp(a, b) make_pair(a, b)
  10. #define LINF 9223372036854775807
  11. #define INF 2147483647
  12.  
  13. using namespace std;
  14.  
  15. int m_x[4] = {0, 0, 1, -1};
  16. int m_y[4] = {1, -1, 0, 0};
  17.  
  18. int n, m;
  19.  
  20. vector<II> bad;
  21. vector<II> good;
  22. string g[51];
  23.  
  24. map<II, int> vst;
  25.  
  26. void dfs() {
  27.     int cnt = 0;
  28.     vst[{n-1, m-1}] = 1;
  29.     stack<II> st;
  30.  
  31.     st.push({n-1, m-1});
  32.  
  33.     while(!st.empty()) {
  34.  
  35.         II u = st.top();
  36.         st.pop();
  37.  
  38.         for(int i = 0; i < 4; i++) {
  39.             int x = max(min(u.fs + m_x[i], n-1), 0ll);
  40.             int y = max(min(u.sc + m_y[i], m-1), 0ll);
  41.  
  42.             II v = {x, y};
  43.             if(vst[v] == 1 || g[x][y] == '#') continue;
  44.  
  45.             vst[v] = 1;
  46.             if(g[x][y] == 'G') cnt ++;
  47.             st.push(v);
  48.         }
  49.     }
  50.  
  51.     if(cnt == good.size()) cout << "Yes\n";
  52.     else cout << "No\n";
  53.  
  54. }
  55.  
  56.  
  57. void solve() {
  58.     bad.clear();
  59.     good.clear();
  60.     vst.clear();
  61.  
  62.     cin >> n >> m;
  63.  
  64.     for(int i = 0; i < n; i++) {
  65.         cin >> g[i];
  66.         for(int j = 0; j < m; j++) {
  67.             if(g[i][j] == 'B') bad.push_back({i, j});
  68.             else if(g[i][j] == 'G') good.push_back({i, j});
  69.         }
  70.     }
  71.  
  72.     if(good.size() == 0) {
  73.         cout << "Yes\n";
  74.         return;
  75.     }
  76.  
  77.     for(int i = 0; i < bad.size(); i++) {
  78.         II b = bad[i];
  79.        
  80.         for(int j = 0; j < 4; j++) {
  81.             int x = max(min(b.fs + m_x[j], n-1), 0ll);
  82.             int y = max(min(b.sc + m_y[j], m-1), 0ll);
  83.            
  84.             if(g[x][y] == 'G' || (x == n-1 && y == m-1)) {
  85.                 cout << "No\n";
  86.                 return;
  87.             }
  88.             g[x][y] = '#';
  89.         }
  90.     }
  91.  
  92.     dfs();
  93. }
  94.  
  95. int32_t main() {
  96.     ios_base::sync_with_stdio(false);
  97.     cin.tie(NULL);
  98.    
  99.     freopen("D.INP", "r", stdin);
  100.     freopen("D.OUT", "w", stdout);
  101.  
  102.     int t;
  103.     cin >> t;
  104.     while(t--) solve();
  105.    
  106.  
  107.     return 0;
  108. }
Advertisement
RAW Paste Data Copied
Advertisement