despores

Untitled

Dec 20th, 2019
172
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.67 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <bitset>
  7. #include <algorithm>
  8. #include <iomanip>
  9. #include <cmath>
  10. #include <unordered_set>
  11. #include <unordered_map>
  12. #include <queue>
  13. #include <deque>
  14. #include <stack>
  15. #include <cstring>
  16. #include <numeric>
  17. #include <random>
  18. using namespace std;
  19.  
  20. typedef long long ll;
  21. typedef long double ld;
  22. typedef pair <int, int> pii;
  23.  
  24. #define FOR(i, k, l) for(int i = k; i < l; i++)
  25. #define DFOR(i, k, l) for(int i = k; i > l; i--)
  26. #define FA(i, k) for(int i = 0; i < int(k.size()); i++)
  27. #define DFA(i, k) for(int i = int(k.size()) - 1; i > -1; i--)
  28. #define ASKS(i) for(cin >> (i); (i)--;)
  29.  
  30. #define MAXINT 2147483647
  31. #define endl '\n'
  32. #define all(x) x.begin(), x.end()
  33. #define fi first
  34. #define se second
  35.  
  36. vector<int> gr[200011];
  37. bool used[200011] = {0};
  38.  
  39. bool way = false;
  40. bool dfs(int v, int r) {
  41.     used[v] = true;
  42.     int cnt = 0;
  43.     bool fl = false;
  44.     FA(i, gr[v]) {
  45.         int to = gr[v][i];
  46.         if(!used[to]) {
  47.             cnt++;
  48.             if(to == r) way = true;
  49.             fl = dfs(to, r);
  50.         }
  51.     }
  52.     if((cnt == 0 && v !=r) || fl) return true;
  53.     else return false;
  54. }
  55.  
  56.  
  57. int main() {
  58.     ios::sync_with_stdio(0);
  59.     cin.tie(0);
  60.     cout.tie(0);
  61.     int m,n;
  62.     cin >> n >> m;
  63.     pair<int, char> field[n][m];
  64.     int c = 0;
  65.     FOR(i, 0, n) {
  66.         FOR(j, 0, m) {
  67.             cin >> field[i][j].second;
  68.             field[i][j].first = c;
  69.             c++;
  70.         }
  71.     }
  72. //    FOR(i, 0, n) {
  73. //        FOR(j, 0, m) cout << field[i][j].fi << " " << field[i][j].second << " ";
  74. //        cout << endl;
  75. //    }
  76.     int st, end;
  77.     FOR(i, 0, n) {
  78.         FOR(j, 0, m) {
  79.             if(field[i][j].second != '#') {
  80.                 if(i-1 >= 0 && field[i-1][j].second != '#') gr[field[i][j].first].push_back(field[i-1][j].first);
  81.                 if(i+1 < n && field[i+1][j].second != '#') gr[field[i][j].first].push_back(field[i+1][j].first);
  82.                 if(j-1 >= 0 && field[i][j-1].second != '#') gr[field[i][j].first].push_back(field[i][j-1].first);
  83.                 if(j+1 < m && field[i][j+1].second != '#') gr[field[i][j].first].push_back(field[i][j+1].first);
  84.             }
  85.             if(field[i][j].second == '1') st = field[i][j].first;
  86.             if(field[i][j].second == '2') end = field[i][j].first;
  87.         }
  88.     }
  89. //    FOR(i, 0, 15) {
  90. //        FA(j, gr[i]) cout << i <<" " <<  gr[i][j] << " ";
  91. //        cout << endl;
  92. //    }
  93. //    cout << st << " " << end;
  94.     if(dfs(st, end)) {
  95.         if (way) {
  96.             cout << "YES\n";
  97.             return 0;
  98.         }
  99.     }
  100.     cout << "NO\n";
  101.     return 0;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment