cosenza987

Untitled

Jan 22nd, 2022
152
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.33 KB | None | 0 0
  1. //#pragma GCC optimize("Ofast")
  2. //#pragma GCC optimize ("unroll-loops")
  3. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4. //THESE ARE LAST DITCH EFFORTS!!!
  5.  
  6. #include <bits/stdc++.h>
  7.  
  8. using namespace std;
  9.  
  10. vector<vector<string>> v(1000);
  11.  
  12. int dx[] = {0, 1, 0, -1};
  13. int dy[] = {1, 0, -1, 0};
  14.  
  15. bool bfs(pair<int, int> a, pair<int, int> b, int n, int m, int k, bool fuck) {
  16.     vector<vector<bool>> vis(n, vector<bool>(m));
  17.     vis[a.first][a.second] = true;
  18.     queue<pair<int, int>> q;
  19.     q.push({a.first, a.second});
  20.     while(!q.empty()) {
  21.         auto p = q.front();
  22.         q.pop();
  23.         for(int i = 0; i < 4; i++) {
  24.             if(p.first + dx[i] >= 0 and p.first + dx[i] < n and p.second + dy[i] >= 0 and p.second + dy[i] < m and v[k][p.first + dx[i]][p.second + dy[i]] != '#' and !vis[p.first + dx[i]][p.second + dy[i]]) {
  25.                 if(!fuck) {
  26.                     if(v[k][p.first + dx[i]][p.second + dy[i]] == 'D') {
  27.                         continue;
  28.                     }
  29.                 }
  30.                 vis[p.first + dx[i]][p.second + dy[i]] = true;
  31.                 q.push({p.first + dx[i], p.second + dy[i]});
  32.             }
  33.         }
  34.     }
  35.     return vis[b.first][b.second];
  36. }
  37.  
  38. int main() {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(0);
  41.     freopen("in.txt", "r", stdin);
  42.     freopen("output.txt", "w", stdout);
  43.     string s;
  44.     int cur = 0;
  45.     while(getline(cin, s)) {
  46.         if(s.size() == 0) {
  47.             cur++;
  48.         } else {
  49.             v[cur].push_back(s);
  50.         }
  51.     }
  52.     for(int k = 0; k < cur; k++) {
  53.         int n = v[k].size();
  54.         int m = v[k][0].size();
  55.         pair<int, int> s, t, g;
  56.         for(int i = 0; i < n; i++) {
  57.             for(int j = 0; j < m; j++) {
  58.                 if(v[k][i][j] == 'S') {
  59.                     s = {i, j};
  60.                 }
  61.                 if(v[k][i][j] == 'G') {
  62.                     g = {i, j};
  63.                 }
  64.                 if(v[k][i][j] == 'T') {
  65.                     t = {i, j};
  66.                 }
  67.             }
  68.         }
  69.         bool a = bfs(s, t, n, m, k, false);
  70.         bool b = bfs(t, g, n, m, k, true);
  71.         bool c = bfs(s, g, n, m, k, false);
  72.         if((a and b) or c) {
  73.             cout << "P ";
  74.         } else {
  75.             cout << "I ";
  76.         }
  77.     }
  78.     return 0;
  79. }
Add Comment
Please, Sign In to add comment