Advertisement
dimuster

antitetris

Sep 28th, 2022
838
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.51 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define ld long double
  7. #define inf 9e18
  8. #define v vector
  9. #define F first
  10. #define S second
  11. #define min(a, b) (a < b ? a : b)
  12. #define max(a, b) (a > b ? a : b)
  13.  
  14.  
  15. int n, m;
  16. v<v<char>> a;
  17. v<v<bool>> used;
  18. v<pair<int, int>> coords;
  19. int ok_path = -1;
  20. string path;
  21.  
  22. void bfs_find(int x, int y, v<pair<int, int>> &coords) {
  23.     queue<pair<int, int>> q, q1;
  24.     char c = a[x][y];
  25.     q.push({x, y});
  26.     while (!q.empty()) {
  27.         int i = q.front().F, j = q.front().S;
  28.         if (i + 1 < n && !used[i + 1][j] && a[i + 1][j] == c) q.push({i + 1, j});
  29.         if (i - 1 >= 0 && !used[i - 1][j] && a[i - 1][j] == c) q.push({i - 1, j});
  30.         if (j + 1 < m && !used[i][j + 1] && a[i][j + 1] == c) q.push({i, j + 1});
  31.         if (j - 1 >= 0 && !used[i][j - 1] && a[i][j - 1] == c) q.push({i, j - 1});
  32. //        q1 = q;
  33. //        for (int u = 0; u < q.size(); u++) {
  34. //            cout << q1.front().F + 1 << " " << q1.front().S + 1 << "  ";
  35. //            q1.pop();
  36. //        }
  37. //        cout << "\n";
  38.         used[i][j] = true;
  39.         coords.push_back({i, j});
  40.         q.pop();
  41.     }
  42. }
  43.  
  44. bool can(int move, pair<int, int> begin, v<pair<int, int>> c) {
  45.     int dx = begin.F - c[0].F, dy = begin.S - c[0].S;
  46.     for (int i = 0; i < c.size(); i++) {
  47.         c[i].F += dx;
  48.         c[i].S += dy;
  49.     }
  50.    
  51.     if (move == 1 && c[0].F == 0) return false;
  52.     for (int i = 0; i < c.size(); i++) {
  53.         if (move == 1) c[i].F -= 1;
  54.         if (move == 2) c[i].S -= 1;
  55.         if (move == 3) c[i].S += 1;
  56.     }
  57.     bool ok = true;
  58.     for (int i = 0; i < c.size(); i++) {
  59.         if (c[i].F >= n || c[i].S >= m || c[i].S < 0 || a[c[i].F][c[i].S] != '.') {
  60.             ok = false;
  61.             break;
  62.         }
  63.     }
  64.     if (!ok) return false;
  65.     return true;
  66. }
  67.  
  68. void dfs(pair<int, int> begin, string p) {
  69.     if (used[begin.F][begin.S]) return;
  70.    
  71.     if (begin.F == 0) {
  72.         ok_path = begin.S;
  73.         path = p;
  74.         return;
  75.     }
  76.     used[begin.F][begin.S] = true;
  77.    
  78.     if (ok_path == -1 && can(1, begin, coords)) dfs({begin.F - 1, begin.S}, "D" + p);
  79.     if (ok_path == -1 && can(2, begin, coords)) dfs({begin.F, begin.S - 1}, "R" + p);
  80.     if (ok_path == -1 && can(3, begin, coords)) dfs({begin.F, begin.S + 1}, "L" + p);
  81. //    1 - UP, 2 - LEFT, 3 - RIGHT
  82. }
  83.  
  84. signed main(signed argc, char* argv[]) {
  85.     ios_base::sync_with_stdio(false);
  86.     cin.tie(NULL);
  87. //    cout.setf(ios::fixed);
  88. //    cout.precision(6);
  89. //    freopen("input.txt", "r", stdin);
  90. //    freopen("output.txt", "w", stdout);
  91.    
  92.     cin >> n >> m;
  93.     a.resize(n, v<char> ('.'));
  94.     for (int i = 0; i < n; i++) {
  95.         for (int j = 0; j < m; j++) {
  96.             cin >> a[i][j];
  97.         }
  98.     }
  99.     v<v<pair<int, int>>> figures;
  100.     used.resize(n, v<bool> (m, false));
  101.     for (int i = 0; i < n; i++) {
  102.         for (int j = 0; j < m; j++) {
  103.             if (a[i][j] == '.' || used[i][j]) continue;
  104.             used[i][j] = true;
  105.             v<pair<int, int>> coord;
  106.             bfs_find(i, j, coord);
  107. //            for (int k = 0; k < coord.size(); k++) {
  108. //                cout << coord[k].F + 1 << " " << coord[k].S + 1 << "  ";
  109. //            }
  110. //            cout << "\n";
  111.             sort(coord.begin(), coord.end());
  112.             figures.push_back(coord);
  113.         }
  114.     }
  115.    
  116.     v<pair<int, string>> ans;
  117.     while (figures.size()) {
  118.         bool ersd = false;
  119.         for (int i = 0; i < figures.size(); i++) {
  120.             used.clear();
  121.             used.resize(n, v<bool> (m, false));
  122.             char symbol = a[figures[i][0].F][figures[i][0].S];
  123.             for (int k = 0; k < figures[i].size(); k++) {
  124.                 a[figures[i][k].F][figures[i][k].S] = '.';
  125.             }
  126.             coords = figures[i];
  127.             ok_path = -1;
  128.             path = "";
  129.             dfs(figures[i][0], "S");
  130.             if (ok_path == -1) {
  131.                 for (int k = 0; k < figures[i].size(); k++) {
  132.                     a[figures[i][k].F][figures[i][k].S] = symbol;
  133.                 }
  134.             } else {
  135.                 ans.push_back({ok_path, path});
  136.                 figures.erase(figures.begin() + i);
  137.                 ersd = true;
  138.             }
  139.        
  140.         }
  141.         if (!ersd) {
  142.             cout << -1;
  143.             return 0;
  144.         }
  145.     }
  146.    
  147.     cout << ans.size() << "\n";
  148.     for (int i = ans.size() - 1; i >= 0; i--) {
  149.         cout << ans[i].F + 1 << " " << ans[i].S << "\n";
  150.     }
  151.    
  152.     return 0;
  153. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement