Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma GCC optimize("Ofast")
- //#pragma GCC optimize ("unroll-loops")
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- //THESE ARE LAST DITCH EFFORTS!!!
- #include <bits/stdc++.h>
- using namespace std;
- vector<vector<string>> v(1000);
- int dx[] = {0, 1, 0, -1};
- int dy[] = {1, 0, -1, 0};
- bool bfs(pair<int, int> a, pair<int, int> b, int n, int m, int k, bool fuck) {
- vector<vector<bool>> vis(n, vector<bool>(m));
- vis[a.first][a.second] = true;
- queue<pair<int, int>> q;
- q.push({a.first, a.second});
- while(!q.empty()) {
- auto p = q.front();
- q.pop();
- for(int i = 0; i < 4; i++) {
- 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]]) {
- if(!fuck) {
- if(v[k][p.first + dx[i]][p.second + dy[i]] == 'D') {
- continue;
- }
- }
- vis[p.first + dx[i]][p.second + dy[i]] = true;
- q.push({p.first + dx[i], p.second + dy[i]});
- }
- }
- }
- return vis[b.first][b.second];
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- freopen("in.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- string s;
- int cur = 0;
- while(getline(cin, s)) {
- if(s.size() == 0) {
- cur++;
- } else {
- v[cur].push_back(s);
- }
- }
- for(int k = 0; k < cur; k++) {
- int n = v[k].size();
- int m = v[k][0].size();
- pair<int, int> s, t, g;
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < m; j++) {
- if(v[k][i][j] == 'S') {
- s = {i, j};
- }
- if(v[k][i][j] == 'G') {
- g = {i, j};
- }
- if(v[k][i][j] == 'T') {
- t = {i, j};
- }
- }
- }
- bool a = bfs(s, t, n, m, k, false);
- bool b = bfs(t, g, n, m, k, true);
- bool c = bfs(s, g, n, m, k, false);
- if((a and b) or c) {
- cout << "P ";
- } else {
- cout << "I ";
- }
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment